**A circular singly linked list is a python data structure wherein the data elements are stored as nodes. Each node contains two variables. One of them is the data value that the node stores and the other is the address link to the next node in the linked list.**

A circular singly linked list is similar to a singly linked list. **The only difference is that the last node holds a reference to the first node of the linked list.**

When we reach the last node of the circular singly linked list, we have an option of going back to the first node. This is not possible in the case of a singly linked list.

**Table of Contents**

### Creation of a Circular Singly Linked List

**To create a circular singly linked list, we initialize the node and linked list class. Next, we set up our list by creating its first element and assigning the “head” and “tail” references to it.**

### Algorithm to create a Circular Singly Linked List

**Step 1:**Create a node class with the two required data variables.**Step 2:**Create the Circular Singly Linked List class and declare the head and tail nodes.**Step 3:**Create a new node and assign it a value.**step 4:**Set the “next” reference of the newly created node to none.**Step 5:**Set both the head and tail references to the new node.**Step 6:**Terminate.

### Method to create a Circular Singly Linked List

```
#Creating the Node class
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
#Create a circular singly linked list class to initialize head and tail references
class CSinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# Function to create Circular Singly Linked List
def createCSLL(self, value):
new_node = Node(value)
new_node.next = None
self.head = new_node
self.tail = new_node
print("The circular singly linked list has been created.")
#Initialize the linked list with a new node
circularSLL = CSinglyLinkedList()
circularSLL.createCSLL(5)
print([node.value for node in circularSLL])
#Output
The circular singly linked list has been created.
[5]
```

### The iterator function

Since the custom-created linked list is not iterable, we have to add an “__iter__” function so as to traverse through the list.

```
#Iterator Function
def __iter__(self):
node = self.head
while node:
yield node
node = node.next
if node == self.tail.next:
break
```

#### Time and Space Complexity

The time complexity for initializing a circular singly linked list is **O(1). **The space complexity is **O(1)** as no additional memory is required to initialize the linked list.

### Insertion in Circular Singly Linked List

A node can be inserted in a circular singly linked list in any one of the following three ways.

- At the beginning of the linked list
- In between the linked list
- At the end of the linked list

### Insertion Algorithm

#### Algorithm to insert a node at the beginning

**Step 1:**Create a node and assign a value to it.**Step 2:**Assign the “next” reference of the node as head.**Step 3:**Set the created node as the new head.**Step 4:**Assign “head” to the “next” reference of the tail.**Step 5:**Terminate.

#### Method to insert a node at the beginning

```
#Insertion at the beginning in a Circular Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
class CSinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
#Function to add node in the beginning
def atBeg(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
self.tail.next = self.head
#Initially, we have a linked list (1,3,5,7,9) called "csll".
csll.atBeg(0)
print([node.value for node in csll])
#Output
[0, 1, 3, 5, 7, 9]
```

#### Algorithm to insert a node in between the linked list

**Step 1:**Create a node and assign a value to it.**Step 2:**If the previous node doesn’t exist, return an error message and move to step 5.**Step 3:**Assign the “next” reference of the previous node to the “next” reference of the new node.**Step 4:**Set the “next” reference of the previous node to the newly added node.**Step 5:**Terminate.

#### Method to insert a node in between the linked list

```
#Insertion in between a Circular Singly Linked List
#Function to add node in the middle
def inMid(self,mid_node, value):
if mid_node is None:
print("Mentioned node doesn't exist")
return
new_node = Node(value)
new_node.next = mid_node.next
mid_node.next = new_node
#Initially, we have a linked list (1,3,5,7,9) called "csll" and "mid" node points to the value 3.
csll.inMid(mid, 11)
print([node.value for node in csll])
#Output
[1, 3, 11, 5, 7, 9]
```

#### Algorithm to insert a node at the end of the linked list

**Step 1:**Create a node and assign a value to it.**Step 2:**If the list is empty, assign new node to head and tail. Move to step 6.**Step 3:**Search for the last node. Once found, set its “next” reference pointing to the new node.**Step 4:**Assign the new node as the tail.**Step 5:**Assign “head” to the “next” reference of the tail.**Step 6:**Terminate.

