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.

Practice

1. What does forward traversal in a linked list mean?

easy

A. Visiting nodes from the first node to the last node

B. Visiting nodes from the last node to the first node

C. Skipping every alternate node while visiting

D. Visiting nodes randomly

Solution

1. Step 1: Understand forward traversal

   Forward traversal means starting at the first node and moving to the next node repeatedly until the end.

2. Step 2: Compare with options

   Only Visiting nodes from the first node to the last node describes visiting nodes from first to last, which matches forward traversal.

3. Final Answer:

   Visiting nodes from the first node to the last node -> Option A

4. Quick Check:

   Forward traversal = first to last [OK]

Hint: Forward means start to end in order [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal is random
• Assuming skipping nodes is traversal

2. Which of the following is the correct syntax to traverse a singly linked list forward in C?

easy

A. for(Node* curr = head; curr != NULL; curr = curr->prev) { /* process curr */ }

B. for(Node* curr = head; curr != NULL; curr = curr->next) { /* process curr */ }

C. while(head != NULL) { head = head->prev; }

D. for(Node* curr = tail; curr != NULL; curr = curr->prev) { /* process curr */ }

Solution

1. Step 1: Identify forward traversal syntax

   Forward traversal in singly linked list uses next pointer starting from head.

2. Step 2: Check options for correct pointer usage

   for(Node* curr = head; curr != NULL; curr = curr->next) { /* process curr */ } uses curr = curr->next starting from head, which is correct.

3. Final Answer:

   for(Node* curr = head; curr != NULL; curr = curr->next) { /* process curr */ } -> Option B

4. Quick Check:

   Use next pointer from head for forward traversal [OK]

Hint: Use next pointer from head for forward traversal [OK]

Common Mistakes:

• Using prev pointer in singly linked list
• Starting from tail in singly linked list
• Using incorrect loop conditions

3. What will be the output of the following code snippet that traverses a doubly linked list backward?

typedef struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
} Node;

void printBackward(Node* tail) {
  Node* curr = tail;
  while(curr != NULL) {
    printf("%d ", curr->data);
    curr = curr->prev;
  }
}

// List: 1 <-> 2 <-> 3, tail points to node with data 3
printBackward(tail);

medium

A. 1 2 3

B. 3 1 2

C. 3 2 1

D. 2 3 1

Solution

1. Step 1: Understand backward traversal in doubly linked list

   Starting from tail (3), moving prev pointer visits nodes 3, 2, then 1.

2. Step 2: Trace the output

   Prints 3, then 2, then 1 with spaces.

3. Final Answer:

   3 2 1 -> Option C

4. Quick Check:

   Backward traversal prints tail to head [OK]

Hint: Backward traversal prints from tail to head [OK]

Common Mistakes:

• Confusing order of printing
• Using next pointer instead of prev
• Starting from head instead of tail

4. Identify the error in the following code that attempts to traverse a doubly linked list backward:

void traverseBackward(Node* tail) {
  Node* curr = tail;
  while(curr->next != NULL) {
    printf("%d ", curr->data);
    curr = curr->prev;
  }
}

medium

A. The printf statement is missing a newline character

B. The pointer curr should start from head, not tail

C. The code should use curr = curr->next instead of curr = curr->prev

D. The loop condition should check curr != NULL, not curr->next != NULL

Solution

1. Step 1: Analyze loop condition for backward traversal

   Backward traversal moves using prev pointer until curr becomes NULL.

2. Step 2: Identify incorrect condition

   Checking curr->next != NULL is wrong; it should be curr != NULL to avoid null pointer access.

3. Final Answer:

   The loop condition should check curr != NULL, not curr->next != NULL -> Option D

4. Quick Check:

   Loop until curr is NULL in backward traversal [OK]

Hint: Check curr != NULL in loops, not curr->next for backward traversal [OK]

Common Mistakes:

• Using next pointer condition in backward traversal
• Starting from head instead of tail
• Ignoring null pointer checks

5. Given a doubly linked list with nodes containing integers, write a function to print the list forward and then backward without using extra space. Which approach correctly achieves this?

hard

A. Traverse from head to tail printing data, then traverse from tail to head printing data

B. Traverse from head to tail printing data twice

C. Traverse from tail to head printing data, then traverse from head to tail printing data

D. Traverse from head to tail printing data, then reverse the list and print forward again

Solution

1. Step 1: Understand traversal without extra space

   Use existing next and prev pointers to traverse forward and backward.

2. Step 2: Identify correct approach

   Traverse from head to tail printing data, then traverse from tail to head printing data correctly traverses forward from head to tail, then backward from tail to head printing data without modifying list.

3. Final Answer:

   Traverse from head to tail printing data, then traverse from tail to head printing data -> Option A

4. Quick Check:

   Use head and tail pointers for forward and backward traversal [OK]

Hint: Print forward from head, backward from tail without changing list [OK]

Common Mistakes:

• Reversing list unnecessarily
• Printing forward twice
• Using extra space like arrays or stacks