Python - Reverse the Circular Doubly Linked List

While working with a circular doubly linked list, sometimes it is required to reverse it. Reversing a List produces following result: if the given List is 10->20->30->40->50, after reversing the List the List becomes 50->40->30->20->10.

Reversing a List requires creating three nodes, considering that the list is not empty, which are as follows: tempNode pointing to head, prevNode pointing to head and curNode pointing to next of head. Then make next and previous of prevNode as itself to make the first node as last node of the reversed list. After that, while the curNode is not head adjust links (unlink curNode and link it to the reversed list from front and modify curNode and prevNode to the next element in the list). At last, make the prevNode (last node) as head.

The function reverseList is created for this purpose. It is a 4-step process.

def reverseList(self):
  #1. If head is not null create three nodes
  #   prevNode - pointing to head,
  #   tempNode - pointing to head,
  #   curNode - pointing to next of head
  if(self.head != None):
    prevNode = self.head
    tempNode = self.head
    curNode = self.head.next
    
    #2. assign next and previous of prevNode 
    #   as itself to make the first node as 
    #   last node of the reversed list
    prevNode.next = prevNode
    prevNode.prev = prevNode
    
    while(curNode != self.head):
      #3. While the curNode is not head adjust links 
      #   (unlink curNode and link it to the reversed list 
      #   from front and modify curNode and prevNode) 
      tempNode = curNode.next

      curNode.next = prevNode
      prevNode.prev = curNode
      self.head.next = curNode
      curNode.prev = self.head

      prevNode = curNode
      curNode = tempNode

    #4. Make prevNode (last node) as head
    self.head = prevNode

The below is a complete program that uses above discussed concept to reverse a given circular doubly linked list.

# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class Linked List
class LinkedList:
  def __init__(self):
    self.head = None

  #Add new element at the end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      newNode.next = self.head
      newNode.prev = self.head
      return
    else:
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = newNode
      newNode.next = self.head
      newNode.prev = temp
      self.head.prev = newNode

  #reverse the list
  def reverseList(self):
    if(self.head != None):
      prevNode = self.head
      tempNode = self.head
      curNode = self.head.next
      
      prevNode.next = prevNode
      prevNode.prev = prevNode
      
      while(curNode != self.head):
        tempNode = curNode.next

        curNode.next = prevNode
        prevNode.prev = curNode
        self.head.next = curNode
        curNode.prev = self.head

        prevNode = curNode
        curNode = tempNode

      self.head = prevNode 

  #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                  
MyList = LinkedList()

#Add five elements in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(40)
MyList.push_back(50)

#Display the content of the list.
MyList.PrintList()

#Reversing the list.
MyList.reverseList()
  
#Display the content of the list.
MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 40 50 
The list contains: 50 40 30 20 10