Circular Doubly Linked Lists in Python

A Circular Doubly Linked List is an ordered data structure implemented using Doubly Linked Lists, where the last node of points at the first header node and vice versa.

Circular Doubly Linked Lists are similar to Douby Linked Lists. Both are dynamic data structures. Any data type can be stored in both the data structures.

However, the only difference lies in the fact that in Circular Doubly Linked Lists, the last node of the Linked List points at the first header node and vice versa, thus giving it a circular form.

A node of this kind of a Linked Lists consists of three fields; the data field, and the left and the right link fields. The two link fields hold the links to the left-hand and the right-hand side nodes.
circular-doubly-linked-list1

The Circular Doubly Linked List class consists of two pointers; the head 1 and the head 2 pointers. They hold the left-most and the right-most nodes of the Linked List.

Characteristics of Circular Doubly Linked Lists

  • Ordered - Elements in a Circular Singly Linked List follow a certain order
  • Mutable - Elements can be added/ deleted/ modified
  • Dynamic - Length of the Circular Linked List is changeable
  • Any data type can be stored
  • The previous element to the current pointer can be accessed
  • Linked List can be reversed due to dual pointers

Implementing the Circular Doubly Linked List

Implementation of a Circular Doubly Linked List is similar to that of Doubly Linked List, except of course while traversing or searching for elements in the Linked List.

During forward or reverse traversing or searching such a Linked List, the point is used to traverse all the elements until it reaches the starting element in a circular manner.

