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 tail node

↓

Visit current node

↓

Move to previous node

↓

Is previous node NULL?

No→Repeat visit

Yes↓

Traversal complete

Start from the head, move forward visiting nodes until tail, then move backward visiting nodes until head.

Execution Sample

DSA C++

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

// Forward traversal
Node* curr = head;
while(curr != nullptr) {
  std::cout << curr->data << std::endl;
  curr = curr->next;
}

// Backward traversal
curr = tail;
while(curr != nullptr) {
  std::cout << curr->data << std::endl;
  curr = curr->prev;
}

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

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start forward traversal	Node 1 (data=10)	curr = head	10 <-> 20 <-> 30 <-> 40 <-> 50
2	Visit current node	Node 1 (10)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 10)
3	Move to next node	Node 2 (20)	curr = curr->next	10 <-> 20 <-> 30 <-> 40 <-> 50
4	Visit current node	Node 2 (20)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 20)
5	Move to next node	Node 3 (30)	curr = curr->next	10 <-> 20 <-> 30 <-> 40 <-> 50
6	Visit current node	Node 3 (30)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 30)
7	Move to next node	Node 4 (40)	curr = curr->next	10 <-> 20 <-> 30 <-> 40 <-> 50
8	Visit current node	Node 4 (40)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 40)
9	Move to next node	Node 5 (50)	curr = curr->next	10 <-> 20 <-> 30 <-> 40 <-> 50
10	Visit current node	Node 5 (50)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 50)
11	Move to next node	NULL	curr = curr->next	Traversal forward ends (curr is NULL)
12	Start backward traversal	Node 5 (50)	curr = tail	10 <-> 20 <-> 30 <-> 40 <-> 50
13	Visit current node	Node 5 (50)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 50)
14	Move to previous node	Node 4 (40)	curr = curr->prev	10 <-> 20 <-> 30 <-> 40 <-> 50
15	Visit current node	Node 4 (40)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 40)
16	Move to previous node	Node 3 (30)	curr = curr->prev	10 <-> 20 <-> 30 <-> 40 <-> 50
17	Visit current node	Node 3 (30)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 30)
18	Move to previous node	Node 2 (20)	curr = curr->prev	10 <-> 20 <-> 30 <-> 40 <-> 50
19	Visit current node	Node 2 (20)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 20)
20	Move to previous node	Node 1 (10)	curr = curr->prev	10 <-> 20 <-> 30 <-> 40 <-> 50
21	Visit current node	Node 1 (10)	None	10 <-> 20 <-> 30 <-> 40 <-> 50 (Printed: 10)
22	Move to previous node	NULL	curr = curr->prev	Traversal backward ends (curr is NULL)

💡 Traversal stops when curr becomes NULL moving forward and backward.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 14	After Step 16	After Step 18	After Step 20	After Step 22
curr	Node 1 (10)	Node 2 (20)	Node 3 (30)	Node 4 (40)	Node 5 (50)	NULL	Node 4 (40)	Node 3 (30)	Node 2 (20)	Node 1 (10)	NULL

Key Moments - 3 Insights

Why does the forward traversal stop when curr becomes NULL?

Because curr moves to curr->next each time, when there is no next node, curr becomes NULL, signaling the end of the list (see execution_table step 11).

Why do we start backward traversal from tail, not head?

Backward traversal uses the prev pointer, which is only valid starting from the tail node (see execution_table step 12). Starting at head would have prev as NULL immediately.

What happens if the list is empty (head and tail are NULL)?

Both forward and backward traversals immediately stop because curr is NULL at start (not shown in table but implied by exit condition).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of curr after step 7?

A Node 4 (40)

B Node 3 (30)

C Node 5 (50)

D NULL

💡 Hint

Check the 'Pointer Changes' and 'Current Node' columns at step 7 in execution_table.

At which step does the forward traversal end because curr becomes NULL?

A Step 10

B Step 12

C Step 11

D Step 22

💡 Hint

Look for the step where 'curr = curr->next' results in NULL in execution_table.

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

A Traversal would print all nodes backward correctly.

B Traversal would stop immediately because curr->prev is NULL at head.

C Traversal would cause an error due to invalid pointer.

D Traversal would print nodes forward instead.

💡 Hint

Refer to key_moments about starting backward traversal from tail and prev pointers.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Forward: Start at head, move using next pointer until NULL.
- Backward: Start at tail, move using prev pointer until NULL.
- Visit nodes by printing data at each step.
- Traversal ends when current pointer becomes NULL.
- Requires both next and prev pointers in nodes.

Full Transcript

Traversal forward and backward in a doubly linked list means visiting nodes from head to tail using next pointers, then from tail to head using prev pointers. We start forward traversal at the head node and move forward until the next pointer is NULL, printing each node's data. Then we start backward traversal at the tail node and move backward until the prev pointer is NULL, printing each node's data. The traversal stops when the current pointer becomes NULL in either direction. This requires the doubly linked list nodes to have both next and prev pointers to move forward and backward respectively.

Practice

