Traversal of Circular Linked List in DSA C++ - Time & Space Complexity

Time Complexity: Traversal of Circular Linked List

O(n)

Understanding Time Complexity

We want to understand how long it takes to go through all elements in a circular linked list.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void traverseCircularList(Node* head) {
    if (!head) return;
    Node* current = head;
    do {
        // Process current node
        current = current->next;
    } while (current != head);
}
    

This code visits each node in a circular linked list exactly once, starting from the head.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The do-while loop that moves through each node.
• How many times: Exactly once per node, until it returns to the start.

How Execution Grows With Input

As the number of nodes increases, the loop runs once for each node.

Input Size (n)	Approx. Operations
10	10
100	100
1000	1000

Pattern observation: The operations grow directly in proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to traverse grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Traversal of a circular linked list takes infinite time because it loops forever."

[OK] Correct: The code stops when it returns to the starting node, so it visits each node only once and then ends.

Interview Connect

Understanding traversal time helps you explain how linked lists work and shows you can reason about loops and stopping conditions clearly.

Self-Check

"What if the list had a cycle but was not circularly linked (no guaranteed start node)? How would the time complexity change?"

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