Reverse a Doubly Linked list

In this post, we will see how to reverse a doubly linked list by reversing the reference pointers of nodes using recursion. Also there is a popular way to reverse a linked list using Stack. The basic algorithms are same for both reversal of Singly Linked List and Doubly Linked List. Only the difference is, in case of doubly linked list, we need to reverse the two pointers next and previous.

Example:

     Original Doubly Linked List

After Reversing Doubly Linked List

 

Reverse a Doubly Linked List By Reversing The Reference Pointers:

We will see the algorithm and execution process of reverse a doubly linked list by reversing the reference pointers. We could achieve this by two ways. 1. Traverse through the each node using while loop and reverse the reference pointers. 2. Traverse through the each node using Recursion and reverse the reference pointers. Core logic for both the process is same as we just need to reverse the reference pointers of each nodes.

Algorithm:

  1. Declare 3 node variables , current,  previous, next and initialize current=root node.
  2. Repeat steps 3, 4 and 5 till current != null.
  3. next= next node of current node & previous=previous node of current node.
  4. reverse the both pointers next & previous. next node of current node =previous & previous node of current node =next.
  5. assign current = previous node of current
  6. At last, set the root node as previous node of previous means root node will be the last node.

Execution process:

Reverse a Doubly Linked List Using Stack:

Now, we will see the algorithm and execution process of reverse a doubly linked list using stack. First, push all the nodes of doubly linked list starting from root node to stack and after pushing all the nodes of the doubly linked list, root of the doubly linked list will be at very bottom and top will have the end node of doubly linked list. Basically, Stack reverse the order of insertion. Now, pop the nodes from top of the stack and keep adding to the root node to form doubly linked list. Similar algorithm and execution process are written for Singly Linked List . Please refer and try to implement the similar logic for doubly linked list. Please leave your comments in case of any issue/discussions.

Below is the code written for reversal of doubly linked list using recusion.

Testing:

 

 

Output:

*************************************************************************************************************

DELL Latitude 5647 added.
Mac Book added.
Mac Book Pro added.
HP Elitebook added.

Original Doubly Linked List : [DoublyNode [data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]],DoublyNode [data=Item [itemId=102, itemName=Mac Book, price=1000.0]],DoublyNode [data=Item [itemId=103, itemName=Mac Book Pro, price=2000.0]],DoublyNode [data=Item [itemId=104, itemName=HP Elitebook, price=700.0]]]

Doubly Linked List after reversal: [DoublyNode [data=Item [itemId=104, itemName=HP Elitebook, price=700.0]],DoublyNode [data=Item [itemId=103, itemName=Mac Book Pro, price=2000.0]],DoublyNode [data=Item [itemId=102, itemName=Mac Book, price=1000.0]],DoublyNode [data=Item [itemId=101, itemName=DELL Latitude 5647, price=300.0]]]

*************************************************************************************************************

 

Hope you like this post. Please leave your comments/suggestions.

 

 

You may like:

Introduction of Doubly Linked List(DLL)

Delete Operation in Doubly Linked List

Reverse a Doubly Linked List

Iterator For Doubly Linked List

 

Top