Reverse a Doubly Linked List in DSA Java - Deep Dive

Overview - Reverse a Doubly Linked List

What is it?

A doubly linked list is a chain of nodes where each node points to both its previous and next nodes. Reversing this list means changing the direction so the last node becomes the first, and the first becomes the last. This operation swaps the previous and next links for every node. It helps us traverse the list backward or change the order of elements efficiently.

Why it matters

Without the ability to reverse a doubly linked list, we would struggle to efficiently change the order of data or navigate backward through the list. This limits flexibility in many applications like undo features, navigation history, or playlist management. Reversing the list in place saves memory and time compared to creating a new reversed copy.

Where it fits

Before learning this, you should understand what a doubly linked list is and how to traverse it. After mastering reversal, you can explore more complex list operations like sorting, merging, or implementing advanced data structures like deques or LRU caches.

Mental Model

Core Idea

Reversing a doubly linked list means swapping each node's previous and next pointers so the list's direction flips end-to-end.

Think of it like...

Imagine a two-way street where cars can drive forward or backward. Reversing the list is like flipping the street signs so cars must drive in the opposite direction on the same road.

Original List:
null <- [Node1] <-> [Node2] <-> [Node3] -> null

After Reversal:
null <- [Node3] <-> [Node2] <-> [Node1] -> null

Build-Up - 6 Steps

1

Foundation

Understanding Doubly Linked List Structure

Concept: Learn how each node in a doubly linked list connects to both previous and next nodes.

A doubly linked list node has three parts: data, a pointer to the previous node, and a pointer to the next node. The first node's previous pointer is null, and the last node's next pointer is null. This allows traversal in both directions.

Result

You can move forward and backward through the list by following next and previous pointers.

Understanding the two-way connections is essential because reversing the list means swapping these pointers for every node.

2

Foundation

Traversing a Doubly Linked List

Concept: Learn how to move through the list from start to end and end to start.

Start at the head node and follow the next pointers to reach the end. To go backward, start at the tail and follow previous pointers back to the head.

Result

You can access all nodes in order and reverse order without extra memory.

Knowing traversal directions helps visualize what changes when the list is reversed.

3

Intermediate

Swapping Pointers in Each Node

🤔Before reading on: Do you think reversing means swapping data values or swapping pointers? Commit to your answer.

Concept: Reversing the list involves swapping the previous and next pointers in each node, not the data inside nodes.

For each node, temporarily store the previous pointer, then set previous to next, and next to the stored previous. Move to the next node using the original next pointer before swapping.

Result

Each node's direction flips, so what was next becomes previous and vice versa.

Understanding pointer swapping avoids unnecessary data movement and keeps the operation efficient.

4

Intermediate

Updating the Head After Reversal

🤔Before reading on: After swapping pointers, do you think the head stays the same or changes? Commit to your answer.

Concept: After reversing pointers, the original tail becomes the new head of the list.

While swapping pointers, keep track of the last processed node. After the loop ends, set the list's head pointer to this node.

Result

The list's entry point updates to the new first node, allowing correct traversal from start.

Recognizing the head must update prevents traversal errors after reversal.

5

Advanced

In-Place Reversal Algorithm in Java

🤔Before reading on: Do you think reversing requires extra memory or can be done in-place? Commit to your answer.

Concept: Implement the reversal by swapping pointers in-place without creating new nodes or lists.

```java class Node { int data; Node prev, next; Node(int d) { data = d; prev = next = null; } } class DoublyLinkedList { Node head; void reverse() { Node current = head; Node temp = null; while (current != null) { temp = current.prev; current.prev = current.next; current.next = temp; current = current.prev; // move to next node in original order } if (temp != null) { head = temp.prev; // update head to new first node } } void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " <-> "); temp = temp.next; } System.out.println("null"); } } public class Main { public static void main(String[] args) { DoublyLinkedList dll = new DoublyLinkedList(); dll.head = new Node(1); Node second = new Node(2); Node third = new Node(3); dll.head.next = second; second.prev = dll.head; second.next = third; third.prev = second; System.out.print("Original List: "); dll.printList(); dll.reverse(); System.out.print("Reversed List: "); dll.printList(); } } ```

