Doubly Linked List – Reverse Operation

Reverse Operation in Doubly Linked List

Reversing a doubly linked list so that the last node becomes the new head, and both next and prev pointers are swapped for every node.

In a doubly linked list, reversing is simpler compared to a singly linked list because each node has both next and prev pointers.

The reversal process involves traversing the list and swapping the next and prev pointers of each node. Finally, the head pointer is updated to point to the new head (previously the tail).

Visual Example

Suppose we have the following doubly linked list:

We want to reverse the list so that the order becomes 50 ⇄ 40 ⇄ 30 ⇄ 20 ⇄ 10.

Step-by-Step Reversal

1. Start with current = head (10).
2. Step 1: current = 10
   Swap prev and next pointers. Move to current.prev (was next).
3. Step 2: current = 20
   Swap prev and next, move to current.prev.
4. Step 3: current = 30
   Swap pointers and move to current.prev.
5. Step 4: current = 40
   Swap pointers and move to current.prev.
6. Step 5: current = 50
   Swap pointers and now current.prev = null. This is the new head.

At the end, current becomes null, and the last non-null node (which was the tail) is now the new head. Return this node as the head of the reversed list.

Complete Pseudocode: Reverse a Doubly Linked List

This pseudocode shows how to reverse a doubly linked list in-place by swapping the next and prev pointers of each node.

function reverse(head):
    curr = head
    temp = null

    while curr != null:
        temp = curr.prev
        curr.prev = curr.next
        curr.next = temp
        curr = curr.prev

    if temp != null:
        head = temp.prev

    return head

Let’s understand each part of the code step by step.

function reverse(head):
    curr = head
    temp = null

Explanation: We use curr to traverse the list and temp to help with swapping. Initially, we start from the head of the list.

---

    while curr != null:
        temp = curr.prev
        curr.prev = curr.next
        curr.next = temp
        curr = curr.prev

Explanation: For each node, we swap the prev and next pointers. Then we move curr to its new prev, which was originally next.

---

    if temp != null:
        head = temp.prev

    return head

Explanation: After the loop, temp holds the last processed node. Its prev pointer now points to the new head of the reversed list.

Doubly Linked List Reverse Operation Examples

The following examples demonstrate how a doubly linked list is reversed in-place by swapping the next and prev pointers of each node.

Initial List	Reversed List	Explanation
[10, 20, 30, 40]	[40, 30, 20, 10]	Each node's next and prev pointers are swapped while traversing the list. The new head is the original tail.
[5, 15, 25]	[25, 15, 5]	The next and prev of each node are flipped. The traversal direction is reversed and the tail becomes the head.
[1]	[1]	A single-node doubly linked list remains unchanged after reversal.
[]	[]	An empty list has no nodes to reverse; the result is still an empty list.

Time Complexity of Doubly Linked List Reverse Operation

Reversal Case	Time Complexity	Explanation
Iterative Reversal	O(n)	We traverse the entire list once, swapping each node’s next and prev pointers. Each operation takes constant time.
Recursive Reversal	O(n)	The recursive approach also visits each node once, recursively swapping next and prev pointers, with additional call stack usage.

Space Complexity of Doubly Linked List Reverse Operation

Reverse Case	Space Complexity	Explanation
Iterative Reverse	O(1)	The reversal is done in-place by swapping next and prev pointers of each node using a fixed number of variables. No extra memory is required.
Recursive Reverse	O(n)	Each recursive call adds a new stack frame, consuming additional memory proportional to the number of nodes in the list.

Key Takeaways

• Reversing a doubly linked list involves swapping the next and prev pointers for each node.
• The head of the list changes to the last node after reversal.
• An iterative approach is more space-efficient, requiring only constant space.
• A recursive approach is elegant but uses O(n) space due to call stack usage.
• Proper pointer handling is crucial to avoid breaking the list or creating cyclic references.
• Always test with edge cases: empty list, single-node list, and lists with multiple nodes.