Python - Reverse the Doubly Linked List

While working with a 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 the prevNode as null to make the first node as last node of the reversed list. After that, while the curNode is not null 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 the 
    #   prevNode as null to make the first 
    #   node as last node of the reversed list
    prevNode.next = None
    prevNode.prev = None
    
    while(curNode != None):
      #3. While the curNode is not null 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
      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 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
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode
      newNode.prev = temp

  #reverse the list
  def reverseList(self):
    if(self.head != None):
      prevNode = self.head
      tempNode = self.head
      curNode = self.head.next
      
      prevNode.next = None
      prevNode.prev = None
      
      while(curNode != None):
        tempNode = curNode.next
        curNode.next = prevNode
        prevNode.prev = curNode
        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 (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      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