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

Start with current = head (10).
Step 1: current = 10
Swap prev and next pointers. Move to current.prev (was next).
Step 2: current = 20
Swap prev and next, move to current.prev.
Step 3: current = 30
Swap pointers and move to current.prev.
Step 4: current = 40
Swap pointers and move to current.prev.
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.