Table of Contents

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:

- We check if the node to be deleted is the first node. If it is, then if the list contains only a single item, we set the head to
`NULL`

. Otherwise, we find the last node. - We update the head to refer to its next node and set the last node next to the new head.
- We delete the previous head and return from the method.

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**

Blog Hero