Result

Original List: 1 <-> 2 <-> 3 <-> null Reversed List: 3 <-> 2 <-> 1 <-> null

Knowing how to reverse in-place saves memory and is the most efficient way to reverse a doubly linked list.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think reversing an empty or single-node list changes it? Commit to your answer.

Concept: Consider empty lists, single-node lists, and performance implications of reversal.

If the list is empty or has one node, reversal does nothing. The algorithm naturally handles these cases without extra checks. The reversal runs in O(n) time, touching each node once, and uses O(1) extra space.

Result

The reversal is safe and efficient for all list sizes, including edge cases.

Understanding edge cases prevents bugs and ensures robust code in production.

Under the Hood

Each node stores two pointers: prev and next. Reversing swaps these pointers for every node. Internally, the algorithm iterates through the list, swapping pointers and moving forward using the original next pointer (which becomes prev after swapping). Finally, the head pointer updates to the last processed node, which is the new start.

Why designed this way?

This design avoids creating new nodes or lists, saving memory and time. Swapping pointers in-place leverages the doubly linked list's bidirectional nature. Alternatives like copying data or rebuilding the list are slower and use more memory.

Start:
head -> [Node1] <-> [Node2] <-> [Node3] -> null

Step 1 (Node1): swap prev and next
[Node1] prev=null, next=[Node2] becomes prev=[Node2], next=null
Move to original next ([Node2])

Step 2 (Node2): swap prev and next
[Node2] prev=[Node1], next=[Node3] becomes prev=[Node3], next=[Node1]
Move to original next ([Node3])

Step 3 (Node3): swap prev and next
[Node3] prev=[Node2], next=null becomes prev=null, next=[Node2]
Move to original next (null)

Update head to Node3

Result:
head -> [Node3] <-> [Node2] <-> [Node1] -> null

Myth Busters - 4 Common Misconceptions

Quick: Does reversing a doubly linked list mean swapping the data inside nodes? Commit yes or no.

Common Belief: Reversing means swapping the data values inside the nodes to reorder the list.

Reality: Reversing swaps the pointers (prev and next) in each node, not the data itself.

Why it matters: Swapping data is inefficient and unnecessary; it can cause errors if data is complex or large. Pointer swapping is faster and safer.

Quick: After reversal, does the head pointer stay the same? Commit yes or no.

Common Belief: The head pointer remains pointing to the original first node after reversal.

Reality: The head pointer must update to the original tail node, which becomes the new head.

Why it matters: Failing to update the head causes traversal to start at the wrong node, breaking list operations.

Quick: Can reversing a doubly linked list be done without extra memory? Commit yes or no.

Common Belief: Reversing requires creating a new list or extra memory to hold nodes.

Reality: Reversal can be done in-place by swapping pointers, using only constant extra memory.

Why it matters: Using extra memory wastes resources and slows down performance, especially for large lists.

Quick: Does reversing a doubly linked list change the number of nodes? Commit yes or no.

Common Belief: Reversing might add or remove nodes to reorder the list.

Reality: Reversing only changes pointer directions; the number of nodes stays the same.

Why it matters: Misunderstanding this can lead to bugs where nodes are accidentally lost or duplicated.

Expert Zone

1

Swapping pointers in-place leverages the doubly linked list's bidirectional links, avoiding data movement and preserving node identity.

2

Tracking the last processed node during reversal is subtle but critical to correctly update the head pointer.

3

The reversal algorithm naturally handles empty and single-node lists without special cases, showing elegant design.

When NOT to use

If you need to preserve the original list order for other operations, reversing in-place is not suitable; instead, create a reversed copy. For singly linked lists, this pointer swapping approach doesn't work because nodes lack backward links; a different algorithm is needed.

Production Patterns

