Reverse a Doubly Linked List in DSA Python

Mental Model

To reverse a doubly linked list, we swap the next and previous links for each node and move forward until all nodes are reversed.

Analogy: Imagine walking backward on a path where each step has a forward and backward arrow; reversing means swapping these arrows so you can walk the path in the opposite direction.

null ← 1 ↔ 2 ↔ 3 -> null
↑curr at 1

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, reverse entire list

Goal: Reverse the list so it becomes 3 ↔ 2 ↔ 1

Step 1: swap next and prev of node 1, move curr to prev (which was originally next)

null ← 1 null  2 ↔ 3 -> null
↑curr at 2

Why: Swapping pointers reverses direction; moving curr to prev continues traversal forward in original list

Step 2: swap next and prev of node 2, move curr to prev

null ← 1 ← 2 null  3 -> null
↑curr at 3

Why: Continue swapping pointers to reverse links for each node

Step 3: swap next and prev of node 3, move curr to prev

null ← 1 ← 2 ← 3 null
↑curr at null (end)

Why: Last node reversed; curr is now null, stop traversal

Step 4: update head to last processed node (3)

null ← 3 ↔ 2 ↔ 1 -> null
↑head at 3

Why: New head is the last node processed after reversal

Result:

null ← 3 ↔ 2 ↔ 1 -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node
        new_node.prev = curr

    def reverse(self):
        curr = self.head
        temp = None
        while curr:
            temp = curr.prev  # store prev
            curr.prev = curr.next  # swap prev and next
            curr.next = temp
            curr = curr.prev  # move to next node in original list
        if temp:
            self.head = temp.prev  # update head to last node processed

    def __str__(self):
        result = []
        curr = self.head
        while curr:
            result.append(str(curr.data))
            curr = curr.next
        return ' ↔ '.join(result) + ' -> null'

# Driver code
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
print("Original list:", dll)
dll.reverse()
print("Reversed list:", dll)

while curr:

iterate through each node until end

temp = curr.prev # store prev

keep original prev to use after swapping

curr.prev = curr.next # swap prev and next

reverse the direction of prev pointer

curr.next = temp

reverse the direction of next pointer

curr = curr.prev # move to next node in original list

advance to next node using swapped pointers

if temp:

check if list was not empty to update head

self.head = temp.prev # update head to last node processed

set new head after reversal

Output

Original list: 1 ↔ 2 ↔ 3 -> null

Reversed list: 3 ↔ 2 ↔ 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once to swap pointers

Space: O(1) because reversal is done in place without extra storage

vs Alternative: Compared to creating a new reversed list (O(n) time and space), this in-place reversal saves memory

Edge Cases

empty list

reverse does nothing, head remains None

DSA Python

if temp:

single node list

reverse swaps pointers but list remains same, head unchanged

DSA Python

if temp:

When to Use This Pattern

When you need to reverse the order of elements in a doubly linked list, use pointer swapping to reverse links efficiently.

Common Mistakes

Mistake: Advancing curr using curr.next after swapping pointers
Fix: Advance curr using curr.prev because pointers are swapped

Mistake: Not updating the head pointer after reversal
Fix: Update head to the last processed node after loop ends

Summary

Reverses a doubly linked list by swapping next and prev pointers of each node.

Use when you want to reverse the order of nodes in a doubly linked list efficiently.

The key insight is to swap pointers and move forward using the swapped links until all nodes are reversed.