Traversal of Circular Linked List in DSA Javascript

Mental Model

A circular linked list loops back to the start, so traversal means visiting each node once without going in circles forever.

Analogy: Imagine walking around a circular track with numbered markers. You start at marker 1 and walk forward, visiting each marker until you return to marker 1 again, then you stop.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), traverse and print all nodes

Goal: Visit each node exactly once and print its value

Step 1: start at head node with value 1

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

Why: We begin traversal from the head node

Step 2: print 1 and move curr to next node

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

Why: After visiting node 1, move to node 2

Step 3: print 2 and move curr to next node

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

Why: After visiting node 2, move to node 3

Step 4: print 3 and move curr to next node

1 -> 2 -> 3 -> [curr->1]

Why: After visiting node 3, move to node 1 again

Step 5: stop traversal because curr is back at head

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

Why: We have visited all nodes once, so stop to avoid infinite loop

Result:

1 -> 2 -> 3 -> back to 1 (traversal complete)

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class CircularLinkedList {
  constructor() {
    this.head = null;
  }

  // Add node to circular list for testing
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head; // points to itself
      return;
    }
    let curr = this.head;
    while (curr.next !== this.head) {
      curr = curr.next;
    }
    curr.next = newNode;
    newNode.next = this.head;
  }

  traverse() {
    if (!this.head) return;
    let curr = this.head;
    do {
      console.log(curr.value);
      curr = curr.next; // advance to next node
    } while (curr !== this.head); // stop when back at head
  }
}

// Driver code
const cll = new CircularLinkedList();
cll.append(1);
cll.append(2);
cll.append(3);
cll.traverse();

let curr = this.head;

start traversal at head node

do {

begin loop to visit nodes at least once

console.log(curr.value);

print current node's value

curr = curr.next;

advance curr to next node

} while (curr !== this.head);

stop traversal when curr returns to head to avoid infinite loop

Output

1

2

3

Complexity Analysis

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

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

vs Alternative: Compared to linear linked list traversal, circular traversal requires a stopping condition to avoid infinite loops, but time complexity remains O(n)

Edge Cases

empty list

traverse does nothing and prints nothing

DSA Javascript

if (!this.head) return;

single node list

prints the single node once and stops

DSA Javascript

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

When to Use This Pattern

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

Common Mistakes

Mistake: Using a while loop with condition curr != null causes infinite loop in circular list
Fix: Use a do-while loop and stop when curr returns to head node

Mistake: Not handling empty list causes errors
Fix: Check if head is null before traversal

Summary

It visits each node in a circular linked list exactly once without looping forever.

Use it when you need to process or print all nodes in a circular linked list.

The key is to stop traversal when you return to the starting node 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 requires a double pointer.

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

C. In a circular linked list, traversal stops when the last node's next is null.

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

Solution

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

   Traversal stops when the next pointer is null, indicating the end.

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

   Traversal stops when the traversal reaches the starting node again, since the list loops back.

3. Final Answer:

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

4. Quick Check:

   Stopping condition differs: null vs start node [OK]

Hint: Remember: circular list loops back to start node [OK]

Common Mistakes:

• Stopping traversal at null in circular list
• Assuming circular list traversal is backward only
• Confusing traversal conditions with doubly linked lists

2. Which of the following is the correct syntax to start traversing a circular linked list in JavaScript assuming head is the starting node?

easy

A. let current = head; do { /* process current */ current = current.next; } while(current !== head);

B. let current = head; while(current.next !== null) { /* process current */ current = current.next; }

C. for(let current = head; current !== null; current = current.next) { /* process current */ }

D. let current = head; while(current !== null) { /* process current */ current = current.next; }

Solution

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

   Traversal must continue until current node loops back to head, so a do-while loop is suitable.

2. Step 2: Check syntax correctness

   let current = head; do { /* process current */ current = current.next; } while(current !== head); uses do-while with condition current !== head, correctly handling circular traversal.

3. Final Answer:

   let current = head; do { /* process current */ current = current.next; } while(current !== head); -> Option A

4. Quick Check:

   Use do-while to handle circular traversal [OK]

Hint: Use do-while to ensure at least one iteration [OK]

Common Mistakes:

• Using while with null condition in circular list
• Forgetting to process the head node
• Using for loop with null condition in circular list

3. What will be the output of the following code snippet?

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

const head = new Node(1);
const second = new Node(2);
const third = new Node(3);

head.next = second;
second.next = third;
third.next = head; // circular link

let current = head;
do {
  console.log(current.data);
  current = current.next;
} while(current !== head);

medium

A. 1 2 3 1

B. Error: Infinite loop

C. 1 2 3 1 2 3 ... (infinite loop)

D. 1 2 3

Solution

1. Step 1: Understand the circular linked list structure

   Nodes 1, 2, 3 are linked circularly: third.next points back to head.

2. Step 2: Trace the do-while loop output

   Loop prints current.data and moves current to next until current equals head again. It prints 1, 2, 3 then stops.

3. Final Answer:

   1 2 3 -> Option D

4. Quick Check:

   Loop prints nodes once until back to start [OK]

Hint: do-while prints all nodes once in circular list [OK]

Common Mistakes:

• Expecting infinite loop output
• Printing head node twice
• Confusing do-while with while loop behavior

4. Identify the error in the following circular linked list traversal code:

let current = head;
while(current !== head) {
  console.log(current.data);
  current = current.next;
}

medium

A. The loop skips the last node.

B. The loop causes an infinite loop.

C. The loop never executes because current equals head initially.

D. The code throws a runtime error due to null reference.

Solution

1. Step 1: Analyze initial condition of the while loop

   current is initialized to head, so current !== head is false at start.

2. Step 2: Understand loop execution

   Since condition is false initially, loop body never executes, so no traversal happens.

3. Final Answer:

   The loop never executes because current equals head initially. -> Option C

4. Quick Check:

   While condition false at start means zero iterations [OK]

Hint: Check initial loop condition carefully in circular traversal [OK]

Common Mistakes:

• Using while instead of do-while for circular lists
• Assuming loop runs at least once
• Ignoring initial condition impact

5. Given a circular linked list where each node contains an integer, how would you find the sum of all node values without getting stuck in an infinite loop?

hard

A. Use a do-while loop starting at head, add node values, stop when current equals head again.

B. Use a while loop checking for current.next !== null to sum values.

C. Use recursion without a base case to sum values.

D. Traverse nodes until current is null, summing values.

Solution

1. Step 1: Choose traversal method suitable for circular list

   Use do-while loop to ensure all nodes are visited once, stopping when current returns to head.

2. Step 2: Sum node values during traversal

   Initialize sum to 0, add current.data each iteration, move to next node until loop ends.

3. Final Answer:

   Use a do-while loop starting at head, add node values, stop when current equals head again. -> Option A

4. Quick Check:

   Do-while loop prevents infinite traversal in circular list [OK]

Hint: Stop traversal when current node equals start node [OK]

Common Mistakes:

• Using null check in circular list traversal
• Forgetting to stop at head node again
• Using recursion without base case causing infinite calls