Python program to create a Circular Linked List of n nodes and display it in reverse order

In this tutorial, we will learn about the algorithm for creating as well as reversing a circular linked list along with its implementation in Python. Here, we need to create a circular linked list, then traverse the list in the reverse order and print the nodes.

What is Circular Linked List?

Circular Linked List is a little more complicated linked data structure. In the circular linked list, we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements point to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.

As the output, we are required to get the list of reverse circular linked list elements.

Look at the given example to understand the working with input and output.

Input:

circular linked list: 4 5 3 6 9 7 8

Output:

original circular linked list:4 5 3 6 9 7 8

reversed circular linked list:8 7 9 6 3 5 4

Input:

circular linked list: 10 2 56

Output:

original circular linked list:10 2 56

reversed circular linked list:56 2 10

Algorithm

Step1: The first element in the array is assumed to be sorted. Take the second element and store it separately in "k". Compare "k" with the first element. If the first element is greater than "k", then "k" is placed in front of the first element.

Step2: Now, the first two elements are sorted. Take the third element and compare it with the elements on its left. Placed it just behind the element smaller than it. If there is no element smaller than it, then place it at the beginning of the array.

Step3: Similarly, place every unsorted element at its correct position.

Step4: The above process goes on until the last element.

Python Program to Create a Circular Linked List of n Nodes and Display it in Reverse Order

#Represents the node of list.    
class Node:    
    def __init__(self,data):    
      self.data = data;    
      self.next = None;    
     
class CreateList:    
    #Declaring head and tail pointer as null.    
    def __init__(self):    
      self.head = Node(None);    
      self.tail = Node(None);    
      self.head.next = self.tail;    
      self.tail.next = self.head;    
          
    #This function will add the new node at the end of the list.    
    def add(self,data):    
      newNode = Node(data);    
      #Checks if the list is empty.    
      if self.head.data is None:    
        #If list is empty, both head and tail would point to new node.    
        self.head = newNode;    
        self.tail = newNode;    
        newNode.next = self.head;    
      else:    
        #tail will point to new node.    
        self.tail.next = newNode;    
        #New node will become new tail.    
        self.tail = newNode;    
        #Since, it is circular linked list tail will point to head.    
        self.tail.next = self.head;    
     
    #Displays all the nodes in the list    
    def display(self):    
        current = self.head;    
        if self.head is None:    
          print("List is empty");    
          return;    
        else:    
            #Prints each node by incrementing pointer.    
            print(current.data),    
            while(current.next != self.head):    
                current = current.next;    
                print(current.data),    
            
    #Reverse the order of the nodes present in the list.    
    def reverse(self, current):    
        #Checks if the next node is head, if yes then prints it.    
        if(current.next == self.head):    
            print(current.data),    
            return;    
        #Recursively calls the reverse function    
        self.reverse(current.next);    
        print(current.data),    
        
        
class CircularLinkedList:    
    cl = CreateList();    
    #Adds data to the list    
    cl.add(1);    
    cl.add(2);    
    cl.add(3);    
    cl.add(4);    
    cl.add(5);    
    cl.add(6);    
    print("Original List: ");    
    cl.display();    
    print("\nReversed List: ");    
    #Print reversed list    
    cl.reverse(cl.head); 

Original List: 1 2 3 4 5 6
Reversed List: 6 5 4 3 2 1

Conclusion

We have concluded the reversing circular linked list in this tutorial. Also, the implementation part has been shown to produce the program's desired output.