In this article, we are going to implement a singly linked list, a data structure that contains a sequence of nodes, where a node has a value and a reference to the next node. We only need access to the first node to traverse the complete linked list since each node references the next node. The first node is usually known as the head. Moreover, the last node’s next pointer points to NULL since there are no more nodes after it.
A singly Linked List Implementation
This implementation of a singly linked list contains the following functionalities:
Insert
It takes a value and adds it at the end of the list. If the value to be inserted is the first one, then the head pointer will be NULL
because the list is empty. So, we create a node with the given value and make the head point to this node. Remember that, by default, the value of the next pointer is NULL
.
If the list already contains some nodes, then we have to traverse to the end of the list to insert the new node with the given value. For that, we create a temp variable that is initially equal to the head node. We iterate over the list using the while loop. At each iteration, we set temp to point to its next node to move forward. The loop runs till temp.next
is equal to NULL
, i.e., the last node. Once we get the last node, we set its next pointer to refer to the new node.
Delete
This method takes a value and removes it from the list. The idea is to find the node(prev)
before the node to be deleted (temp). Once it is found, change prev.next
to point to the next of temp. Finally, delete temp to free the memory. If no node with the given value is found, we raise an error.
Traverse
This method iterates over the whole list and prints values. To do that, we create a temp node that is initially equal to the head node. Then, we iterate over the list using a while loop and print each node’s value. At each iteration, we set temp to point to its next node to advance the list. The loop runs till temp is equal to NULL
, i.e., when we have gone through all list elements.
Search
This method takes a value and finds the position of its node. We create a temp node that points to the head and a variable i = 0
to keep track of the index. We iterate over the list using the while loop. At each iteration, we compare the current node’s value to the given one. If both are equal, we return the position. Otherwise, we change the temp to point to its next node and increment the i
variable. If no node with the given value is found, we raise an error.
Code to implement a singly inked list
The code is given below.
#node for the linked list class Node: def __init__(self, value=None): self.value = value self.next = None # The reference to the next node #implementation of linked list class LinkedList: def __init__(self): self.head = None #adds a node at the end of the linked list def insert(self, value): node = Node(value) #create a node if self.head == None: #if list is empty insert a node at the start self.head = node else: temp = self.head #iterate through the list till last node is found while temp.next: temp = temp.next temp.next = node #adding a new node #find the position of the given value in the list def search(self, value): temp = self.head i = 0 #iterate through the list while temp: if temp.value == value: return i temp = temp.next i += 1 raise KeyError(f'Item with the value {value} does not exist') #remove the node with the given value from the list or throw an error def delete(self, value): if self.head: #if the list is not empty if self.head.value == value: #if the node to be deleted is the first node deleted_node = self.head self.head = self.head.next del deleted_node return else: temp = self.head.next #node after the head node prev=self.head #iterate through the list while temp: if temp.value == value: prev.next = temp.next del temp return else: prev = temp temp = temp.next raise KeyError(f'Item with the value {value} does not exist') #traverse the complete list and print the node value def traverse(self): temp = self.head while temp: print(temp.value, end="\t") temp = temp.next print("") ll = LinkedList() #create list_1 #insert values ll.insert(1) ll.insert(8) ll.insert(6) ll.insert(2) print("Linked list:") ll.traverse() #search operation print("The value 2 is found at position", ll.search(2)) print("The value 1 is found at position", ll.search(1)) #delete operation ll.delete(2) ll.delete(8) print("Linked list:") ll.traverse()
Output
Linked list: 1 8 6 2 The value 2 is found at position 3 The value 1 is found at position 0 Linked list: 1 6
ll = LinkedList() #create list_1 #insert values ll.insert(1) ll.insert(8) ll.insert(6) print("Linked list:") ll.traverse() #search operation print("The value 2 is found at position", ll.search(2))
Output