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