Python - Circular Doubly Linked List

A circular doubly linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains three sub-elements. A data part that stores the value of the element, the previous part that stores the link to the previous node, and the next part that stores the link to the next node as shown in the below image:

The first node also known as HEAD is always used as a reference to traverse the list. Last element contains link to the first element as next and the first element contains link of the last element as previous. A circular doubly linked can be visualized as a chain of nodes, where every node points to previous and next node.

Implementation of Circular Doubly Linked List

Representation:

In Python, circular doubly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

Create a Circular Doubly Linked List

Let us create a simple circular doubly linked list which contains three data nodes.

# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

# test the code   
# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(10)
#linking with head node
MyList.head = first
#linking next of the node with head
first.next = MyList.head 
#linking prev of the head 
MyList.head.prev = first

#Add second node.
second = Node(20)
#linking with first node
second.prev = first
first.next = second
#linking next of the node with head
second.next = MyList.head 
#linking prev of the head 
MyList.head.prev = second

#Add third node.
third = Node(30)
#linking with second node
third.prev = second
second.next = third
#linking next of the node with head
third.next = MyList.head 
#linking prev of the head 
MyList.head.prev = third

Traverse a Circular Doubly Linked List

A circular doubly linked list can be traversed from any node of the list using a temp node. Keep on moving the temp node to the next one and displaying its content. Stop the traversal, after reaching the starting node.

# node structure
class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class Linked List
class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (True):
        print(temp.data, end=" ")
        temp = temp.next
        if(temp == self.head):
          break
      print()
    else:
      print("The list is empty.")

# test the code    
# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(10)
#linking with head node
MyList.head = first
#linking next of the node with head
first.next = MyList.head 
#linking prev of the head 
MyList.head.prev = first

#Add second node.
second = Node(20)
#linking with first node
second.prev = first
first.next = second
#linking next of the node with head
second.next = MyList.head 
#linking prev of the head 
MyList.head.prev = second

#Add third node.
third = Node(30)
#linking with second node
third.prev = second
second.next = third
#linking next of the node with head
third.next = MyList.head 
#linking prev of the head 
MyList.head.prev = third

#print the content of list 
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30