Traversal and Printing a Linked List in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of traversing a linked list?

To visit each node in the linked list one by one, usually to read or process the data stored in each node.

beginner

In a singly linked list, how do you move from one node to the next?

By following the 'next' pointer/reference in the current node to reach the next node in the list.

beginner

What condition tells you that you have reached the end of a linked list during traversal?

When the 'next' pointer/reference of the current node is null (or nullptr in C++), it means you have reached the end.

intermediate

Why is it important to check for null before accessing the next node in a linked list?

To avoid errors or crashes by trying to access a node that does not exist (null pointer dereference).

beginner

What is the output format when printing a linked list like 1 -> 2 -> 3 -> null?

It shows the sequence of node values connected by arrows, ending with 'null' to indicate the list's end.

What does the 'next' pointer in a linked list node represent?

A The address of the next node in the list

B The value stored in the node

C The address of the previous node

D The total number of nodes

The 'next' pointer holds the address of the next node, allowing traversal through the list.

How do you know when to stop traversing a singly linked list?

A When the current node points to itself

B When the current node's value is zero

C After visiting 10 nodes

D When the current node's next pointer is null

Traversal stops when the next pointer is null, meaning no more nodes follow.

Which of these is the correct way to print a linked list node values in order?

A Start at head, print value, move to next until null

B Start at tail, print value, move to previous until null

C Print all values at once without traversal

D Print values randomly

You start at the head and move forward using next pointers until you reach null.

What happens if you forget to check for null before accessing the next node?

A The list will reverse

B The list will print correctly

C Program may crash due to null pointer access

D You will skip nodes

Accessing a null pointer causes runtime errors or crashes.

What is the time complexity of traversing a linked list with n nodes?

A O(1)

B O(n)

C O(n^2)

D O(log n)

You visit each node once, so time grows linearly with n.

Explain step-by-step how to traverse and print all elements of a singly linked list.

Think about visiting each node one by one until the end.

Describe why checking for null is important during linked list traversal and what could happen if you don't.

Consider what happens if you try to use a pointer that points nowhere.

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