*What is Circular Singly Linked List?*

Circular singly linked is same as singly linked list. In single linked list, the last node points to `none`

but in circular singly linked list, the last node will be pointing back to its `head`

.

Circular singly linked lost creation:

```
class Node:
def __init__(self, value):
self.value = value
self.next = None
class CSLinkedList: #with 1 element
def __init__(self):
new_node = Node(value)
new_node.next = new_node
self.head = new_node
self.tail = new_node
self.length = 1
class CSLinkedList: #empty list
def __init__(self) :
self.head = self.tail = None
self.length = 0
```

Here, the time and space complexity is O(1) times complexity for both of the versions, because it takes cons time operation and no extra additional memory is required for this code.

*Append Method*

Append means we are adding a new node to the last of a linked list.

Visualization

Code:

```
class CSLinkedList: #empty linked list
def __init__(self):
self.head = self.tail = None
self.length = 0
def append(self,value):
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
new_node.next = new_node
else:
self.tail.next = new_node
new_node.next = self.head
self.tail = new_node
self.length += 1
```

All the lines will take O(1) time complexity, at the end of the code we are increasing the length by 1, that's also O(1) time complexity. It's obvious the space complexity will be O(1) too because we are just adding one element to the linked list.

*Print Circular Singly List*

As from the previous blog, we have learned printing linked list ain't similar to normal lists. We have to take out the value from it and store it somewhere then we will be able to print it.

Visualization :

Code :

```
def __str__(self)
temp_node = self.head
result = ''
while temp_node != None:
result += str(temp_node.value)
temp_node = temp_node.next
if temp_node == self.head:
break
result += "->"
return result
```

*Prepend Method*

Prepend means adding at the beginning of the linked list.

Visualization :

Code :

```
def prepend(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
new_node.next = new_node
else:
new_node.next = self.head
self.tail.next = new_node
self.head = new_node
self.length += 1
```

All the lines will take O(1) time complexity, at the end of the code we are increasing the length by 1, that's also O(1) time complexity. It's obvious the space complexity will be O(1) too because we are just adding one element to the linked list

*Insert Method*

Now I will write on how to insert a new node to any given location in the circular singly linked list. We will take two params, `value`

and `index`

. Based on the index, we will insert a new node.

Visualization :

Code :

```
def insert(self,index, value) :
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
new_node.next = new_node
if index > self.length or index < 0:
print("Error")
else:
temp_node = self.head
for _ in range(index-1):
temp_node = temp_node.next #if index is 2, temp_node will stop at 1
new_node.next = temp_node.next
temp_node.next = new_node
self.length += 1
```

Every line in this code will take O(1) time complexity except the for loop. In the worst case, we might have to loop through all the elements so it will take O(N) time complexity. But the space complexity will take O(1)

*Traversing*

Traversing means visiting all the elements one by one.

Visualization :

Code :

```
def traverse(self):
temp_node = self.head
while temp_node != None:
print(temp_node.value)
temp_node = temp_node.next
if temp_node == self.head: #to avoid infinity loop
break
```

As we are going through all the element (a loop) the time complexity will be O(N). Additionally, no extra space is required to perform this program, so the space complexity is going to be O(1)

*Searching method*

It's going to be a linear search. We will take "target" param so see if this is the value we are looking for. If not, we will continue to the next node. If we find the value, we return `true`

. If we don't find the value, we return `false`

Code :

```
def search(self, target):
current_node = self.head
while current_node != None:
if current_node == target:
return True
current_node = current_node.next
if current_node == self.head:
break
return False
```

As you can see, there's a loop. So the overall time complexity is going to be O(N) time complexity and the space complexity is going to be O(1)

*Get method*

Code :

```
def get(self,index)
if index < -1 or index >= self.length:
return None
elif index == -1:
return self.tail.value
temp_node = self.head
for _ in range(index):
current = current.next
return current.value
```

if condition will take O(1) time complexity, for loop will take O(N) time complexity. Space will take O(1).

*Set method*

```
def set_value(self, index, value) :
temp = self.get(index)
if temp:
temp.value = value
return True
return False
```

get method takes O(N) time complexity, so the overall time complexity will be O(N) time complexity and the space complexity is O(1)

*Pop first method*

When we will call pop first method, it is going to remove the first node and return the value of the first node.

Code :

```
def pop_first(self):
popped_node = self.head
if self.length == 0:
return None
if self.length == 1:
self.head = self.tail = None
else:
self.head = self.head.next
self.tail.next = self.head
popped_node.next = None
self.length -= 1
return popped_node
```

Space complexity : O(1)

Time complexity : O(1)

*Pop method*

Pop method is going to remove the last node and return.

Code :

```
def pop_last(self)
popped_node = self.tail
if self.length == 0:
return None
if self.length == 1:
self.head = self.tail = None
else:
temp = self.head
while temp.next is not self.tail:
temp = temp.next
temp.next = self.head
self.tail = temp
popped_node.next = None
self.legth -= 1
return popped_node
```

Time complexity : O(N)

Space complexity : O(1)

*Remove method*

Code:

```
def remove(self, index)
if index < 0 or index >= self.length:
return None
elif index == -1:
return self.tail
elif index == 0:
return self.pop_first()
prev_node = self.get(index-1)
popped_node = prev_node.next
prev_node.next = popped_node.next
popped_node.next = None
return popped_node
```

Time complexity : O(N)

Space complexity : O(1)

*Delete All Nodes*

Code:

```
def delete_all(self) :
if self.length == 0:
return None
self.tail.next = None
self.head = None
self.tail = None
self.length = 0
```

Thus, the garbage collector will collect all the nodes. Time and space complexity both are O(N)

That's all for today. In the next blog, we will solve some problem based on Circular Singly Linked List. Stay hydrated!