Traversal of Circular Linked List in DSA C++

Mental Model

A circular linked list loops back to the start, so traversal means visiting nodes until we return to the first node.

Analogy: Imagine walking around a circular track; you keep moving forward until you reach the starting point again.

head -> 1 -> 2 -> 3 ->
↑                   ↓
← ← ← ← ← ← ← ← ← ← ←

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, circular (3 points back to 1)

Goal: Print all nodes once by traversing the circular linked list

Step 1: start at head node with value 1

head -> [curr->1] -> 2 -> 3 -> back to 1

Why: We begin traversal from the first node

Step 2: print 1 and move curr to next node 2

head -> 1 -> [curr->2] -> 3 -> back to 1

Why: Visit current node and advance to next

Step 3: print 2 and move curr to next node 3

head -> 1 -> 2 -> [curr->3] -> back to 1

Why: Continue visiting nodes in order

Step 4: print 3 and move curr to next node which is head (1)

head -> [curr->1] -> 2 -> 3 -> back to 1

Why: Reached last node, next is head again

Step 5: stop traversal because curr is back at head

head -> 1 -> 2 -> 3 -> back to 1

Why: To avoid infinite loop, stop when we return to start

Result:

1 -> 2 -> 3 -> (back to head)

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

void traverseCircularList(Node* head) {
    if (!head) return; // empty list
    Node* curr = head;
    do {
        cout << curr->data << " ";
        curr = curr->next; // advance to next node
    } while (curr != head); // stop when back at head
    cout << endl;
}

int main() {
    // Create circular linked list: 1 -> 2 -> 3 -> back to 1
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    head->next = second;
    second->next = third;
    third->next = head; // circular link

    traverseCircularList(head);

    // Free memory (not required for this example but good practice)
    third->next = nullptr; // break circular link to avoid infinite loop in deletion
    delete third;
    delete second;
    delete head;

    return 0;
}

if (!head) return; // empty list

handle empty list to avoid errors

Node* curr = head;

start traversal at head node

do {

begin loop to visit nodes at least once

cout << curr->data << " ";

print current node's data

curr = curr->next; // advance to next node

move to next node in the list

} while (curr != head); // stop traversal when we return to starting node

stop traversal when we return to starting node

Output

1 2 3 

Complexity Analysis

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

Space: O(1) because we use only a few pointers regardless of list size

vs Alternative: Compared to linear linked list traversal, circular traversal requires a stopping condition to avoid infinite loops

Edge Cases

empty list (head is nullptr)

function returns immediately without printing

DSA C++

if (!head) return; // empty list

single node circular list (node points to itself)

prints the single node once and stops

DSA C++

do { ... } while (curr != head);

When to Use This Pattern

When you see a linked list where the last node points back to the first, use circular traversal with a do-while loop to visit all nodes exactly once.

Common Mistakes

Mistake: Using a while loop with condition curr != nullptr causes infinite loop because circular list never ends with nullptr
Fix: Use a do-while loop and stop when curr returns to head

Summary

It visits every node in a circular linked list exactly once by looping until it returns to the start.

Use it when you have a circular linked list and want to process or print all nodes.

The key insight is to stop traversal when you reach the starting node again to avoid infinite loops.

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