Traversal and Printing a Linked List in DSA C++

Mental Model

Go through each item in the list one by one from start to end and show its value.

Analogy: Like reading a line of people holding hands, looking at each person's face in order until the last person.

head -> [1] -> [2] -> [3] -> null
          ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Print all values in the list in order separated by arrows

Step 1: Start at the head node with value 1

head -> [1] -> [2] -> [3] -> null
          ↑ current

Why: We begin traversal from the first node

Step 2: Print value 1 and move current to next node

head -> [1] -> [2] -> [3] -> null
                ↑ current

Why: After printing, move to the next node to continue

Step 3: Print value 2 and move current to next node

head -> [1] -> [2] -> [3] -> null
                      ↑ current

Why: Continue printing each node's value in order

Step 4: Print value 3 and move current to null (end)

head -> [1] -> [2] -> [3] -> null
                            ↑ current

Why: Reached the last node, print its value and end traversal

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Node class for linked list
class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Function to print linked list
void printList(Node* head) {
    Node* current = head; // start at head
    while (current != nullptr) { // traverse until end
        cout << current->data << " -> "; // print current node's data
        current = current->next; // move to next node
    }
    cout << "null" << endl; // end of list
}

int main() {
    // Create linked list 1->2->3->null
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    printList(head); // print the list
    return 0;
}

Node* current = head; // start at head

initialize traversal pointer at the first node

while (current != nullptr) { // traverse until end

continue until we reach the end of the list

cout << current->data << " -> "; // print current node's data

output the current node's value followed by arrow

current = current->next; // move to next node

advance pointer to next node to continue traversal

cout << "null" << endl; // end of list

print null to indicate end of list

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit each of the n nodes exactly once

Space: O(1) because we only use a fixed amount of extra space for traversal

vs Alternative: Compared to recursive printing which uses O(n) space on call stack, this iterative approach is more space efficient

Edge Cases

empty list (head is nullptr)

prints 'null' immediately without errors

DSA C++

while (current != nullptr) {

single node list

prints the single node value followed by 'null'

DSA C++

while (current != nullptr) {

When to Use This Pattern

When you need to visit or display every element in a linked list in order, use traversal by moving from head to next nodes until null.

Common Mistakes

Mistake: Not updating the current pointer inside the loop causing infinite loop
Fix: Add 'current = current->next;' inside the while loop to move forward

Mistake: Printing 'null' inside the loop instead of after traversal ends
Fix: Print 'null' only after the loop finishes to indicate list end

Summary

It goes through each node in the linked list and prints its value in order.

Use it when you want to see or process all elements in a linked list from start to end.

The key is to keep moving from one node to the next until you reach the end (null).

Practice

1. What is the main purpose of traversing a linked list in data structures?

easy

A. To delete all nodes at once

B. To reverse the linked list automatically

C. To create a new linked list

D. To visit each node and access its data

Solution

1. Step 1: Understand traversal meaning

   Traversal means visiting each node one by one in the linked list.

2. Step 2: Purpose of traversal

   The main goal is to access or process the data stored in each node during the visit.

3. Final Answer:

   To visit each node and access its data -> Option D

4. Quick Check:

   Traversal = Visit nodes [OK]

Hint: Traversal means visiting nodes one by one [OK]

Common Mistakes:

• Confusing traversal with deletion
• Thinking traversal creates new lists
• Assuming traversal reverses the list

2. Which of the following is the correct syntax to start traversing a singly linked list in C++ if head is the pointer to the first node?

easy

A. Node* current = head;

B. Node current = head;

C. Node* current = &head;

D. Node current = *head;

Solution

1. Step 1: Understand pointer usage

   In C++, linked list nodes are accessed via pointers. head is a pointer to the first node.

2. Step 2: Correct pointer assignment

   To traverse, we create a pointer current and assign it to head directly: Node* current = head;

3. Final Answer:

   Node* current = head; -> Option A

4. Quick Check:

   Use pointer to start traversal [OK]

Hint: Use pointer assignment to start traversal [OK]

Common Mistakes:

• Using object instead of pointer
• Taking address of head incorrectly
• Dereferencing head wrongly

3. What will be the output of the following C++ code snippet that prints a linked list?

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

int main() {
  Node n3 = {3, nullptr};
  Node n2 = {2, &n3};
  Node n1 = {1, &n2};
  Node* head = &n1;

  Node* current = head;
  while (current != nullptr) {
    std::cout << current->data << " -> ";
    current = current->next;
  }
  std::cout << "null" << std::endl;
  return 0;
}

medium

A. null -> 1 -> 2 -> 3

B. 3 -> 2 -> 1 -> null

C. 1 -> 2 -> 3 -> null

D. 1 2 3 null

Solution

1. Step 1: Trace node connections

   Node n1 points to n2, n2 points to n3, n3 points to nullptr (end).

2. Step 2: Follow the while loop output

   The loop prints data of current node then moves to next. So prints 1, then 2, then 3, then stops.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option C

4. Quick Check:

   Print nodes in order from head [OK]

Hint: Follow next pointers from head until nullptr [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing '->' arrows in output
• Not printing 'null' at the end

4. Identify the error in the following code snippet that attempts to print a linked list:

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

void printList(Node* head) {
  Node* current = head;
  while (current->next != nullptr) {
    std::cout << current->data << " -> ";
    current = current->next;
  }
  std::cout << "null" << std::endl;
}

medium

A. The loop condition should be current != nullptr, not current->next != nullptr

B. The print statement should be after the loop

C. The function should return an int

D. The pointer current should be declared as Node current, not Node* current

Solution

1. Step 1: Analyze loop condition

   The loop stops when current->next is nullptr, so it skips printing the last node's data.

2. Step 2: Correct loop condition

   It should check current != nullptr to print all nodes including the last one.

3. Final Answer:

   The loop condition should be current != nullptr, not current->next != nullptr -> Option A

4. Quick Check:

   Loop until current is nullptr to print all nodes [OK]

Hint: Loop until current is nullptr to include last node [OK]

Common Mistakes:

• Stopping loop too early missing last node
• Wrong pointer type declaration
• Misplacing print statement

5. Given a singly linked list, how would you modify the traversal code to print the list in reverse order without changing the list structure or using recursion?

hard

A. Traverse normally and print nodes as you go

B. Use a stack to store nodes during traversal, then pop and print

C. Reverse the list first, then print

D. Use two pointers to print backwards

Solution

1. Step 1: Understand constraints

   We cannot change the list or use recursion, so reversing pointers or recursive calls are not allowed.

2. Step 2: Use auxiliary data structure

   Use a stack to push each node's data during traversal, then pop from stack to print in reverse order.

3. Final Answer:

   Use a stack to store nodes during traversal, then pop and print -> Option B

4. Quick Check:

   Stack reverses order without modifying list [OK]

Hint: Use stack to reverse print without changing list [OK]

Common Mistakes:

• Trying to reverse list pointers directly
• Using recursion despite restriction
• Assuming two pointers can print backwards