Reverse a Doubly Linked List in DSA C - 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 NULL

↓

Update head to last processed node

↓

Done: List reversed

We start at the head node, swap the prev and next pointers of each node, move forward using the swapped pointers, and finally update the head to the last node processed.

Execution Sample

DSA C

void reverse(struct Node** head_ref) {
  struct Node* current = *head_ref;
  struct Node* temp = NULL;
  while (current != NULL) {
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    current = current->prev;
  }
  if (temp != NULL) *head_ref = temp->prev;
}

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

Execution Table

Step	Operation	Current Node	prev Pointer Before	next Pointer Before	prev Pointer After	next Pointer After	Move To	Head Pointer	Visual State
1	Start at head	Node 1	NULL	Node 2	Node 2	NULL	Node 2	Node 1	1 <-> 2 <-> 3 <-> 4 <-> NULL
2	Swap pointers	Node 2	Node 1	Node 3	Node 3	Node 1	Node 3	Node 1	1 <-> 2 <-> 3 <-> 4 <-> NULL
3	Swap pointers	Node 3	Node 2	Node 4	Node 4	Node 2	Node 4	Node 1	1 <-> 2 <-> 3 <-> 4 <-> NULL
4	Swap pointers	Node 4	Node 3	NULL	NULL	Node 3	NULL	Node 1	1 <-> 2 <-> 3 <-> 4 <-> NULL
5	Update head	NULL	-	-	-	-	-	Node 4	4 <-> 3 <-> 2 <-> 1 <-> NULL
6	End	NULL	-	-	-	-	-	Node 4	4 <-> 3 <-> 2 <-> 1 <-> NULL

💡 current becomes NULL, loop ends, head updated to last processed node (Node 4)

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	Node 1	Node 2	Node 3	Node 4	NULL	NULL	NULL
temp	NULL	Node 1	Node 2	Node 3	Node 4	Node 4	Node 4
head_ref	Node 1	Node 1	Node 1	Node 1	Node 1	Node 4	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 the list links. See execution_table steps 1 to 4 where prev and next pointers are exchanged.

Why do we move current to current->prev after swapping?

After swapping, current->prev points to the next node in original order. Moving to current->prev continues traversal forward. This is shown in execution_table column 'Move To'.

How do we update the head pointer after reversal?

After the loop ends, temp points to the old prev of the last node processed. The new head is temp->prev, as shown in execution_table step 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the 'prev Pointer After' of Node 3?

A Node 2

B Node 1

C Node 4

D NULL

💡 Hint

Check the 'prev Pointer After' column for step 3 in execution_table.

At which step does the current pointer become NULL, ending the loop?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at the 'current Node' column in execution_table to find when it becomes NULL.

If we forget to update the head pointer after reversal, what will be the head node?

A Node 4 (new head)

B Node 1 (original head)

C NULL

D Node 2

💡 Hint

Refer to variable_tracker for head_ref changes and execution_table step 5.

Concept Snapshot

Reverse a Doubly Linked List:
- Traverse each node from head
- Swap prev and next pointers
- Move to original next via swapped pointers
- Update head to last node processed
- Result: list links reversed direction

Full Transcript

To reverse a doubly linked list, we start at the head node and for each node, swap its prev and next pointers. This reverses the direction of the links. We then move to the next node using the swapped pointers (current = current->prev). When current becomes NULL, we update the head pointer to the last node processed, which is stored in temp->prev. This process reverses the list so the last node becomes the new head. 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_ref change during execution. Key moments clarify why we swap pointers, how traversal continues, and how the head is updated. The visual quiz tests understanding of pointer changes and loop termination.