Reversing doubly linked lists is common in undo-redo systems, navigation history stacks, and playlist shuffling. In production, it is often combined with other operations like insertion or deletion, requiring careful pointer management to avoid memory leaks or dangling references.

Connections

Singly Linked List Reversal

Related operation but simpler structure with only next pointers.

Understanding doubly linked list reversal deepens comprehension of pointer manipulation, which helps grasp singly linked list reversal that uses pointer redirection without backward links.

Stack Data Structure

Reversing a list is conceptually similar to reversing order using a stack's LIFO behavior.

Knowing how stacks reverse order helps understand why reversing a doubly linked list flips traversal direction.

Railroad Switch Tracks

Physical system where tracks switch direction, similar to pointer swapping in nodes.

Recognizing how physical track switches redirect trains helps visualize pointer swaps that reverse list direction.

Common Pitfalls

#1 Not updating the head pointer after reversal.

Wrong approach:

void reverse() {
Node current = head;
Node temp = null;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
// head not updated
}

Correct approach:

void reverse() {
Node current = head;
Node temp = null;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}

Root cause:

Forgetting that the head must point to the new first node after pointers are swapped.

#2 Swapping data values instead of pointers to reverse the list.

Wrong approach:

void reverse() {
Node left = head;
Node right = tail; // assume tail pointer exists
while (left != right && left.prev != right) {
int temp = left.data;
left.data = right.data;
right.data = temp;
left = left.next;
right = right.prev;
}
}

Correct approach:

void reverse() {
Node current = head;
Node temp = null;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}

Root cause:

Misunderstanding that reversing means changing node order, not swapping data inside nodes.

#3 Using current.next to move forward after swapping pointers.

Wrong approach:

while (current != null) {
Node temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.next; // wrong: pointer swapped
}

Correct approach:

while (current != null) {
Node temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev; // correct: original next
}

Root cause:

Not realizing that after swapping, the original next pointer is now in prev.

Key Takeaways

A doubly linked list has nodes connected both forward and backward, allowing two-way traversal.

Reversing a doubly linked list means swapping each node's previous and next pointers to flip the direction.

The reversal can be done efficiently in-place without extra memory by carefully swapping pointers and updating the head.

Always update the head pointer to the original tail after reversal to maintain correct access to the list.

Understanding pointer manipulation in reversal helps avoid common bugs and is foundational for advanced list operations.

Practice

1. What is the main purpose of reversing a doubly linked list?

easy

A. To change the direction of traversal so the last node becomes the first

B. To delete all nodes from the list

C. To sort the nodes in ascending order

D. To convert it into a singly linked list

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes with pointers to both previous and next nodes, allowing traversal in both directions.

2. Step 2: Purpose of reversing

   Reversing swaps the previous and next pointers of each node, making the last node the first and vice versa.

3. Final Answer:

   To change the direction of traversal so the last node becomes the first -> Option A

4. Quick Check:

   Reversing means swapping directions [OK]

Hint: Reversing flips the list direction, last becomes first [OK]

Common Mistakes:

• Confusing reversing with deleting nodes
• Thinking reversing sorts the list
• Assuming it converts to singly linked list

2. Which of the following Java code snippets correctly swaps the next and prev pointers of a node curr in a doubly linked list?

easy

A. curr.next = curr.prev; curr.prev = null;

B. Node temp = curr.prev; curr.prev = curr.next; curr.next = null;

C. curr.next = curr.prev; curr.prev = curr.next;

D. Node temp = curr.next; curr.next = curr.prev; curr.prev = temp;

Solution

1. Step 1: Identify correct swapping logic

   Swapping two pointers requires a temporary variable to hold one pointer before overwriting it.

2. Step 2: Check each option

   A temporary variable is required to swap pointers without data loss. curr.next = curr.prev; curr.prev = null; incorrectly sets prev to null. Node temp = curr.prev; curr.prev = curr.next; curr.next = null; uses temp but wrongly sets next to null. curr.next = curr.prev; curr.prev = curr.next; overwrites without preserving original values. Node temp = curr.next; curr.next = curr.prev; curr.prev = temp; correctly swaps the pointers.

