How to Reverse a Doubly Linked List in Java

In this post we’ll see a Java program to reverse a doubly linked list.

Reversing a doubly linked list

In a doubly Linked list each node stores reference to both next and previous nodes. For reversing a doubly linked list, for each node previous and next references should be swapped.

Once the doubly linked list is reversed head and tail references should also be adjusted accordingly.

Java program to reverse a doubly linked list can be written using both-

Iterative approach. See example.
Recursive approach. See example.

Java program to reverse a doubly linked list – Iterative

public class ReverseDLL {
 private Node head;
 private Node tail;
 static class Node{
  //data
  int i;
  // next node in the list
  Node next;
  // previous node in the list
  Node prev;
  Node(int i){
   this.i = i;
  }
  public void displayData(){
   System.out.print(i + " ");
  }
 }
 // constructor
 public ReverseDLL(){
  this.head = null;
  this.tail = null;
 }
 
 public boolean isEmpty(){
  return head == null;
 }
 
 public void insertFirst(int i){
  //Create a new node
  Node newNode = new Node(i);
  // if first insertion tail should
  // also point to this node
  if(isEmpty()){
   tail = newNode;
  }else{
   head.prev = newNode;
  }
  newNode.next = head;
  head = newNode;
 }
 
 // Method for forward traversal
 public void displayForward(){
  System.out.println("Forward display");
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
  System.out.println("");
 }
 // Method to traverse and display all nodes
 public void displayBackward(){
  System.out.println("Backward display");
  Node current = tail;
  while(current != null){
   current.displayData();
   current = current.prev;
  }
  System.out.println("");
 }
 // Method for reversing doubly linked list
 public void reverseList(){
  Node previous = null;
  //change reference head becomes tail in reversal
  tail = head;
  Node current = head;
  while(current != null){
   // swap prev and next for the current node
   previous = current.prev;
   current.prev = current.next;
   current.next = previous;
   // to move to next node current.prev has to be called
   // as that has reference to next node now
   current = current.prev;
  }
  if(previous != null){
   head = previous.prev;
  }
 }
 public static void main(String[] args) {
  ReverseDLL list = new ReverseDLL();
  list.insertFirst(4);
  list.insertFirst(3);
  list.insertFirst(2);
  list.insertFirst(1);
  list.displayForward();
  
  list.reverseList();
  list.displayForward();
  list.displayBackward();
 }
}

Output

Forward display
1 2 3 4 
Forward display
4 3 2 1 
Backward display
1 2 3 4

Java program to reverse a doubly linked list – Recursive

In the recursive method for reversing a doubly linked linked list method is called passing the first node then the method is recursively called by passing the next node (node.next).

public class ReverseDLL {
 private Node head;
 private Node tail;
 static class Node{
  //data
  int i;
  // next node in the list
  Node next;
  // previous node in the list
  Node prev;
  Node(int i){
   this.i = i;
  }
  public void displayData(){
   System.out.print(i + " ");
  }
 }
 // constructor
 public ReverseDLL(){
  this.head = null;
  this.tail = null;
 }
 
 public boolean isEmpty(){
  return head == null;
 }
 
 public void insertFirst(int i){
  //Create a new node
  Node newNode = new Node(i);
  // if first insertion tail should
  // also point to this node
  if(isEmpty()){
   tail = newNode;
  }else{
   head.prev = newNode;
  }
  newNode.next = head;
  head = newNode;
 }
 
 // Method for forward traversal
 public void displayForward(){
  System.out.println("Forward display");
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
  System.out.println("");
 }
 // Method to traverse and display all nodes
 public void displayBackward(){
  System.out.println("Backward display");
  Node current = tail;
  while(current != null){
   current.displayData();
   current = current.prev;
  }
  System.out.println("");
 }

  public Node reverseListRec(Node current){
    if (current == null) {
      return current;
    }
    if (current.next == null) {
    current.prev = null;
      return current;
    }
    Node node = reverseListRec(current.next);
    current.next.next = current;    
    current.prev = current.next;
    current.next = null;
    return node;
  }
 public static void main(String[] args) {
  ReverseDLL list = new ReverseDLL();
  list.insertFirst(4);
  list.insertFirst(3);
  list.insertFirst(2);
  list.insertFirst(1);
  list.displayForward();
  // change tail reference before calling reverse method
  list.tail = list.head;
  Node node = list.reverseListRec(list.head);
  // change head to point to returned node
  list.head = node;
  //list.reverseList();
  list.displayForward();
  list.displayBackward();
 }
}

Output

Forward display
1 2 3 4 
Forward display
4 3 2 1 
Backward display
1 2 3 4

In the recursive method for reversing doubly linked list reference is reversed in the following lines.

current.next.next = current;
current.prev = current.next;

Following image tries to clarify what this line does.

That's all for this topic How to Reverse a Doubly Linked List in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Wednesday, April 20, 2022