If you have went through my last blog, you certainly have clear idea on Doubly Linked List, right? Okay so, to make it more efficient, Circular Doubly List's tail node point to the head and head points to the tail. Means, there's no None
present here. So we can go from the last node to the first time and the vice versa in a very short time.
Constructor Creation : The Node class is going to be the same as before.
class CircularDLL:
def __init__(self, value):
new_node = Node(value)
new_node.next = new_node
new_node.prev = new_node
self.head = self.tail = new_node
self.length = 1
Appending CDLL
This is a bit difference from Circular singly linked list. Here we are going to -
1) update the last node's next reference to the new node and update the first node's previous reference to point to the new node
2) Update the new node's previous reference to point to the tail and new node's next reference to point to the head. Finally, move tail to the new node
Visualization :
Code :
def append(self, value):
new_node = Node(value)
if self.length == 0:
self.head = self.tail = new_node
new_node.next = new_node
new_node.prev = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.head.prev = new_node
new_node.next = self.head
self.tail = new_node
self.length += 1
Time and space complexity : O(1)
__str__ method CDLL
First, we are going to make a pointer which will point to the head. Then we will run a loop and save the values in string form in a variable. While current node is not none, we are going to take the nodes value and print it to result
. Then we will move the current node to the next node. After the loop ends, current node will go to the head through the reference link, in that case we will put a break statement if that happens. So the code will check if its the head or not, if it's not the head then it will append <->
to the result
, otherwise it will end the loop.
def __str__(self):
current_node = self.head
result = ""
while current_node is not None:
result += str(current_node.value)
current_node = current_node.next
if current_node == self.head : break
result += " <-> "
return result
Prepend method CDLL
First we will create a new node. Then we will add it in the beginning of the CDLL. Here we are going to -
update the tail's next reference -> new node
update head's next reference -> new node
update new node's next reference -> head
update new node prev reference -> tail
update the new node as the head
Visualization :
Code:
def prepend(self,value)
if self.length == 0:
self.head = self.tail = new_node
new_node.next = new_node.prev = new_node
else:
self.tail.next = new_node
self.head.prev = new_node
new_node.next = self.head
new_node.prev = self.tail
self.head = new_node
self.length += 1
Time and space complexity : O(1)
Traverse method CDLL
Here, we will go through the whole loop one by one node. Point to remember is, as the last node points back to the first node, we have to write the code in a way where it doesn't go to the head of the CDLL. We will assign a pointer to perform the traversal.
Code:
def traverse(self):
current_node = self.head
while current_node:
print(current_node.value)
current_node = current_node.next
if current_node == self.head : break
Time complexity : O(N), Space complexity: O(1)
Reverse Traverse method CDLL
Reverse traverse means, we will visit all the nodes from the tail to backwards through previous reference. We will set a pointer to the tail and write a code that will perform backward traversal.
def reverse_traverse(self):
current_node = self.tail:
while self.tail:
print(current_node.value)
current_node = current_node.prev
if current_node == self.head : break
Time complexity : O(N), Space complexity: O(1)
Search method CDLL
To search for a node, we have to pass a value as a parameter. The we will search for the target value. If found, we will return True. We will set a pointer node here. If we can't find the node in side the loop, we will return False outside of the loop. Another fact is, as the tail goes back to head - if the targeted node is not found then the current node will go back to the head. That's a trouble, na? To avoid the infinity loop, we will put another if condition saying if current node is head, loop will break.
Code:
def search(self,target):
current_node = self.head
while current_node:
if current_node.value == target:
return True
current_node = current_node.next
if current_node == self.head: break
return False
Time complexity : O(N), Space complexity: O(1)
Get method CDLL
We will access node via index, or in other words, we will bring out the value of an index using get(). And we will divide the length into half as before for better optimization. I mean, if we have the ability to afford back links so why not use them, right? Okay so, if the index is in first half, the loop will start from the head until the half length and vice versa for the 2nd half. We will pass index as the parameter here. The we will return the pointer node.
For backward range, we will decrease the value by 1 each time until index
def get(self, index):
current_node = None
if index < 0 or index >= self.length:
return None
if index <= self.length//2: # ----> O(N/2)
current_node = self.head
for _ in range(index):
current_node = current_node.next
else:
current_node = self.tail # ----> O(N/2)
for _ in range(self.length-1, index, -1):
current_node = current_node.prev
return current_node
Time complexity : O(N), Space complexity: O(1). (After adding both the O(N/2), it will eliminate the 1/2
and O(N) will remain)
Set method CDLL
Set method takes two params - 1. index, 2. value. Basically, set method will access the node of the given index and will change the value of the node with the given value. The code will run with the help of get()
, because get method will use the index and return that node. Let's start by assigning a pointer node to the head.
def set_value(self,index,value):
current_node = self.head
temp = self.get(index)
if index < 0 or index >= self.length: Return None
if temp:
temp.value = value
return True
return False
Time complexity : O(N), Space complexity: O(1) [ get method takes O(n) ]
Insert method CDLL
Here, we are going to insert a new node at a specific index. It's easy, don't worry. Keep it in mind, we will assign the pointer node to the previous node of the given index, not to the head.
Visualization:
For the sake of simplicity, I have marked steps, i.e. 1,2,3,4. But following these steps are not mandatory, as long as you can understand what's happening you are good to go. Once, you know what's happening, the steps won't be necessary.
Code :
I have put if conditions to avoid edge cases.
def insert(self, index, value):
new_node = Node(value)
prev_node = self.get(index-1)
if index == 0:
self.prepend(value)
return
if index == -1:
self.append(value)
return
if index < -1 or index >= self.length:
return None
prev_node.next = new_node
prev_node.next.prev = new_node
new_node.prev = prev_node
new_node.next = prev_node.next
self.length += 1
Time complexity : O(N), Space complexity: O(1)
Pop first method CDLL
Detaching the first node and returning the node.
Code:
def pop_first(self):
if self.length == 0:
return none
popped_node = self.head
popped_node.next = None
popped_node.prev = None
self.head = self.head.next
self.tail.next = self.head
self.head.prev = self.tail
self.length -= 1
return popped_node
Time complexity : O(1), Space complexity: O(1)
Pop method CDLL
Detaching the last node and returning the node.
def pop(self):
if self.length == 0:
return none
popped_node = self.tail
if self.length == 1:
self.head = self.tail = None
self.tail = self.tail.prev
popped.next = popped.prev = None
self.tail.next = self.head
self.head.prev = self.tail
self.length -= 1
return popped_node
Time complexity : O(1), Space complexity: O(1)
Remove Method CDLL
Removing any given node based on it's index.
Visualization :
Code:
def remove(self, index):
popped_node = self.get(index)
prev_node = self.get(index-1)
if index == 0:
return self.pop_first()
if index = self.length-1:
return self.pop()
if index < 0 or index >= self.length:
return None
prev_node.next = popped_node.next
popped_node.next.prev = prev_node
popped_node.next = popped_node.prev = None
self.length -= 1
return popped_node
Time complexity : O(N), Space complexity: O(1) (because of get method)
Delete All Nodes CDLL
def delete_all(self):
self.head = self.tail = None
self.length = 0
With this, linked list finally ends here!! Congratulations for finishing this, great job indeed! See you in the next blog. Don't forget to stay hydrated.