In this article, we will implement a circular singly linked list. A singly linked list is similar to the singly linked list, except the next pointer of the last node points to the first node and is not NULL.

Implementation of a Circular Singly Linked List

Let’s go ahead and see how to implement the basic functionalities of a circular linked list.

Insert

It takes a value and adds it at the end of the list. Initially, when the list is empty, i.e., head=NULL, we create a node with the given value and assign it to the head. Moreover, we set the next pointer of the head to itself as this is the only node.

When the list contains other items, then we need to find the last node. For that, we create a temp variable that starts from the head and continues moving forward till its next is equal to the head. We make a new node with the given value and the next pointer pointing to the head. We assign this node to the next temp (the last node).

Delete

It takes a value and removes it from the list. If not found, it throws an error.

Below are the steps needed to perform a delete operation on a Circular singly linked list:

If the node to be deleted is not the first one, we find the node (prev) before the node to be deleted (temp). Once found, we change prev.next to point to the next of temp. Finally, delete temp to free the memory.

Search

This method takes a value and finds the position of its node. If not found, it raises an error.

To search a circular linked list, first, we check if the head’s value is equal to the given one. If it is, we return 0. Otherwise, we create a temp variable that initially refers to the head’s next. We run a while loop that runs till temp is equal to the head, i.e., the list is traversed completely. At each iteration, we compare the current node’s value with the given one. If they are equal, we return the index of that node. Otherwise, we advance temp to point to its next node and increment i.

Traverse

It iterates over the list and prints each node’s value. It works similar to the search method, except it displays each node’s value and does not perform any comparison.

Code to Implement a Circular Singly Linked List

The code is given below.

#node for the linked list
class Node:
  def __init__(self, value=None, next=None):
    self.value = value 
    self.next = next #reference to the next node

#implementation of linked list
class CircularLinkedList:
  def __init__(self):
    self.head = None

  #adds a node at the end of the linked list
  def insert(self, value):
    node = Node(value, self.head) #create a node
    if self.head == None: #if list is empty insert a node at the start
      self.head = node
      self.head.next = node 
    else:
      temp = self.head
      #iterate through the list till last node is found, i.e., last node next pointer refers to the first node.
      while temp.next != self.head: 
        temp = temp.next 
      
      temp.next = node #adding a new node
  
  #find the position of the given value in the list
  def search(self, value):
    if self.head: #list is not empty
      if self.head.value ==  value: #if the given value is equal to the head's value
        return 0
      temp = self.head.next
      i = 1
      #iterate through the list
      while temp != self.head:
        if temp.value == value:
          return i
        temp = temp.next
        i += 1
    
    raise KeyError(f'Item with the value {value} does not exist')
  
  def deleteHead(self):
    deleted_node = self.head
    if self.head.next == self.head: #list contains a single node only
      self.head = None
    else:
      #get the last node
      temp = self.head
      while temp.next != self.head:
        temp = temp.next
      self.head = self.head.next #update the head
      temp.next = self.head #make the last next refer to the new head
    del deleted_node

  #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
        self.deleteHead()
        return
      else:
        temp = self.head.next #node after the head node
        prev=self.head
        #iterate through the list
        while temp != self.head:
          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):
     if self.head: #list is not empty
      print(self.head.value, end="\t") #display value of head node
      temp = self.head.next
      #iterate through the list
      while temp != self.head:
        print(temp.value, end="\t")
        temp = temp.next
      print("")

ll = CircularLinkedList() #create list

#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(1)
ll.delete(6)
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:
8	2

ll = CircularLinkedList() #create list

#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