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.
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:
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:
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:
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
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.