Reverse a Doubly Linked List in DSA Python - Execution Trace

Concept Flow - Reverse a Doubly Linked List

Start at head node

↓

For each node: Swap prev and next pointers

↓

Move to new prev (old next) node

↓

Repeat until current node is None

↓

Update head to last processed node

↓

Done: List reversed

We start at the head and for each node, swap its previous and next pointers. Then move to the next node (which is the old next, now prev). Repeat until all nodes are processed. Finally, update the head to the last node processed.

Execution Sample

DSA Python

def reverse_dll(head):
    current = head
    temp = None
    while current:
        temp = current.prev
        current.prev = current.next
        current.next = temp
        current = current.prev
    if temp:
        head = temp.prev
    return head

This code reverses a doubly linked list by swapping prev and next pointers of each node and updating the head.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node 1	None	1 <-> 2 <-> 3 <-> 4 <-> None
2	Swap prev and next of Node 1	Node 1	prev: None -> Node 2, next: Node 2 -> None	1 <- 2 <-> 3 <-> 4 <-> None
3	Move current to old next (now prev)	Node 2	current: Node 1 -> Node 2	1 <- 2 <-> 3 <-> 4 <-> None
4	Swap prev and next of Node 2	Node 2	prev: Node 1 -> Node 3, next: Node 3 -> Node 1	1 <- 2 <- 3 <-> 4 <-> None
5	Move current to old next (now prev)	Node 3	current: Node 2 -> Node 3	1 <- 2 <- 3 <-> 4 <-> None
6	Swap prev and next of Node 3	Node 3	prev: Node 2 -> Node 4, next: Node 4 -> Node 2	1 <- 2 <- 3 <- 4 <-> None
7	Move current to old next (now prev)	Node 4	current: Node 3 -> Node 4	1 <- 2 <- 3 <- 4 <-> None
8	Swap prev and next of Node 4	Node 4	prev: Node 3 -> None, next: None -> Node 3	1 <- 2 <- 3 <- 4
9	Move current to old next (now prev)	None	current: Node 4 -> None	1 <- 2 <- 3 <- 4
10	Update head to last processed node	None	head: Node 1 -> Node 4	4 <-> 3 <-> 2 <-> 1 <-> None
11	Return new head	Node 4	None	4 <-> 3 <-> 2 <-> 1 <-> None

💡 current becomes None, all nodes processed, head updated to last node

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
current	Node 1	Node 2	Node 3	Node 4	None	None
temp	None	Node 1.prev (None)	Node 2.prev (Node 1)	Node 3.prev (Node 2)	Node 4.prev (Node 3)	Node 4.prev (Node 3)
head	Node 1	Node 1	Node 1	Node 1	Node 1	Node 4

Key Moments - 3 Insights

Why do we swap prev and next pointers for each node?

Swapping prev and next reverses the direction of links. See execution_table steps 2,4,6,8 where pointers change to reverse the list.

Why do we move current to current.prev after swapping?

After swapping, current.prev points to the original next node. Moving current to current.prev moves forward in the original list. See execution_table steps 3,5,7,9.

How do we update the head after reversal?

After the loop, temp holds the original prev of the last processed node. Due to prior swaps, temp.prev now points to the new head (original tail node). See execution_table step 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node at step 6?

A Node 3

B Node 2

C Node 4

D None

💡 Hint

Check the 'Current Node' column at step 6 in execution_table.

At which step does the 'current' pointer become None?

A Step 8

B Step 10

C Step 9

D Step 11

💡 Hint

Look for 'current' value changing to None in variable_tracker and execution_table.

If we forget to update the head after reversal, what will be the visual state at the end?

A List remains reversed with head at Node 4

B List remains reversed but head points to Node 1 (old head)

C List is not reversed

D List becomes empty

💡 Hint

Refer to execution_table step 10 where head is updated to new node.

Concept Snapshot

Reverse a Doubly Linked List:
- Start at head node
- For each node, swap prev and next pointers
- Move current to old next (now prev)
- Repeat until current is None
- Update head to last processed node
- Return new head

Full Transcript

To reverse a doubly linked list, we start at the head node. For each node, we swap its prev and next pointers to reverse the direction of links. Then we move the current pointer to the old next node, which after swapping is current.prev. We repeat this until current becomes None, meaning we processed all nodes. Finally, we update the head pointer to the last node processed, which is stored in temp.prev. This completes the reversal. The execution table shows each step with pointer changes and the visual state of the list. The variable tracker shows how current, temp, and head change over time. Key moments clarify why we swap pointers, why we move current to current.prev, and how we update the head. The visual quiz tests understanding of these steps. This method reverses the list in place without creating new nodes.