Traversal of Circular Linked List in DSA C++ - Execution Trace

Concept Flow - Traversal of Circular Linked List

Start at head node

↓

Print current node data

↓

Move to next node

↓

Is current node head again?

Yes→Stop traversal

No↓

Repeat print and move

Start from the head node, print data, move to next node, and repeat until you reach the head again, completing the circle.

Execution Sample

DSA C++

Node* current = head;
do {
    cout << current->data << " -> ";
    current = current->next;
} while (current != head);

Traverse the circular linked list starting from head, printing each node's data until back at head.

Execution Table

Step	Operation	Current Node Data	Pointer Changes	Visual State
1	Start at head	10	current = head (10)	10 -> 20 -> 30 -> 40 -> (back to 10)
2	Print data	10	none	10 -> 20 -> 30 -> 40 -> (back to 10)
3	Move to next	20	current = current->next (20)	10 -> 20 -> 30 -> 40 -> (back to 10)
4	Print data	20	none	10 -> 20 -> 30 -> 40 -> (back to 10)
5	Move to next	30	current = current->next (30)	10 -> 20 -> 30 -> 40 -> (back to 10)
6	Print data	30	none	10 -> 20 -> 30 -> 40 -> (back to 10)
7	Move to next	40	current = current->next (40)	10 -> 20 -> 30 -> 40 -> (back to 10)
8	Print data	40	none	10 -> 20 -> 30 -> 40 -> (back to 10)
9	Move to next	10	current = current->next (10)	10 -> 20 -> 30 -> 40 -> (back to 10)
10	Check if current == head	10	none	Traversal complete

💡 Traversal stops when current node pointer returns to head node.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	Final
current	head (10)	20	30	40	10	10 (stop)

Key Moments - 3 Insights

Why do we use a do-while loop instead of a while loop?

Because we must process the head node first before checking if we returned to it. The execution_table shows printing at step 2 before the condition check at step 10.

What happens if the list has only one node?

The traversal prints that single node once and stops immediately after moving back to head, as shown by the condition current == head at step 10.

Why does traversal stop when current equals head again?

Because in a circular list, returning to head means we completed one full circle. The exit_note and step 10 in execution_table confirm this stopping condition.

Visual Quiz - 3 Questions

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

A 30

B 20

C 40

D 10

💡 Hint

Check the 'Pointer Changes' and 'Current Node Data' columns at step 5.

At which step does the traversal stop because current equals head again?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the 'Operation' column where traversal stops in the execution_table.

If the circular linked list had only one node, how many times would the print operation occur?

A 0 times

B 1 time

C 2 times

D Infinite times

💡 Hint

Refer to key_moments about single node traversal and the exit condition in execution_table.

Concept Snapshot

Traversal of Circular Linked List:
- Start at head node
- Print current node data
- Move to next node
- Repeat until back at head
- Use do-while loop to ensure head is processed
- Stops when current == head again

Full Transcript

Traversal of a circular linked list starts at the head node. We print the data of the current node, then move the pointer to the next node. This repeats until the pointer returns to the head node, indicating a full circle. A do-while loop is used to ensure the head node is processed before checking the stopping condition. The traversal stops when the current pointer equals the head again, preventing infinite loops. This process is shown step-by-step in the execution table, tracking the current node and pointer changes.

Practice

1. What is the main difference between traversing a circular linked list and a singly linked list?

easy

A. In a circular linked list, traversal stops at the last node with NULL pointer.

B. In a circular linked list, traversal requires a double pointer.

C. In a circular linked list, traversal stops when the starting node is reached again.

D. In a circular linked list, traversal is done backwards only.

Solution

1. Step 1: Understand traversal stopping condition for singly linked list

   In a singly linked list, traversal stops when the next pointer is NULL, indicating the end.

2. Step 2: Understand traversal stopping condition for circular linked list

   In a circular linked list, the last node points back to the first node, so traversal stops when we reach the starting node again to avoid infinite loop.

3. Final Answer:

   In a circular linked list, traversal stops when the starting node is reached again. -> Option C

4. Quick Check:

   Traversal stops at start node in circular list = B [OK]

Hint: Stop traversal when you reach the start node again [OK]

Common Mistakes:

