Traversal Forward and Backward in DSA C - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at head node

↓

Visit current node

↓

Move to next node

↓

Is next node NULL?

No→Repeat visit

Yes↓

Reached end, start backward traversal

↓

Visit current node

↓

Move to previous node

↓

Is previous node NULL?

No→Repeat visit

Yes↓

Traversal complete

Traverse nodes from head to tail using next pointers, then from tail to head using previous pointers.

Execution Sample

DSA C

Node* current = head;
while (current != NULL) {
    printf("%d\n", current->data);
    current = current->next;
}

current = tail;

while (current != NULL) {
    printf("%d\n", current->data);
    current = current->prev;
}

Traverse a doubly linked list forward from head to tail, then backward from tail to head.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start forward traversal	Node 1 (data=10)	current = head	10 <-> 20 <-> 30 <-> NULL
2	Visit node	Node 1 (10)	Print 10	10 <-> 20 <-> 30 <-> NULL
3	Move to next	Node 2 (20)	current = current->next	10 <-> 20 <-> 30 <-> NULL
4	Visit node	Node 2 (20)	Print 20	10 <-> 20 <-> 30 <-> NULL
5	Move to next	Node 3 (30)	current = current->next	10 <-> 20 <-> 30 <-> NULL
6	Visit node	Node 3 (30)	Print 30	10 <-> 20 <-> 30 <-> NULL
7	Move to next	NULL	current = current->next	10 <-> 20 <-> 30 <-> NULL
8	End forward traversal, start backward	Node 3 (30)	current = tail	10 <-> 20 <-> 30 <-> NULL
9	Visit node	Node 3 (30)	Print 30	10 <-> 20 <-> 30 <-> NULL
10	Move to prev	Node 2 (20)	current = current->prev	10 <-> 20 <-> 30 <-> NULL
11	Visit node	Node 2 (20)	Print 20	10 <-> 20 <-> 30 <-> NULL
12	Move to prev	Node 1 (10)	current = current->prev	10 <-> 20 <-> 30 <-> NULL
13	Visit node	Node 1 (10)	Print 10	10 <-> 20 <-> 30 <-> NULL
14	Move to prev	NULL	current = current->prev	10 <-> 20 <-> 30 <-> NULL
15	Traversal complete	NULL	current == NULL	10 <-> 20 <-> 30 <-> NULL

💡 Traversal stops when current becomes NULL in both forward and backward directions.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	After Step 12	Final
current	Node 1 (10)	Node 2 (20)	Node 3 (30)	NULL	Node 2 (20)	Node 1 (10)	NULL

Key Moments - 3 Insights

Why does the backward traversal start at the tail node, not at NULL?

Because after forward traversal ends at NULL (step 7), we reset current to tail (step 8) to start backward traversal. This is shown in execution_table rows 7 and 8.

Why do we check current != NULL before visiting nodes?

To avoid accessing data of a NULL pointer which causes errors. The check ensures we only visit valid nodes, as seen in steps 1 and 14.

Why does the forward traversal stop when current becomes NULL?

Because NULL means no more nodes ahead. This is the termination condition shown in step 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current after step 5?

A Node 2 (20)

B NULL

C Node 3 (30)

D Node 1 (10)

💡 Hint

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

At which step does the forward traversal end?

A Step 7

B Step 8

C Step 6

D Step 14

💡 Hint

Look for when current becomes NULL in forward traversal in execution_table.

If we start backward traversal from head instead of tail, what happens?

A Traversal prints nodes forward again.

B Traversal stops immediately because head->prev is NULL.

C Traversal prints nodes in reverse order correctly.

D Traversal causes an error.

💡 Hint

Refer to pointer changes and current node in backward traversal steps in execution_table.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Start at head, move next until NULL
- Visit each node's data
- Then start at tail, move prev until NULL
- Visit each node's data backward
- Use current pointer to track position
- Stop when current is NULL

Full Transcript

This concept shows how to traverse a doubly linked list forward from the head node to the tail node by following next pointers, printing each node's data. After reaching the end (NULL), traversal continues backward from the tail to the head by following prev pointers, again printing each node's data. The traversal stops when the current pointer becomes NULL in either direction. The execution table traces each step, showing the current node, pointer changes, and the list's visual state. Key moments clarify why traversal starts backward at the tail and why NULL checks are necessary to avoid errors.