#### Method to insert a node at the end of the linked list

```
#Insertion at the end in a Circular Singly Linked List
#Function to add node in the end
def atEnd(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
return
last_node = self.head
while(last_node.next != self.head):
last_node = last_node.next
last_node.next = new_node
self.tail = new_node
self.tail.next = self.head
#Initially, we have a linked list (1,3,5,7,9) called "csll".
csll.atEnd(0)
print([node.value for node in csll])
#Output
[1, 3, 5, 7, 9, 0]
```

#### Time and Space Complexity

In python, instead of iterating over the linked list and reaching the required position, we can directly jump to any point. Therefore, the time complexity of insertion in a circular singly linked list is **O(1). **

But, for insertion at the end, the time complexity is **O(N)** as we need to traverse to the last element. The space complexity is **O(1) **because it takes a constant space to add a new node.

### Traversal in Circular Singly Linked List

A circular singly linked list can only be traversed in the forward direction from the first element to the last. We get the value of the next data element by simply iterating with the help of the reference address.

### Traversing Method

```
#Traversal through Circular Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
class CSinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def printList(self):
node_print = self.head
while node_print:
print(node_print.value)
node_print = node_print.next
if node_print == self.tail.next:
break
#Initially, we have a linked list (1,3,5,7,9) called "csll".
csll.printList()
#Output
1
3
5
7
9
```

#### Time and Space Complexity

We need to loop over the linked list to traverse and print every element. The time complexity for traversal is **O(N)** where ‘N’ is the size of the given linked list. The space complexity is **O(1) **as no additional memory is required to traverse through a circular singly linked list.

### Searching in a Circular Singly Linked List

To find a node in a given circular singly linked list, we use the technique of traversal. The only difference, in this case, is that as soon as we find the searched node, we will terminate the loop.

The worst-case scenario for search is when we have the required element at the end of the linked list, in such a case we have to iterate through the entire linked list to find the required element.

### Searching Algorithm

**Step 1:**If the linked list is empty, return the message and move to step 5.**Step 2:**Iterate over the linked list using the reference address for each node.**Step 3:**Search every node for the given value.**Step 4:**If the element is found, break the loop. If not, return the message “Element not found”.**Step 5:**Terminate.

### Searching Method

```
#Searching in a Circular Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
class CSinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def searchList(self, value):
position = 0
found = 0
if self.head is None:
print("The linked list does not exist")
else:
temp_node = self.head
while temp_node:
position = position + 1
if temp_node.value == value:
print("The required value was found at position: " + str(position))
found = 1
break
if temp_node == self.tail.next:
break
temp_node = temp_node.next
if found == 0:
print("The required value does not exist in the list")
#Initially, we have a linked list (1,3,5,7,9) called "csll".
print(csll.searchList(7))
#Output
The required value was found at position: 4
```

#### Time and Space Complexity

The time complexity for searching a given element in the linked list is **O(N) **as we have to loop over all the nodes and check for the required one. The space complexity is **O(1) **as no additional memory is required to traverse through a circular singly linked list and perform a search.

### Deletion of node from Circular Singly Linked List

**To delete an existing node from a circular singly linked list, we must know the value that the node holds. For deletion, we first locate the node previous to the given node. Then we point the “next” reference of this node to the one after the node to be deleted.**

A node can be deleted from a circular singly linked list in any one of the following three ways.

- Deleting the first node
- Deleting any given node
- Deleting the last node

### Deletion Algorithm

#### Algorithm to delete a node from the beginning

**Step 1:**If the linked list is empty, return a null statement and go to step 6.**Step 2:**If there’s only one element, delete that node and set head and tail to none. Go to step 6.**Step 3:**Set a “temp_node” pointing at head.**Step 4:**Assign head as the next node. Delete the temp node.**Step 5:**Assign “head” to the “next” reference of the tail.**Step 6:**Terminate.

#### Method to delete a node from the beginning