The Python 3 code to implement a Circular Doubly Linked List, and the methods to manipulate it as follows.

  1. Defining the Node class which holds the data and the two link fields
    class Node:
        def __init__(self, val):
            self.value = val
            self.left = None
            self.right = None​
  2. Defining the Circular Doubly Linked List class
    class CDLL:​
  3. Initializing the two header pointers
        def __init__(self):
            self.head1 = None
            self.head2 = None​
  4. Defining the add() method which is used to add elements to the Circular Doubly Linked List
    def add(self, val):​
    1. Checking whether or not the Linked List is empty and creating it if it is
              if self.empty() is True:
                  self.head1 = Node(val)
                  self.head2 = self.head1
                  self.head2.right = self.head1
                  self.head1.left = self.head2
                  print("Head value created")
                  return​
    2. Adding a Node at the beginning of the Linked List
              if opt == 1:
                  a = Node(val)
                  a.right = self.head1
                  self.head1.left = a
                  self.head2.right = a
                  a.left = self.head2
                  self.head1 = self.head1.left​
    3. Adding a Node to the end of the Linked List
              elif opt == 2:
                  a = Node(val)
                  self.head2.right = a
                  a.left = self.head2
                  a.right = self.head1
                  self.head1.left = a
                  self.head2 = self.head2.right​
    4. Adding a Node before a given Node
              elif opt == 3:
                  pos = int(input("Enter the position ::"))
                  i = 1
                  n = self.head1.right
                  flag = 0
                  while n is not self.head1:
                      if i == pos:
                          flag = 1
                          break
                      n = n.right
                      i = i + 1
                  if flag == 1:
                      a = Node(val)
                      a.right = n
                      n.left.right = a
                      a.left = n.left
                      n.left = a
                  else:
                      print("Position not found")​
    5. Adding a Node after a given Node
              elif opt == 4:
                  pos = int(input("Enter the position ::"))
                  i = 0
                  n = self.head1
                  flag = 0
                  while n.right is not self.head1:
                      if i == pos:
                          flag = 1
                          break
                      n = n.right
                      i = i + 1
                  if flag == 1:
                      a = Node(val)
                      n.right.left = a
                      a.right = n.right
                      a.left = n
                      n.right = a
                  else:
                      print("Position not found")​
  5. Defining the delete() method which is used to delete elements from a Circular Doubly Linked List
    def delete(self):​
    1. To check whether or not a given Linked List is empty or delete the last element in the Linked List
              if self.empty() is True:
                  print("Linked List empty")
                  return
              elif self.head1.right is self.head2:
                  self.head1 = None
                  self.head2 = None
                  return​
    2. Deleting the first Node of the Linked List
              if opt == 1:
                  self.head1 = self.head1.right
                  self.head1.left = self.head2
                  self.head2.right = self.head1​
    3. Deleting the end Node of the Linked List
              elif opt == 2:
                  self.head2 = self.head2.left
                  self.head2.right = self.head1
                  self.head1.left = self.head2​
    4. Deleting a Node-based on position or based on the value
              else:
                  op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                  if op == 1:
                      pos = int(input("Enter the position ::"))
                      i = 1
                      n = self.head1.right
                      flag = 0
                      while n.right is not self.head1:
                          if i == pos:
                              flag = 1
                              break
                          i = i + 1
                          n = n.right
                      if flag == 1:
                          n.left.right = n.right
                          n.right.left = n.left
                      else:
                          print("Position not found")
                          return
                  else:
                      val = int(input("Enter the value you want to delete ::"))
                      n = self.head1
                      flag = 0
                      while n.right is not self.head1:
                          if n.value == val:
                              flag = 1
                              break
                          n = n.right
                      if flag == 1:
                          n.left.right = n.right
                          n.right.left = n.left
                      else:
                          print("Value not found")
                          return​
  6. Defining the clear() method which is used to empty the Circular Doubly Linked List
        def clear(self):
            self.head1 = None
            self.head2 = None
            print("Linked List cleared")​
  7. Defining the empty() method which is used to check whether or not the Circular Doubly Linked List is empty
        def empty(self):
            if self.head1 is None:
                return True
            else:
                return False​
  8. Defining the display() method which is used to present the Circular Doubly Linked List in a user-comprehendible format with the ability to choose the direction of the display
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head1.right is self.head1:
                print("LINKED LIST")
                print(self.head1.value, "HEAD 1 & 2")
                print("Linked List ends")
                return
            o = int(input("Enter 1 to print in forward direction\nEnter 2 to print in backward direction ::"))
            print("LINKED LIST")
            if o == 1:
                print(self.head1.value, " <== HEAD 1")
                n = self.head1.right
                while n is not self.head2:
                    print(n.value)
                    n = n.right
                print(self.head2.value, " <== HEAD 2")
                print("Linked List ends")
            elif o == 2:
                print(self.head2.value, " <== HEAD 2")
                n = self.head2.left
                while n is not self.head1:
                    print(n.value)
                    n = n.left
                print(self.head1.value, " <== HEAD 1")
                print("Linked List ends")
            else:
                print("Wrong option")​
  9. After assembling the program, creating an instance, and defining a menu-driven program to manipulate the Circular Doubly Linked List

    class Node:
        def __init__(self, val):
            self.value = val
            self.left = None
            self.right = None
    
    class CDLL:
        def __init__(self):
            self.head1 = None
            self.head2 = None
    
        def add(self, val):
            if self.empty() is True:
                self.head1 = Node(val)
                self.head2 = self.head1
                self.head2.right = self.head1
                self.head1.left = self.head2
                print("Head value created")
                return
            opt = int(input(
                "Enter 1 to add a Node at the beginning\nEnter 2 to add a Node at the end\nEnter 3 to add a Node before "
                " a node\nEnter 4 to add a Node after a node ::"))
            if opt == 1:
                a = Node(val)
                a.right = self.head1
                self.head1.left = a
                self.head2.right = a
                a.left = self.head2
                self.head1 = self.head1.left
            elif opt == 2:
                a = Node(val)
                self.head2.right = a
                a.left = self.head2
                a.right = self.head1
                self.head1.left = a
                self.head2 = self.head2.right
            elif opt == 3:
                pos = int(input("Enter the position ::"))
                i = 1
                n = self.head1.right
                flag = 0
                while n is not self.head1:
                    if i == pos:
                        flag = 1
                        break
                    n = n.right
                    i = i + 1
                if flag == 1:
                    a = Node(val)
                    a.right = n
                    n.left.right = a
                    a.left = n.left
                    n.left = a
                else:
                    print("Position not found")
            elif opt == 4:
                pos = int(input("Enter the position ::"))
                i = 0
                n = self.head1
                flag = 0
                while n.right is not self.head1:
                    if i == pos:
                        flag = 1
                        break
                    n = n.right
                    i = i + 1
                if flag == 1:
                    a = Node(val)
                    n.right.left = a
                    a.right = n.right
                    a.left = n
                    n.right = a
                else:
                    print("Position not found")
            else:
                print("Wrong option")
    
        def delete(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head1.right is self.head2:
                self.head1 = None
                self.head2 = None
                return
            opt = int(input("Enter 1 to delete the beginning element\nEnter 2 to delete the last element\nEnter 3 to "
                            "delete elements in between ::"))
            if opt == 1:
                self.head1 = self.head1.right
                self.head1.left = self.head2
                self.head2.right = self.head1
            elif opt == 2:
                self.head2 = self.head2.left
                self.head2.right = self.head1
                self.head1.left = self.head2
            else:
                op = int(input("Enter 1 to delete by position\nEnter 2 to delete by value ::"))
                if op == 1:
                    pos = int(input("Enter the position ::"))
                    i = 1
                    n = self.head1.right
                    flag = 0
                    while n.right is not self.head1:
                        if i == pos:
                            flag = 1
                            break
                        i = i + 1
                        n = n.right
                    if flag == 1:
                        n.left.right = n.right
                        n.right.left = n.left
                    else:
                        print("Position not found")
                        return
                else:
                    val = int(input("Enter the value you want to delete ::"))
                    n = self.head1
                    flag = 0
                    while n.right is not self.head1:
                        if n.value == val:
                            flag = 1
                            break
                        n = n.right
                    if flag == 1:
                        n.left.right = n.right
                        n.right.left = n.left
                    else:
                        print("Value not found")
                        return
    
        def clear(self):
            self.head1 = None
            self.head2 = None
            print("Linked List cleared")
    
        def empty(self):
            if self.head1 is None:
                return True
            else:
                return False
    
        def display(self):
            if self.empty() is True:
                print("Linked List empty")
                return
            elif self.head1.right is self.head1:
                print("LINKED LIST")
                print(self.head1.value, "HEAD 1 & 2")
                print("Linked List ends")
                return
            o = int(input("Enter 1 to print in forward direction\nEnter 2 to print in backward direction ::"))
            print("LINKED LIST")
            if o == 1:
                print(self.head1.value, " <== HEAD 1")
                n = self.head1.right
                while n is not self.head2:
                    print(n.value)
                    n = n.right
                print(self.head2.value, " <== HEAD 2")
                print("Linked List ends")
            elif o == 2:
                print(self.head2.value, " <== HEAD 2")
                n = self.head2.left
                while n is not self.head1:
                    print(n.value)
                    n = n.left
                print(self.head1.value, " <== HEAD 1")
                print("Linked List ends")
            else:
                print("Wrong option")
    
    LL = CDLL()
    while True:
        option = int(input("Enter 1 to add an element\nEnter 2 to delete an element\nEnter 3 to clear the Linked "
                           "List\nEnter 4 to display the Linked List\nEnter 5 to exit ::"))
        if option == 1:
            value = int(input("Enter the value you want to add ::"))
            LL.add(value)
            continue
        elif option == 2:
            LL.delete()
            continue
        elif option == 3:
            LL.clear()
            continue
        elif option == 4:
            LL.display()
            continue
        elif option == 5:
            print("Goodbye")
            break
        elif option == 6:
            print(LL.empty())
        else:
            print("Wrong option")

    output

    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::5
    Head value created
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::6
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::7
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::8
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::3
    Enter the position ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::9
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::4
    Enter the position ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Enter 1 to print in forward direction
    Enter 2 to print in backward direction ::1
    LINKED LIST
    6  <== HEAD 1
    8
    5
    9
    7  <== HEAD 2
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::2
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Enter 1 to print in forward direction
    Enter 2 to print in backward direction ::2
    LINKED LIST
    9  <== HEAD 2
    5
    8  <== HEAD 1
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::3
    Enter 1 to delete by position
    Enter 2 to delete by value ::1
    Enter the position ::1
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Enter 1 to print in forward direction
    Enter 2 to print in backward direction ::1
    LINKED LIST
    8  <== HEAD 1
    9  <== HEAD 2
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::1
    Enter the value you want to add ::10
    Enter 1 to add a Node at the beginning
    Enter 2 to add a Node at the end
    Enter 3 to add a Node before  a node
    Enter 4 to add a Node after a node ::4
    Enter the position ::0
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::2
    Enter 1 to delete the beginning element
    Enter 2 to delete the last element
    Enter 3 to delete elements in between ::3
    Enter 1 to delete by position
    Enter 2 to delete by value ::2
    Enter the value you want to delete ::10
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Enter 1 to print in forward direction
    Enter 2 to print in backward direction ::2
    LINKED LIST
    9  <== HEAD 2
    8  <== HEAD 1
    Linked List ends
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::3
    Linked List cleared
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::4
    Linked List empty
    Enter 1 to add an element
    Enter 2 to delete an element
    Enter 3 to clear the Linked List
    Enter 4 to display the Linked List
    Enter 5 to exit ::5
    Goodbye

Advantages and Disadvantages of Circular Doubly Linked Lists

Advantages
  • Reversing the Linked List is easy
  • Dynamic memory allocation is enabled
  • Deletion of nodes is easy
Disadvantages
  • Not easy to reverse the Linked List
  • The danger of falling into an infinite loop
  • Takes up extra memory to store extra link fields and pointers
  • Handling of pointers should be with care in anticipation of the loss of data

Applications of Circular Doubly Linked Lists

    • Managing media applications manager
    • Managing online shopping carts
    • Used in Fibonacci Heaps
    • Used to implement queues
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions