Why Traversal Forward and Backward in DSA C++?

The Big Idea

What if you could flip through your list from both ends without losing your place or wasting time?

The Scenario

Imagine you have a long list of your favorite songs written on paper. You want to find a song you heard recently, but you only remember if it was near the start or the end of the list. You start flipping pages from the front, but it takes a long time. Then you try from the back, but you have to flip all the way through again. This back-and-forth flipping is tiring and slow.

The Problem

Manually searching through a list from only one direction means you might waste a lot of time going through many items before finding what you want. Also, if you want to go backward, you have to start over or remember where you were, which is confusing and error-prone.

The Solution

Traversal forward and backward lets you move through a list in both directions easily. This means you can start from the front or the back and move step-by-step without losing your place. It saves time and makes finding items much simpler and faster.

Before vs After

✗ Before

for (int i = 0; i < size; i++) {
    if (list[i] == target) {
        // found
    }
}
// To go backward, repeat from end

✓ After

Node* current = head;
while (current != nullptr) {
    if (current->value == target) break;
    current = current->next;
}
// To go backward
while (current != nullptr) {
    current = current->prev;
}

What It Enables

This lets you quickly and easily explore data from both ends, making searching and navigation smooth and efficient.

Real Life Example

Think of a playlist app where you can skip songs forward or backward easily without restarting the list or losing your place.

Key Takeaways

Manual one-way search is slow and tiring.

Traversal forward and backward allows easy movement in both directions.

This makes finding and navigating data faster and less error-prone.

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