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

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