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!