What is a Circular Doubly Linked List?

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.