Circular Doubly Linked List in Python
In this tutorial, you‚ will learn how to implement a circular doubly linked list using the Python programming language. A circular linked list is a data structure where each node has a reference to the next node, and the last node’s next pointer points back to the first node, creating a circular structure. On top of that a doubly linking indicates that the nodes are not connected uni-directional, they are bi-directionally linked.
The table of content is structured as follows:
Let’s dive into the implementation!
Implementation of Circular Doubly Linked List
First of all, we start by defining a Node class. Each node has a data attribute to store the actual data and next and prev attributes to reference the next and previous nodes, respectively.
class Node: def __init__(self, data): self.data = data self.next = None self.prev = None
Next, we define the CircularDoublyLinkedList class.
- The
headattribute points toNone, indicating an empty list. - The
is_empty()method checks if the list is empty by verifying if the head is None. - The
append()method adds a new node with the given data at the end of the list. If the list is empty, the head is set to the new node. Otherwise, we update the references (pointers) to maintain the circular doubly linked list structure. - The
prepend()method adds a new node with the given data at the beginning of the list. If the list is empty, the head is set to the new node. Otherwise, we update the references accordingly. - The
insert_after()method inserts a new node with the given data after a specified value in the list. It searches for the specified value and, if found, inserts the new node after it by updating the references. - The
remove()method removes the node with the specified data from the list. It searches for the specified data and removes the node by updating the references. If the removed node was the head, the head is updated accordingly. - The
display()method prints the elements of the circular doubly linked list in order.
class CircularDoublyLinkedList: def __init__(self): self.head = None def is_empty(self): """ Check if the list is empty. """ return self.head is None def append(self, data): """ Add a new node with the given data at the end of the list. """ new_node = Node(data) if self.is_empty(): # If the list is empty, set the new node as the head self.head = new_node else: # If the list is not empty, update the references to maintain the circular structure last_node = self.head.prev last_node.next = new_node new_node.prev = last_node new_node.next = self.head self.head.prev = new_node def prepend(self, data): """ Add a new node with the given data at the beginning of the list. """ new_node = Node(data) if self.is_empty(): # If the list is empty, set the new node as the head self.head = new_node else: # If the list is not empty, update the references to maintain the circular structure last_node = self.head.prev new_node.next = self.head new_node.prev = last_node last_node.next = new_node self.head.prev = new_node self.head = new_node def insert_after(self, data, after_data): """ Insert a new node with the given data after a specified value in the list. """ if self.is_empty(): raise Exception("List is empty") current = self.head while current.data != after_data: current = current.next if current == self.head: raise Exception(f"{after_data} not found in the list") new_node = Node(data) new_node.next = current.next new_node.prev = current current.next.prev = new_node current.next = new_node def remove(self, data): """ Remove the node with the specified data from the list. """ if self.is_empty(): raise Exception("List is empty") current = self.head while current.data != data: current = current.next if current == self.head: raise Exception(f"{data} not found in the list") current.prev.next = current.next current.next.prev = current.prev if current == self.head: self.head = current.next def display(self): """ Display the elements of the circular doubly linked list. """ if self.is_empty(): print("List is empty") return current = self.head while True: print(current.data, end=" ") current = current.next if current == self.head: break print()
Example
Now that we have our CircularDoublyLinkedList class let’s test it with some examples to see how it performs.
# Usage example cdll = CircularDoublyLinkedList() cdll.append(1) cdll.append(2) cdll.append(3) cdll.prepend(0) cdll.insert_after(2.5, 2) cdll.remove(1) cdll.display() # 0 2 2.5 3
In this example, we created a circular doubly linked list, appended elements, prepended an element, inserted an element after element 2, and removed an element. The display method is used to print the contents of the list.
And we’re done! You now have a basic implementation of a circular doubly linked list in Python. You can extend the CircularDoublyLinkedList class with more functionality as needed for your specific use case.
Video, Further Resources & Summary
Do you need more explanations on how to define a circular doubly linked list in Python? Then you should have a look at the following YouTube video of the Statistics Globe YouTube channel.
The YouTube video will be added soon.
Furthermore, you could have a look at some of the other tutorials on Statistics Globe:
- Are Dictionaries Faster than Lists in Python?
- Check if Linked List is Empty in Python (2 Examples)
- What is a List Node in Python? (2 Examples)
- How to Use Lists in Python (13 Examples)
This post has shown how to create a circular doubly linked list in Python. In case you have further questions, you may leave a comment below.
This page was created in collaboration with Ömer Ekiz. You may have a look at Ömer’s author page to read more about his academic background and the other articles he has written for Statistics Globe.
I’m Joachim Schork. On this website, I provide statistics tutorials as well as code in Python and R programming.