3. Final Answer:

   Node temp = curr.next; curr.next = curr.prev; curr.prev = temp; -> Option D

4. Quick Check:

   Use temp variable to swap pointers [OK]

Hint: Always use a temp variable to swap two pointers [OK]

Common Mistakes:

• Swapping without a temporary variable
• Setting one pointer to null accidentally
• Swapping pointers in wrong order

3. Given the following doubly linked list nodes and code to reverse it, what will be the printed output after reversal?

class Node {
  int data;
  Node prev, next;
  Node(int d) { data = d; prev = next = null; }
}

// List: 1 <-> 2 <-> 3
Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second; second.prev = head;
second.next = third; third.prev = second;

// Reverse code snippet
Node curr = head;
Node temp = null;
while (curr != null) {
  temp = curr.prev;
  curr.prev = curr.next;
  curr.next = temp;
  curr = curr.prev;
}
if (temp != null) head = temp.prev;

// Print list forward
Node ptr = head;
while (ptr != null) {
  System.out.print(ptr.data + " ");
  ptr = ptr.next;
}

medium

A. 1 2 3

B. 3 2 1

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Understand reversal logic

   The code swaps prev and next for each node, then moves curr to the original next node (now prev after swap).

2. Step 2: Trace the list after reversal

   Original list: 1 <-> 2 <-> 3
   After reversal, head points to node with data 3.
   Printing from head forward prints: 3 2 1

3. Final Answer:

   3 2 1 -> Option B

4. Quick Check:

   Reversed list prints nodes backward [OK]

Hint: After reversal, head points to original tail node [OK]

Common Mistakes:

• Not updating head after reversal
• Confusing prev and next pointers
• Printing from old head instead of new head

4. Identify the error in the following code snippet that attempts to reverse a doubly linked list:

Node curr = head;
while (curr != null) {
  Node temp = curr.next;
  curr.next = curr.prev;
  curr.prev = temp;
  curr = curr.next;
}

medium

A. The pointers next and prev are not swapped correctly

B. The temp variable should store curr.prev, not curr.next

C. The loop moves curr to curr.next instead of curr.prev after swapping

D. The loop condition should be curr.next != null

Solution

1. Step 1: Analyze pointer swapping

   The code swaps next and prev correctly using temp.

2. Step 2: Check loop iteration step

   After swapping, curr.next points to the original prev. To move forward in the original list, curr should move to curr.prev (which is original next). The code incorrectly moves to curr.next, causing wrong traversal.

3. Final Answer:

   The loop moves curr to curr.next instead of curr.prev after swapping -> Option C

4. Quick Check:

   Move curr to curr.prev after swapping [OK]

Hint: After swapping, move curr to curr.prev to continue traversal [OK]

Common Mistakes:

• Moving curr to wrong pointer after swap
• Confusing temp usage
• Incorrect loop condition

5. You have a doubly linked list with nodes containing integer data. After reversing the list using the standard pointer swap method, you want to find the middle node efficiently. Which approach is best to find the middle node after reversal?

hard

A. Use two pointers starting from the new head: one moves one step, the other moves two steps until the faster reaches null

B. Traverse from the original head before reversal to find the middle

C. Count nodes from the tail and divide by two to find middle index

D. Reverse the list again and then find the middle node

Solution

1. Step 1: Understand list reversal effect

   After reversal, the head points to the original tail. The list is still doubly linked and can be traversed forward.

2. Step 2: Efficient middle node finding

   The two-pointer technique (slow and fast pointers) starting from the new head finds the middle in one pass efficiently.

3. Final Answer:

   Use two pointers starting from the new head: one moves one step, the other moves two steps until the faster reaches null -> Option A

4. Quick Check:

   Two-pointer method finds middle in O(n) [OK]

Hint: Use slow and fast pointers from new head to find middle [OK]

Common Mistakes:

• Trying to find middle from old head after reversal
• Counting nodes from tail which is inefficient
• Reversing list again unnecessarily