1. What does forward traversal mean in the context of a singly linked list?

easy

A. Visiting nodes from the head to the tail in order

B. Visiting nodes from the tail to the head in reverse order

C. Skipping every other node while visiting

D. Visiting nodes randomly without order

Solution

1. Step 1: Understand singly linked list structure

   A singly linked list has nodes connected only forward, from head to tail.

2. Step 2: Define forward traversal

   Forward traversal means visiting nodes starting at the head and moving to the tail in order.

3. Final Answer:

   Visiting nodes from the head to the tail in order -> Option A

4. Quick Check:

   Forward traversal = head to tail [OK]

Hint: Forward means start at head and go next nodes [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal can skip nodes
• Assuming random order traversal

2. Which of the following is the correct syntax to traverse a vector forward in C++?

easy

A. for (int i = 0; i < vec.size(); i++) { cout << vec[i] << ' '; }

B. for (int i = vec.size(); i >= 0; i--) { cout << vec[i] << ' '; }

C. for (int i = 1; i <= vec.size(); i++) { cout << vec[i] << ' '; }

D. for (int i = vec.size() - 1; i > 0; i--) { cout << vec[i] << ' '; }

Solution

1. Step 1: Understand vector indexing in C++

   Vectors are zero-indexed, so valid indices are 0 to size()-1.

2. Step 2: Check loop boundaries

   for (int i = 0; i < vec.size(); i++) { cout << vec[i] << ' '; } loops from 0 to size()-1, correctly accessing all elements forward.

3. Final Answer:

   for (int i = 0; i < vec.size(); i++) { cout << vec[i] << ' '; } -> Option A

4. Quick Check:

   Forward vector traversal uses i from 0 to size()-1 [OK]

Hint: Start from 0, go to less than size() for forward loops [OK]

Common Mistakes:

• Using i <= vec.size() causing out-of-range error
• Starting loop from 1 instead of 0
• Looping backwards for forward traversal

3. What is the output of the following C++ code?

std::vector<int> v = {10, 20, 30};
for (int i = v.size() - 1; i >= 0; i--) {
    std::cout << v[i] << ' ';
}

medium

A. 10 20 30

B. 30 20 10

C. 30 20

D. Runtime error

Solution

1. Step 1: Analyze loop start and end

   Loop starts at v.size()-1 = 2 and decrements to 0 inclusive.

2. Step 2: Trace output values

   v[2] = 30, v[1] = 20, v[0] = 10 printed in that order with spaces.

3. Final Answer:

   30 20 10 -> Option B

4. Quick Check:

   Backward traversal prints 30 20 10 [OK]

Hint: Backward vector loop starts at size()-1 down to 0 [OK]

Common Mistakes:

• Confusing forward and backward order
• Off-by-one errors in loop condition
• Expecting runtime error due to unsigned index

4. Identify the error in this backward traversal of a vector in C++:

std::vector<int> v = {1, 2, 3};
for (int i = v.size(); i >= 0; i--) {
    std::cout << v[i] << ' ';
}

medium

A. Vector cannot be traversed backward

B. Loop condition should be i > 0, not i >= 0

C. Loop starts at v.size(), which is out of range

D. No error, code runs fine

Solution

1. Step 1: Check loop start index

   v.size() is 3, but valid indices are 0 to 2, so v[3] is invalid.

2. Step 2: Understand consequences

   Accessing v[3] causes out-of-range error or undefined behavior.

3. Final Answer:

   Loop starts at v.size(), which is out of range -> Option C

4. Quick Check:

   Index must be less than size() [OK]

Hint: Start backward loop at size()-1, not size() [OK]

Common Mistakes:

• Starting loop at size() instead of size()-1
• Ignoring vector index bounds
• Assuming no error on out-of-range access

5. Given a doubly linked list with nodes 1 <-> 2 <-> 3, which code snippet correctly prints the list backward starting from tail in C++?

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

Node* tail = /* points to node with data 3 */;
// Which loop prints backward traversal?

hard

A. for (Node* cur = tail; cur->next != nullptr; cur = cur->next) { std::cout << cur->data << ' '; }

B. for (Node* cur = tail; cur != nullptr; cur = cur->next) { std::cout << cur->data << ' '; }

C. for (Node* cur = tail; cur->prev != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; }

D. for (Node* cur = tail; cur != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; }

Solution

1. Step 1: Understand doubly linked list backward traversal

   Backward traversal moves from tail to head using prev pointers.

2. Step 2: Check loop correctness

   for (Node* cur = tail; cur != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; } starts at tail and moves using cur = cur->prev until nullptr, printing all nodes backward.

3. Final Answer:

   for (Node* cur = tail; cur != nullptr; cur = cur->prev) { std::cout << cur->data << ' '; } -> Option D

4. Quick Check:

   Backward traversal uses prev pointer from tail [OK]

Hint: Backward traversal uses prev pointer from tail to head [OK]

Common Mistakes:

• Using next pointer for backward traversal
• Stopping loop before head (checking cur->prev != nullptr)
• Starting from head instead of tail