```
#Deletion at the beginning of a Cirular Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
class CSinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
#Function to delete node from the beginning
def delBeg(self):
if(self.head == None):
return
elif (self.head.next == self.tail.next):
self.head = self.tail = None
return
else:
temp_node = self.head
self.head = self.head.next
temp_node = None
self.tail.next = self.head
return
#Initially, we have a linked list (1,3,5,7,9) called "csll".
csll.delBeg()
print([node.value for node in csll])
#Output
[3, 5, 7, 9]
```

#### Algorithm to delete a node from between the linked list

**Step 1:**If the linked list is empty, return a null statement and go to step 6.**Step 2:**If the value to be deleted is the first node, set head to the next element and remove the first node. Go to step 6.**Step 3:**Iterate through the linked list and search for the element to be deleted.**Step 4:**Set “prev” as the node before the one to be deleted. Break the loop.**Step 5:**Delete the required node and set “next” reference of “prev” to the node after the deleted one.**Step 6:**Terminate.

#### Method to delete a node from between the linked list

```
#Function to delete a node from between the linked list
def delMid(self, del_value):
temp_head = self.head
if (temp_head is not None):
if (temp_head.value == del_value):
self.head = temp_head.next
temp_head = None
return
while (temp_head is not None):
if temp_head.value == del_value:
break
prev = temp_head
temp_head = temp_head.next
if (temp_head == None):
return
prev.next = temp_head.next
temp_head = None
#Initially, we have a linked list (1,3,5,7,9) called "csll".
csll.delMid(3)
print([node.value for node in csll])
#Output
[1, 5, 7, 9]
```

#### Algorithm to delete a node from the end

**Step 1:**If the linked list is empty, return a null statement and go to step 7.**Step 2:**If there’s only one element, delete that node and set head and tail to none. Go to step 7.**Step 3:**Set a “temp_node” pointing at head. Iterate the linked list till that node points to the second last node of the list.**Step 4:**Assign tail as the temp node. Set temp node to the next node, i.e., last in the list.**Step 5:**Delete the temp_node.**Step 6:**Assign “head” to the “next” reference of the tail.**Step 7:**Terminate.

#### Method to delete a node from the end

```
#Function to delete node from the end
def delEnd(self):
if(self.head == None):
return
elif (self.head.next == self.tail.next):
self.head = self.tail = None
return
else:
temp_node = self.head
while (temp_node.next is not self.tail):
temp_node = temp_node.next
self.tail = temp_node
temp_node.next = None
self.tail.next = self.head
return
#Initially, we have a linked list (1,3,5,7,9) called "csll".
csll.delEnd()
print([node.value for node in csll])
#Output
[1, 3, 5, 7]
```

#### Time and Space Complexity

The time complexity for deletion in a circular singly linked list is **O(N) **as we have to loop over all the nodes and search for the required one. The space complexity is **O(1) **as no additional memory is required to delete an element from a circular singly linked list.

### Deletion of entire Circular Singly Linked List

The deletion of an entire circular singly linked list is quite a simple process. All we have to do is set the two reference nodes “head” and “tail” to none.

#### Algorithm to delete an entire circular singly linked list

**Step 1:**If the linked list is empty, return an error message and go to step 5.**Step 2:**Delete the “head” node by setting it to none.**Step 3:**Delete the “tail” node by setting it to none.Delete the “next” reference of tail node by setting it to none.**Step 4:****Step 5:**Terminate.

#### Method to delete an entire circular singly linked list

```
#Deletion of an entire Circular Singly Linked List
class Node:
def __init__(self, value = None):
self.value = value
self.next = None
class CSinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def delCSLL(self):
if self.head is None:
print("The circular singly linked list does not exist.")
else:
self.head = None
self.tail.next = None
self.tail = None
print("The circular singly linked list has been deleted.")
#Initially, we have a linked list (1,3,5,7,9) called "csll".
sll.delCSLL()
#Output
The circular singly linked list has been deleted.
```

#### Time and Space Complexity

The time complexity for deletion of an entire circular singly linked list is **O(1) **because we are just setting the “head” and “tail” references to none. The space complexity is **O(1) **as well since there is no additional space required when deleting the references.