Traversal and Printing a Linked List in DSA C++ - Execution Trace

Concept Flow - Traversal and Printing a Linked List

Start at head node

↓

Is current node NULL?

Yes→Stop traversal

No↓

Print current node data

↓

Move to next node

↩Back to check current node

Start from the head node, print its data, move to the next node, and repeat until the end (NULL) is reached.

Execution Sample

DSA C++

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

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

This code prints all elements of a linked list from head to end, showing arrows between nodes and ending with null.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start at head	10	current = head (points to node with 10)	10 -> null
2	Print current data	10	No pointer change	10 -> null
3	Move to next node	20	current = current->next (points to node with 20)	10 -> 20 -> null
4	Print current data	20	No pointer change	10 -> 20 -> null
5	Move to next node	30	current = current->next (points to node with 30)	10 -> 20 -> 30 -> null
6	Print current data	30	No pointer change	10 -> 20 -> 30 -> null
7	Move to next node	NULL	current = current->next (nullptr)	10 -> 20 -> 30 -> null
8	Check current node	NULL	Traversal ends	10 -> 20 -> 30 -> null

💡 Traversal stops when current node becomes NULL, meaning end of list reached.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
current	points to node with 10	points to node with 20	points to node with 30	nullptr	nullptr

Key Moments - 3 Insights

Why do we check if current is NULL before printing?

Because when current is NULL, it means we reached the end of the list and there is no data to print. See execution_table step 8 where traversal stops.

Why do we move current to current->next after printing?

To advance to the next node in the list so we can print all nodes one by one. This is shown in steps 3, 5, and 7 in the execution_table.

What does the visual state '10 -> 20 -> 30 -> null' represent?

It shows the linked list nodes in order with arrows pointing to the next node, ending with null to indicate the list end. This is the printed output after traversal.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current after step 5?

A Points to node with 30

B Points to node with 20

C Points to node with 10

D nullptr

💡 Hint

Check the 'Pointer Changes' column at step 5 in the execution_table.

At which step does the traversal stop because current becomes NULL?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'Current Node Data' and 'Operation' columns in the execution_table for when current is NULL and traversal ends.

If the list had only one node with data 10, how many times would the loop print data?

A 0 times

B 1 time

C 2 times

D 3 times

💡 Hint

Refer to the variable_tracker and execution_table to see how many nodes are visited and printed.

Concept Snapshot

Traversal and Printing a Linked List:
- Start at head node
- While current node is not NULL:
  - Print current node data
  - Move to next node
- End when current is NULL
- Output format: data -> data -> ... -> null

Full Transcript

Traversal and printing of a linked list means starting at the head node and moving through each node one by one. At each node, we print its data and then move to the next node using the next pointer. This continues until we reach a node that points to NULL, which means the end of the list. The printed output shows all node data separated by arrows and ends with null to indicate the list end.

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