Python Program to Implement Circular Doubly Linked List

Article Creation Date : 24-Jun-2021 12:30:50 PM
A circular linked list is basically a linear linked list that may be singly or doubly. The only difference is that there is no any NULL value terminating the list. In fact in the list every node points to the next node and last node points to the first node, thus forming a circle.
CODE:
#class Node is for creating a node
class Node:
    def __init__(self, data):
       self.data = data
       self.next = None
       self.prev = None
 
 
class CircularDoublyLinkedList:
    def __init__(self):
        self.first = None
 
    def get_node(self, index):
        current = self.first
        for i in range(index):
            current = current.next
            if current == self.first:
                return None
        return current
 
    def insert_after(self, ref_node, new_node): #This method is for inserting elements into the list when the user selects insert after option
        new_node.prev = ref_node
        new_node.next = ref_node.next
        new_node.next.prev = new_node
        ref_node.next = new_node
 
    def insert_before(self, ref_node, new_node): #This method is for inserting elements into the list when the user selects insert before option
        self.insert_after(ref_node.prev, new_node)
 
    def insert_at_end(self, new_node): #This method is for inserting elements into the list when the user selects insert at end option
        if self.first is None:
            self.first = new_node
            new_node.next = new_node
            new_node.prev = new_node
        else:
            self.insert_after(self.first.prev, new_node)
 
    def insert_at_beg(self, new_node): #This method is for inserting elements into the list when the user selects insert at beginning option
        self.insert_at_end(new_node)
        self.first = new_node
 
    def remove(self, node):	#This method is for deleting elements from the list
        if self.first.next == self.first:
            self.first = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
            if self.first == node:
                self.first = node.next
 
    def display(self):	#This method is for showing elements present in the list
        if self.first is None:
            return
        current = self.first
        while True:
            print(current.data, end = ' ')
            current = current.next
            if current == self.first:
                break
 
 
a_cdllist = CircularDoublyLinkedList()
 
print('Menu')
print('insert <data> after <index>')
print('insert <data> before <index>')
print('insert <data> at beg')
print('insert <data> at end')
print('remove <index>') 
print('quit')
 
while True:
    print('The list: ', end = '')
    a_cdllist.display()
    print()
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
 
    if operation == 'insert':
        data = int(do[1])
        position = do[3].strip().lower()
        new_node = Node(data)
        suboperation = do[2].strip().lower() 
        if suboperation == 'at':
            if position == 'beg':
                a_cdllist.insert_at_beg(new_node)
            elif position == 'end':
                a_cdllist.insert_at_end(new_node)
        else:
            index = int(position)
            ref_node = a_cdllist.get_node(index)
            if ref_node is None:
                print('No such index.')
                continue
            if suboperation == 'after':
                a_cdllist.insert_after(ref_node, new_node)
            elif suboperation == 'before':
                a_cdllist.insert_before(ref_node, new_node)
 
    elif operation == 'remove':
        index = int(do[1])
        node = a_cdllist.get_node(index)
        if node is None:
            print('No such index.')
            continue
        a_cdllist.remove(node)
 
    elif operation == 'quit':
        break


Runtime Test Cases
Case 1:
Menu
insert <data> after <index>
insert <data> before <index>
insert <data> at beg
insert <data> at end
remove <index>
quit
The list: 
What would you like to do? insert 3 at beg
The list: 3 
What would you like to do? insert 5 at end
The list: 3 5 
What would you like to do? insert 1 after 0
The list: 3 1 5 
What would you like to do? insert 2 after 2
The list: 3 1 5 2 
What would you like to do? remove 0
The list: 1 5 2 
What would you like to do? remove 2
The list: 1 5 
What would you like to do? remove 1
The list: 1 
What would you like to do? remove 0
The list: 
What would you like to do? quit
 
Case 2:
Menu
insert <data> after <index>
insert <data> before <index>
insert <data> at beg
insert <data> at end
remove <index>
quit
The list: 
What would you like to do? insert 3 after 0
No such index.
The list: 
What would you like to do? insert 10 at end
The list: 10 
What would you like to do? insert 1 at beg
The list: 1 10 
What would you like to do? insert 5 before 0
The list: 1 10 5 
What would you like to do? insert 9 at beg
The list: 9 1 10 5 
What would you like to do? remove 3
The list: 9 1 10 
What would you like to do? quit
Program Explanation
1. An instance of CircularDoublyLinkedList is created.
2. The user is presented with a menu to perform various operations on the list.
3. The corresponding methods are called to perform each operation.