• Stopping traversal at NULL pointer in circular list
• Not checking for start node to end traversal
• Assuming circular list traversal is backward

2. Which of the following is the correct syntax to traverse a circular linked list starting from node head in C++?

easy

A. do { /* process node */ head = head->next; } while(head != NULL);

B. do { /* process node */ head = head->next; } while(head != start);

C. while(head != NULL) { /* process node */ head = head->next; }

D. for(Node* temp = head; temp != NULL; temp = temp->next) { /* process node */ }

Solution

1. Step 1: Identify traversal loop type for circular linked list

   Traversal must use a do-while loop to process the start node before checking the condition.

2. Step 2: Check loop condition for circular list traversal

   The loop continues until the pointer returns to the start node, not NULL.

3. Final Answer:

   do { /* process node */ head = head->next; } while(head != start); -> Option B

4. Quick Check:

   Use do-while and check for start node to traverse circular list [OK]

Hint: Use do-while and check for start node, not NULL [OK]

Common Mistakes:

• Using while loop with NULL condition
• Using for loop with NULL condition
• Not processing the start node before condition check

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

#include <iostream>

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

int main() {
  Node n1{1, nullptr}, n2{2, nullptr}, n3{3, nullptr};
  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n1; // circular link

  Node* temp = &n1;
  do {
    std::cout << temp->data << " ";
    temp = temp->next;
  } while(temp != &n1);
  return 0;
}

medium

A. 1 2 3

B. 1 2 3 1

C. 1 2

D. Runtime error

Solution

1. Step 1: Understand the circular linked list structure

   Nodes 1, 2, 3 are linked circularly: 1->2->3->1.

2. Step 2: Trace the do-while traversal

   Traversal starts at node 1, prints 1, moves to 2, prints 2, moves to 3, prints 3, then moves back to 1 and stops.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Print nodes until back to start = 1 2 3 [OK]

Hint: Print nodes until you reach start node again [OK]

Common Mistakes:

• Printing the start node twice
• Stopping traversal early
• Confusing circular with NULL-terminated list

4. Identify the error in the following code snippet for traversing a circular linked list starting at head:

Node* temp = head;
while(temp != head) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. The loop misses printing the last node.

B. The loop causes infinite printing of nodes.

C. The code will cause a segmentation fault.

D. The loop never executes because condition is false initially.

Solution

1. Step 1: Analyze the loop condition and initialization

   temp is initialized to head, but the loop condition is while(temp != head), which is false at start.

2. Step 2: Understand loop execution

   Since condition is false initially, the loop body never executes and no nodes are printed.

3. Final Answer:

   The loop never executes because condition is false initially. -> Option D

4. Quick Check:

   temp == head at start, so while(temp != head) is false [OK]

Hint: Use do-while to process start node first in circular list [OK]

Common Mistakes:

• Using while instead of do-while for circular list
• Not processing the start node
• Assuming loop runs at least once

5. Given a circular linked list where each node contains an integer, write a C++ function to find the sum of all node values. Which approach correctly handles the circular nature without infinite loops?

hard

A. Use a do-while loop starting at head, add node data, move to next, stop when back at head.

B. Use a while loop with condition temp != nullptr to sum nodes.

C. Use a for loop from 0 to size-1, summing nodes by moving next pointer.

D. Use recursion without base case to sum nodes.

Solution

1. Step 1: Understand circular list traversal for summation

   Traversal must start at head and continue until we return to head to avoid infinite loops.

2. Step 2: Evaluate each option's approach

   Use a do-while loop starting at head, add node data, move to next, stop when back at head. uses do-while loop checking for return to head, correctly summing all nodes once. Use a while loop with condition temp != nullptr to sum nodes. uses nullptr which never occurs in circular list. Use a for loop from 0 to size-1, summing nodes by moving next pointer. assumes size known but size is not given. Use recursion without base case to sum nodes. causes infinite recursion without base case.

3. Final Answer:

   Use a do-while loop starting at head, add node data, move to next, stop when back at head. -> Option A

4. Quick Check:

   Do-while with head check sums circular list correctly [OK]

Hint: Use do-while and stop when pointer returns to head [OK]

Common Mistakes:

• Using nullptr condition in circular list
• Assuming known size without given data
• Using recursion without base case