Traversal Forward and Backward in DSA C++

Mental Model

Traversal means visiting each item in a list one by one, either from start to end or from end to start.

Analogy: Imagine walking through a line of people holding hands. Going forward means walking from the first person to the last. Going backward means walking back from the last person to the first.

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null
↑ current position at head

Dry Run Walkthrough

Input: Doubly linked list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5; traverse forward then backward

Goal: Visit and print all nodes from start to end, then from end to start

Step 1: Start at head node (1) for forward traversal

head -> [1] ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null

Why: We begin traversal from the first node

Step 2: Move forward to node 2

head -> 1 ↔ [2] ↔ 3 ↔ 4 ↔ 5 -> null

Why: Visit next node in forward direction

Step 3: Move forward to node 3

head -> 1 ↔ 2 ↔ [3] ↔ 4 ↔ 5 -> null

Why: Continue forward traversal

Step 4: Move forward to node 4

head -> 1 ↔ 2 ↔ 3 ↔ [4] ↔ 5 -> null

Why: Keep moving forward

Step 5: Move forward to node 5 (tail)

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ [5] -> null

Why: Reached last node for forward traversal

Step 6: Start backward traversal from tail node (5)

head -> 1 ↔ 2 ↔ 3 ↔ 4 ↔ [5] -> null

Why: Begin visiting nodes backward from last node

Step 7: Move backward to node 4

head -> 1 ↔ 2 ↔ 3 ↔ [4] ↔ 5 -> null

Why: Visit previous node in backward direction

Step 8: Move backward to node 3

head -> 1 ↔ 2 ↔ [3] ↔ 4 ↔ 5 -> null

Why: Continue backward traversal

Step 9: Move backward to node 2

head -> 1 ↔ [2] ↔ 3 ↔ 4 ↔ 5 -> null

Why: Keep moving backward

Step 10: Move backward to node 1 (head)

head -> [1] ↔ 2 ↔ 3 ↔ 4 ↔ 5 -> null

Why: Reached first node for backward traversal

Result:

Forward traversal: 1 -> 2 -> 3 -> 4 -> 5 -> null
Backward traversal: 5 -> 4 -> 3 -> 2 -> 1 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    Node* tail;
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = tail = newNode;
            return;
        }
        tail->next = newNode; // link current tail to new node
        newNode->prev = tail; // link new node back to current tail
        tail = newNode;       // update tail to new node
    }

    void traverseForward() {
        Node* curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next; // move forward
        }
        cout << "null" << endl;
    }

    void traverseBackward() {
        Node* curr = tail;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->prev; // move backward
        }
        cout << "null" << endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(1);
    dll.append(2);
    dll.append(3);
    dll.append(4);
    dll.append(5);

    cout << "Forward traversal: ";
    dll.traverseForward();

    cout << "Backward traversal: ";
    dll.traverseBackward();

    return 0;
}

tail->next = newNode; // link current tail to new node

connect current last node forward to new node

newNode->prev = tail; // link new node back to current tail

connect new node backward to previous last node

curr = curr->next; // move forward

advance pointer forward to next node

curr = curr->prev; // move backward

advance pointer backward to previous node

Output

Forward traversal: 1 -> 2 -> 3 -> 4 -> 5 -> null

Backward traversal: 5 -> 4 -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because traversal visits each of the n nodes once in forward or backward direction

Space: O(1) because traversal uses only a pointer variable without extra storage

vs Alternative: Compared to singly linked list, doubly linked list allows backward traversal easily without extra work

Edge Cases

Empty list

Traversal prints 'null' immediately without errors

DSA C++

while (curr) { ... } in traverseForward and traverseBackward

Single node list

Traversal prints the single node value then 'null' in both directions

DSA C++

while (curr) { ... } handles single node correctly

When to Use This Pattern

When you need to visit elements in both directions in a list, use doubly linked list traversal because it has pointers to both next and previous nodes.

Common Mistakes

Mistake: Trying to traverse backward in a singly linked list which has no previous pointers
Fix: Use a doubly linked list that stores previous pointers to enable backward traversal

Mistake: Not updating tail pointer when appending nodes, causing backward traversal to fail
Fix: Always update tail to the new last node after insertion

Summary

It visits all nodes in a doubly linked list from start to end and then from end to start.

Use it when you want to move through a list in both forward and backward directions easily.

The key is that each node links to both the next and previous nodes, allowing two-way movement.

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