Traversal Forward and Backward in DSA C++ - Build from Scratch

Traversal Forward and Backward

📖 Scenario: Imagine you have a train with several connected carriages. You want to check the order of carriages from the front to the back and then from the back to the front.

🎯 Goal: You will create a doubly linked list representing the train carriages and then traverse it forward and backward to see the order of carriages.

📋 What You'll Learn

Create a doubly linked list with exactly 4 nodes containing carriage numbers 101, 102, 103, and 104

Create a pointer called head pointing to the first carriage

Create a pointer called tail pointing to the last carriage

Traverse the list forward using current pointer and print carriage numbers separated by ->

Traverse the list backward using current pointer and print carriage numbers separated by ->

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in real-world applications like music players to move forward and backward through songs, or in web browsers to go forward and back through pages.

💼 Career

Understanding traversal in doubly linked lists is important for software developers working with data structures, memory management, and building efficient navigation systems.

1

Create the doubly linked list nodes

Create a struct called Node with int data, Node* next, and Node* prev. Then create four nodes named node1, node2, node3, and node4 with data 101, 102, 103, and 104 respectively. Set their next and prev pointers to connect them in order.

DSA C++

// Define Node struct and create 4 nodes with data 101, 102, 103, 104
// Connect nodes using next and prev pointers
// Your code here

Hint

Think of each node as a carriage. Connect each carriage's next to the next carriage and prev to the previous carriage.

2

Create head and tail pointers

Create two pointers called head and tail. Set head to point to node1 and tail to point to node4.

DSA C++

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

Node node1 = {101, nullptr, nullptr};
Node node2 = {102, nullptr, nullptr};
Node node3 = {103, nullptr, nullptr};
Node node4 = {104, nullptr, nullptr};

node1.next = &node2;
node2.prev = &node1;
node2.next = &node3;
node3.prev = &node2;
node3.next = &node4;
node4.prev = &node3;

// Create head and tail pointers
// Your code here

Hint

Head points to the first carriage, tail points to the last carriage.

3

Traverse forward and backward

Create a pointer called current. Use a while loop to traverse forward from head to tail, printing each current->data followed by " -> " except after the last node. Then use another while loop to traverse backward from tail to head, printing each current->data followed by " -> " except after the last node.

DSA C++

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

Node node1 = {101, nullptr, nullptr};
Node node2 = {102, nullptr, nullptr};
Node node3 = {103, nullptr, nullptr};
Node node4 = {104, nullptr, nullptr};

node1.next = &node2;
node2.prev = &node1;
node2.next = &node3;
node3.prev = &node2;
node3.next = &node4;
node4.prev = &node3;

Node* head = &node1;
Node* tail = &node4;

// Traverse forward and backward and print data
// Your code here

Hint

Use current to move forward using next pointers and backward using prev pointers. Print the data with arrows between nodes.

4

Print the traversal output

Add the necessary #include directives and main function to run the code. Print the forward traversal on one line and the backward traversal on the next line exactly as shown.

DSA C++

// Add #include and main function
// Your code here

Hint

Make sure to include <iostream> and wrap your code inside int main(). The output should show forward traversal on the first line and backward traversal on the second line.

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