Generic selectors
Exact matches only
Search in title
Search in content
wb_sunny

Doubly Circular Linked Lists in Python

Doubly Circular Linked Lists

A doubly circular linked list is a data structure that is utilized to store records in a list. It is fundamentally the same as linked lists but with a few additional highlights. In this tutorial, we’ll look at what a doubly circular linked list is, how to make one in Python, and what is its output.

Pre-Requisites

We should first discuss a few data structures before moving onto doubly circular linked lists.

1. Linked Lists

A linked list is a list in which items are linked to other items in a specific way. Different types of linked lists have different ways of linking items.

The simplest linked list is the “singly linked list” or simply, a “linked list”. In this, each item links to the next item in the list. (But not in reverse). So to access the nth item, we will need to access the (n-1)th item first. And accessing the nth item enables us to access the (n+1)th item of the list.

We have direct access to the first item of the list, using which we can access the 2nd one, and then the 3rd one, and so on until the last item which does not have access to any other item in the list.

Each item in a linked list is called a node. Each node has a part that stores its data, and another part to store the link/reference to the next node.

Singly Linked List Repr
Singly Linked List Representation

2. Doubly Linked Lists

Doubly linked lists are similar to linked lists, but in this case, each node has two links, one to the next node and one to the previous node.

So, to access the nth node, we will need to first access the (n-1)th node or the (n+1)th node. And after we have accessed the nth node, using it, we can access the (n-1)th node or the (n+1)th node. That is, traversal can happen in either direction.

Each node is made of three parts, one for data and the other two for the previous and next links. It looks something like this:

Doubly Linked List Repr 3
Doubly Linked List Representation

3. Circular Linked Lists

Circular linked lists are also similar to linked lists, the only difference being that the last node links to the first node instead of having no link. So it forms a circular linkage between the nodes, and if we keep on accessing the next nodes, it will never end and go back to the start after the first node.

It looks something like this:

Circular Linked List Repr 1
Circular Linked List Representation

Doubly Circular Linked Lists

Now that we know how doubly linked lists and circular linked lists look like, it’s not hard to understand what a doubly circular linked list will be.

Here, each node contains three parts, one for the data and the other two for the links. Each node links to the next and previous nodes of the list. For the first node, there is no previous node, so it goes in a circle and links to the last node of the list. Similarly, for the last node, there is no next node, so it goes in a circle and links to the first node of the list.

To access any node, we need to access either the node after it or the node before it, and after accessing any node, the nodes after and before it can be directly accessed. But we can also access the last node directly from the first node and vice versa.

To visualize, a doubly circular linked list looks something like this:

Doubly Circular Linked List Repr
Doubly Circular Linked List Representation

In the above example, you can see that there are four nodes in the list and each node is connected to a node after it and a node before it. The last node points to the second-last node and the first node, and the first node points to the last node and the second node.

The head points to the start of the list, and now we can either traverse forward and reach the end or we can traverse backwards and reach the start of the list.

Implementing Doubly Circular Linked Lists in Python

We have to create two classes, one for the nodes and another that will use the nodes to create the linked list.

Class: Node

class Node:
    def __init__(self, data = None):
        self.data = data
        self.previous = self
        self.next = self

Initially, upon creation of a node, it will point to itself in both directions to form a doubly circular linked list with only one item.

Class: Doubly Circular Linked List

class DCLL:
    def __init__(self):
        self.head = None
        self.count = 0
    
    def __repr__(self):
        string = ""
         
        if(self.head == None):
            string += "Doubly Circular Linked List Empty"
            return string
         
        string += f"Doubly Circular Linked List:\n{self.head.data}"       
        temp = self.head.next
        while(temp != self.head):
            string += f" -> {temp.data}"
            temp = temp.next
        return string
    
    def append(self, data):
        self.insert(data, self.count)
        return
    
    def insert(self, data, index):
        if (index > self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
        
        if self.head == None:
            self.head = Node(data)
            self.count = 1
            return
        
        temp = self.head
        if(index == 0):
            temp = temp.previous
        else:
            for _ in range(index - 1):
                temp = temp.next
        
        temp.next.previous = Node(data)
        temp.next.previous.next, temp.next.previous.previous = temp.next, temp
        temp.next = temp.next.previous
        if(index == 0):
            self.head = self.head.previous
        self.count += 1
        return
    
    def remove(self, index):
        if (index >= self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
            
        if self.count == 1:
            self.head = None
            self.count = 0
            return
        
        target = self.head
        for _ in range(index):
            target = target.next
            
        if target is self.head:
            self.head = self.head.next
            
        target.previous.next, target.next.previous = target.next, target.previous
        self.count -= 1
        
    def index(self, data):
        temp = self.head
        for i in range(self.count):
            if(temp.data == data):
                return i
            temp = temp.next
        return None
    
    def get(self, index):
        if (index >= self.count) | (index < 0):
            raise ValueError(f"Index out of range: {index}, size: {self.count}")
            
        temp = self.head
        for _ in range(index):
            temp = temp.next
        return temp.data
    
    def size(self):
        return self.count
    
    def display(self):
        print(self)

The above class contains many methods, let’s discuss them one by one.

The __init__ method

We declare two members, the head and the count initialized by None and 0 respectively because there are no nodes in the list at the beginning.

The __repr__ method

The __repr__ method will return a string that will print the contents of the list appropriately on the screen.

The append and insert method

We can either append or insert nodes in the list. The append method is created just for convenience as it calls the insert method and sends the appropriate values.

In the insert method, we first check if the index is in range or not, and if not, we raise a ValueError. Then, if the list is empty, then we simply assign a new node to the head and make the count equal to 1. Now we reach the node just before the index where the new node is to be inserted.

At this point, we make the previous of the node at the specified index equal to the new node. Then we make the new node’s next and previous equal to the node at the specified index and the node before the specified index respectively. And now we make the next of the node before the specified index equal to the new node. Finally, if the specified index was 0, then we make the head point to the node just before where it was pointing.

Just increment the count and the insert method is done.

The remove method

In this method too we first check if the index is out of range and throw a ValueError if it is. Then if there is one node only, we simply make the head as None and make the count as 0 and return.

If not, we reach the required node to be deleted, and if the target node is the head, we make the head point to the node after it so that we don’t lose the list.

Finally, we make the next of the node before the specified index point to the node after the specified index, and we make the previous of the node after the specified index point to the node before the specified index. This will make the node at the specified index unreachable from the list (basically skipped), and we decrement the count to finish the method.

The index, get, size, and display method

The index method searches linearly through the list and returns the index if the item is found, None otherwise.

The get method returns the item at the specified index, and raises a ValueError if the index is out of range.

The size method returns the number of items in the list.

The display method prints the list.

The Output

Python DCLL Output 1
Output for the initialization, insertion, and append methods
Python DCLL Output 2
Output for remove, index, get, size, and display methods.

Conclusion

In this tutorial, we studied the doubly circular linked list in detail and implemented it in Python. Hope you enjoyed learning about it and see you in the next tutorial.