Reverse a Doubly Linked List

Q: How do you reverse a doubly linked list?

Swap the prev and next references of every node. The last node processed becomes the new head: It runs in O(n) time and O(1) space.

Q: Why do we move to current.prev instead of current.next after swapping?

After the swap, current.prev holds what used to be current.next. Moving to current.prev therefore continues forward through the original list.

Q: If the list keeps head and tail references, what else must change?

Swap the head and tail references after reversing the links, because the old tail is now the first node and the old head is now the last.

Q: Write a recursive Java method to reverse a doubly linked list.

Java example: static Node reverse(Node node) { if (node == null) { return null; } Node temp = node.next; node.next = node.prev; node.prev = temp; if (node.prev == null) { return node; // this was the last node: new head } return reverse(node.prev); }

Q: What are the edge cases when reversing?

An empty list returns null. A one-node list stays the same. The caller must store the returned new head.

Reverse a Doubly Linked List

In this tutorial we are going to talk about how to reverse a doubly linked list using the Java program.

In order to reverse a doubly linked list, we need to iterate through the list while swapping the next and previous pointers of each node. Once we reach the end of the list, the head pointer will point to the last node of the list.

Let's understand the reverse of a doubly linked list with the given example below:

Example: Reverse a Doubly Linked List in Java

Class: Node

Node.java

public class Node {
  int data;   // Data stored in the node
  Node prev;  // Reference to the next node in the list
  Node next;  // Reference to the previous node in the list

  // Constructor to initialize a new node with data
  Node(int new_data) {
    data = new_data;
    prev = null;
    next = null;
  }
}

Class: ReverseDoublyLinkedList

ReverseDoublyLinkedList.java

// Java program to reverse a doubly linked list using recursion approach
public class ReverseDoublyLinkedList {
  static Node head;

  // Method to insert a node in doubly linked list
  static void insertNode(int data) {
    Node newNode = new Node(data);
    Node last = head;
    if (head == null) {
      head = newNode;
      return;
    }
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
    newNode.prev = last;
  }

  // Method to reverse a doubly linked list using recursive approach
  static Node reverseList(Node node) {

    // If node is null that means list is empty
    if (node == null)
      return null;

    // Swap the next and previous pointers
    Node temp = node.prev;
    node.prev = node.next;
    node.next = temp;

    // If prev is null after swap, this is the new head
    if (node.prev == null) {
      return node;
    }

    // Recurse for the next node
    return reverseList(node.prev);
  }

  // Method to print a list
  static void printList(Node node) {
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Insert node into a doubly linked list
    insertNode(10);
    insertNode(20);
    insertNode(30);
    insertNode(40);
    insertNode(50);

    System.out.println("Original doubly linked list:");
    printList(head);

    // Reverse the doubly linked list
    head = reverseList(head);

    System.out.println("Reversed doubly linked list:");
    printList(head);
  }
}

Output

Original doubly linked list:
10 20 30 40 50
Reversed doubly linked list:
50 40 30 20 10

Time Complexity: O(n)

Auxiliary Space: O(n)

here n means the total number of nodes in a doubly linked list.

Frequently Asked Questions (FAQ)

Q1. How do you reverse a doubly linked list?

Swap the prev and next references of every node. The last node processed becomes the new head:

ReverseDoubly.java

static Node reverse(Node head) {
    Node current = head;
    Node newHead = head;
    while (current != null) {
        Node temp = current.prev;
        current.prev = current.next;
        current.next = temp;
        newHead = current;
        current = current.prev;        // prev now holds the old next
    }
    return newHead;
}

It runs in O(n) time and O(1) space.

Q2. Why do we move to current.prev instead of current.next after swapping?

After the swap, current.prev holds what used to be current.next. Moving to current.prev therefore continues forward through the original list.

Q3. How is reversing a doubly linked list different from reversing a singly linked list?

In a singly linked list you must track the previous node yourself and rewrite one link per node. In a doubly linked list each node already knows both neighbours, so you only swap its two links. Both are O(n).

Q4. If the list keeps head and tail references, what else must change?

Swap the head and tail references after reversing the links, because the old tail is now the first node and the old head is now the last.

Q5. Write a recursive Java method to reverse a doubly linked list.

ReverseRecursive.java

static Node reverse(Node node) {
    if (node == null) {
        return null;
    }
    Node temp = node.next;
    node.next = node.prev;
    node.prev = temp;
    if (node.prev == null) {
        return node;                  // this was the last node: new head
    }
    return reverse(node.prev);
}

Q6. Can you reverse a doubly linked list by swapping data instead of links?

Yes. Use one pointer from the head and one from the tail and swap their values until they meet:

ReverseBySwappingData.java

static void reverseData(Node head, Node tail) {
    Node left = head, right = tail;
    while (left != right && left.prev != right) {
        int temp = left.data;
        left.data = right.data;
        right.data = temp;
        left = left.next;
        right = right.prev;
    }
}

This is simple, but swapping links is preferred when nodes hold large objects or are referenced elsewhere.

Q7. What are the edge cases when reversing?

An empty list returns null.
A one-node list stays the same.
The caller must store the returned new head.

Q8. How do you verify that the reversal worked?

Print the list forward from the new head and backward from the new tail. The forward output should be the old backward output. Also check that the new head's prev is null.

Q9. Do you need to reverse a doubly linked list to print it backward?

No. You can print it backward without changing it by starting at the tail and following prev. Reverse the list only when its actual order must change.

Q10. What is the time and space complexity of each approach?

Swapping links iteratively: O(n) time, O(1) space.
Recursive reversal: O(n) time, O(n) stack space.
Swapping data with two pointers: O(n) time, O(1) space.

Was this tutorial helpful?

Help Us Improve

Reverse a Doubly Linked List

Example: Reverse a Doubly Linked List in Java

Class: Node

Class: ReverseDoublyLinkedList

Frequently Asked Questions (FAQ)