In this blog post you will learn how to implement a linked list in Python from scratch. We will understand the internals of linked lists, the computational complexity of using a linked list and some advantages and disadvantages of using a linked list over an array.
Introduction
Linked list is one of the most fundamental data structure in programming. Imagine you are building a directory of image files and each of these files are linked to each other. How could we model this problem? There are various data structures at our disposal to solve this problem. You could use an array to store the files in a contiguous block of memory. The advantage of using an array is its quick access time. While an array does help us in accessing the files in O(1) time, there are some disadvantages of using an array if we would like to insert a new file or delete a new file. A linked list helps us in inserting and deleting an element in constant time.
A linked list is represented by a collection of nodes and each node is linked to the other node by using a pointer. Figure 1 demonstrates the concept of a linked list.
Figure 1: Linked List
As you can see in Figure 1, a linked list is created by connecting the next pointer of a node with another node. Let us now get started by opening our editor and constructing a singly linked list in Python.
A linked list has a collection of nodes, so we first start by constructing a Node class
class Node(object):
def __init__(self, value):
self.data = value
self.next = NoneThe Node class has two member variables — the data and the pointer called next which points to the next node. Whenever a new node is created, the next pointer will be set to a None value.
Now let us begin by constructing the Linked List class. The class will be composed of the following functionalities
- Inserting an element at the front of the Linked List
- Inserting an element at the back or the tail of the Linked List
- Deleting an element at a specified index in the Linked List
- Searching the Linked List for a specified data value
- Displaying the Linked List
Let us begin by constructing the Linked List and initializing the member variables
class LinkedList(object):
def __init__(self):
self.head = NoneOperations on a Linked list
Next, you’ll learn about all the discussed linked list operations—and how to implement them in Python!
Inserting an element at the front of the Linked List
In order to insert a new node at the front of the list we first need to check if the list is empty or not. We do this by checking the head of the list. If the list is empty then we can point the head to the newly created node. If, however, the list is not empty, we will point the next value of the newly created node to the head of the linked list, and we will reassign the head pointer to point to the newly created node. The code snippet below demonstrates how you can implement this functionality.
class LinkedList(object):
def __init__(self):
self.head = None
def insert_front(self, node):
if self.head is not None:
node.next = self.head
self.head = node
else:
self.head = nodeInserting an element at the end of the list
In order to insert an element at the end of the list we need to traverse the list till we reach the tail of the list and as soon as we reach the tail of the list we point the next pointer of the tail to the newly created node.
def insert_back(self, node):
if self.head is not None:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
else:
self.head = nodeDeleting an element at a specified index in the Linked List
Now we will look at how to delete an element from the linked list given an index value.
There are three conditions we need to check if we would like to delete a node from a linked list.
- Deleting a node if the linked list is empty: We will first check if the linked list is empty or not. If the list is empty we print a message that the linked list is empty and return from the function.
- Deleting the head of the linked list: The second condition arises when we would like to delete the first node or in other words the head of the linked list. To remove the head of the linked list we first create a temporary node to point to the head of the node and then reassign the head pointer to the next node of the original head. We then delete the temporary node.
- Deleting a node at an arbitrary position: In order to delete a node at an arbitrary position we traverse through the linked list and check if the value that we would like to delete matches with that of the current node. If a match is found we reassign the previous node’s next pointer to the current node’s next node. We then delete the current node.
def delete(self, value):
if self.head is None:
print('Linked List is empty')
return
if self.head.data == value:
node_to_delete = self.head
self.head = self.head.next
del node_to_delete
return
# deletion at arbitary position
current_node = self.head
while current_node is not None:
if current_node.next.data == value:
temp_node = current_node.next
current_node.next = temp_node.next
del temp_node
return
current_node = current_node.next
Searching the Linked List for a specified value
We will now look at searching for a given value in a linked list. In order to achieve this we start at the head of the linked list and at every iteration we check for the node’s value. If a match is found we print the location of that node by keep track of a counter variable that we have defined. If no match is found we jump to the next node and repeat the steps to check for a match.
def search(self, value):
counter = 1
current_node = self.head
while current_node is not None:
if current_node.data == value:
print('Node with value {} found at location {}'.format(value, counter))
return
current_node = current_node.next
counter += 1
print('Node with value {} not found'.format(value))
Displaying the Linked List
We will create a function called display to traverse through the linked list and print the data value of the node. Once we print the value we jump to the next node by updating the value of the current node.
def display(self,):
current_node = self.head
while current_node is not None:
if current_node.next is None:
print(current_node.data, end=' ', flush=True)
else:
print(current_node.data, end='-->', flush=True)
current_node = current_node.next
print('\n')
Demonstration
Let us now see all the functionalities in action. We start by creating four nodes with the following values
We then create an instance of the LinkedList class and insert the above nodes at the back of the linked list.
node1 = Node(12) node2 = Node(13) node3 = Node(14) node4 = Node(15) ll = LinkedList() ll.insert_back(node1) ll.insert_back(node2) ll.insert_back(node3) ll.insert_back(node4) ll.display()
We can see the output as follows
12-->13-->14-->15
Next we will insert a node at the front of the linked list as follows.
node5 = Node(1) ll.insert_front(node5) ll.display()
On calling the display function, we get the following output
1-->12-->13-->14-->15
Now we will look at the search functionality to search for a node with a specific data value and get the position of that node in the linked list.
ll.search(12) ll.search(1) ll.search(5) ll.search(15)
As we can see in the output below we can observe that the node with the value 12 is at position 2, the node with the value 1 is at the first position, the node with the value 5 is not there in the list and the node with the value 15 is located at the position 5.
- Node with value 12 found at location 2
- Node with value 1 found at location 1
- Node with value 5 not found
- Node with value 15 found at location 5
We will now delete a node with a given value
ll.delete(12) ll.display()
As we can see in the output below we were able to delete the node with the value 12 and update its previous pointer i.e. the node with the value 1 now points to the node with the value 13.
1-->13-->14-->15
As a last step we will see what happens if we insert a new node at the specific location. In the example below we will try to insert a node with value 12 at the position 2, delete the node with the value 15 and 1 and observe the output after each step.
ll.insert(Node(12), 2) ll.display() ll.delete(15) ll.display() ll.delete(1) ll.display()
We get the following output
1-->12-->13-->14-->15 1-->12-->13-->14 12-->13-->14
You can see the entire code below
class Node(object):
def __init__(self, value):
self.data = value
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
def insert_front(self, node):
if self.head is not None:
node.next = self.head
self.head = node
else:
self.head = node
def insert_back(self, node):
if self.head is not None:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
else:
self.head = node
def insert(self, node, index):
if self.head is not None:
current_counter = 1
current_node = self.head
while current_node is not None:
if current_counter == (index - 1):
node.next = current_node.next
current_node.next = node
current_node = current_node.next
current_counter +=1
else:
print('List is empty')
self.insert_front(node)
def search(self, value):
counter = 1
current_node = self.head
while current_node is not None:
if current_node.data == value:
print('Node with value {} found at location {}'.format(value, counter))
return
current_node = current_node.next
counter += 1
print('Node with value {} not found'.format(value))
def delete(self, value):
if self.head is None:
print('Linked List is empty')
return
if self.head.data == value:
node_to_delete = self.head
self.head = self.head.next
del node_to_delete
return
# deletion at arbitary position
current_node = self.head
while current_node is not None:
if current_node.next.data == value:
temp_node = current_node.next
current_node.next = temp_node.next
del temp_node
return
current_node = current_node.next
def display(self,):
current_node = self.head
while current_node is not None:
if current_node.next is None:
print(current_node.data, end=' ', flush=True)
else:
print(current_node.data, end='-->', flush=True)
current_node = current_node.next
print('\n')
if __name__ == "__main__":
node1 = Node(12)
node2 = Node(13)
node3 = Node(14)
node4 = Node(15)
ll = LinkedList()
ll.insert_back(node1)
ll.insert_back(node2)
ll.insert_back(node3)
ll.insert_back(node4)
ll.display()
node5 = Node(1)
ll.insert_front(node5)
ll.display()
ll.search(12)
ll.search(1)
ll.search(5)
ll.search(15)
ll.delete(12)
ll.display()
ll.insert(Node(12), 2)
ll.display()
ll.delete(15)
ll.display()
ll.delete(1)
ll.display()
Conclusion
In this tutorial we saw how to implement a linked list from scratch. We then saw how to do some common operations like insertion, deletion, search and traversal on a linked list. Linked Lists have an advantage when we would like to insert or delete a node from our list. We can achieve both these tasks in constant time. In the next tutorial we will look at some common linked list problems and how to solve them efficiently.