Traversal of Circular Linked List in DSA Typescript

Mental Model

A circular linked list loops back to the start, so traversal keeps going 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), traverse and print all nodes

Goal: Visit each node exactly once and print its value

Step 1: Start at head node with value 1

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

Why: We begin traversal from the first node

Step 2: Print value 1 and move curr to next node

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

Why: Visit next node to continue traversal

Step 3: Print value 2 and move curr to next node

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

Why: Keep moving forward to visit all nodes

Step 4: Print value 3 and move curr to next node

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

Why: Curr loops back to head, traversal should stop now

Result:

1 -> 2 -> 3 -> (back to head, stop traversal)

Annotated Code

DSA Typescript

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

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

  // Create circular list from array for testing
  createFromArray(arr: number[]): void {
    if (arr.length === 0) return;
    this.head = new Node(arr[0]);
    let curr = this.head;
    for (let i = 1; i < arr.length; i++) {
      curr.next = new Node(arr[i]);
      curr = curr.next;
    }
    curr.next = this.head; // make it circular
  }

  traverse(): void {
    if (!this.head) return; // empty list
    let curr: Node | null = this.head;
    do {
      console.log(curr.value);
      curr = curr.next;
    } while (curr !== this.head);
  }
}

// Driver code
const cll = new CircularLinkedList();
cll.createFromArray([1, 2, 3]);
cll.traverse();

if (!this.head) return; // empty list

handle empty list by stopping traversal

let curr: Node | null = 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 to next node

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

stop when we return to head

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: Traversal of a circular list is similar to a normal list but requires a check to stop when we loop back to head, avoiding infinite loops

Edge Cases

empty list

traversal does nothing and exits immediately

DSA Typescript

if (!this.head) return; // empty list

single node circular list

prints the single node once and stops

DSA Typescript

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 traversal with a stop condition checking if you returned to the start to avoid infinite loops.

Common Mistakes

Mistake: Using a while loop without checking if current node equals head, causing infinite loop
Fix: Use a do-while loop and stop when current node equals head

Summary

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

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

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

Practice

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

easy

A. In a circular linked list, nodes cannot be traversed.

B. In a circular linked list, nodes have two pointers instead of one.

C. In a circular linked list, nodes are stored in an array.

D. In a circular linked list, the last node points back to the first node.

Solution

1. Step 1: Understand linked list types

   A regular singly linked list ends with a node pointing to null, while a circular linked list connects the last node back to the first node.

2. Step 2: Identify the key difference

   This connection makes the list circular, allowing traversal to loop indefinitely.

3. Final Answer:

   In a circular linked list, the last node points back to the first node. -> Option D

4. Quick Check:

   Circular linked list loops back = A [OK]

Hint: Last node points to first in circular lists [OK]

Common Mistakes:

• Thinking circular lists have two pointers per node
• Confusing circular list with doubly linked list
• Assuming nodes are stored in arrays

2. Which of the following is the correct way to start traversing a circular linked list in TypeScript?

easy

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

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

C. for(let i = 0; i < length; i++) { /* process node */ }

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

Solution

1. Step 1: Understand traversal of circular linked list

   Traversal must start at head and continue until we return to head again, using a do-while loop to ensure at least one iteration.

2. Step 2: Check each option

   let current = head; do { /* process current */ current = current.next; } while(current !== head); uses do-while with condition current !== head, which correctly traverses all nodes once. Others either check for null (wrong for circular) or use for loop without node references.

3. Final Answer:

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

4. Quick Check:

   Use do-while until back to head [OK]

Hint: Use do-while loop until current equals head [OK]

Common Mistakes:

• Using while loop with null condition in circular list
• Using for loop without node references
• Stopping traversal too early

3. What will be the output of the following TypeScript code that traverses a circular linked list with nodes containing values 10, 20, 30?

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

const n1 = new Node(10);
const n2 = new Node(20);
const n3 = new Node(30);
n1.next = n2;
n2.next = n3;
n3.next = n1; // circular link

let current = n1;
do {
  console.log(current.value);
  current = current.next!;
} while (current !== n1);

medium

A. 20 30 10

B. 10 20 30 10

C. 10 20 30

D. 10 20

Solution

1. Step 1: Understand the circular linked list structure

   Nodes are linked as 10 -> 20 -> 30 -> back to 10, forming a circle.

2. Step 2: Trace the traversal loop

   Starting at n1 (10), the do-while prints 10, moves to 20, prints 20, moves to 30, prints 30, then moves back to 10. Loop stops because current === n1.

3. Final Answer:

   10 20 30 -> Option C

4. Quick Check:

   Print nodes once until back to start [OK]

Hint: Print nodes until current equals head once [OK]

Common Mistakes:

• Printing the first node twice
• Stopping traversal before last node
• Confusing circular with linear traversal

4. Identify the error in this TypeScript code snippet for traversing a circular linked list:

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

medium

A. The code skips the first node during traversal.

B. The loop never runs because current equals head initially.

C. The code throws a null pointer exception.

D. The loop runs infinitely because condition is always true.

Solution

1. Step 1: Analyze the loop condition

   The while loop condition is current !== head, but current starts as head, so condition is false immediately.

2. Step 2: Understand loop execution

   Since condition is false at start, loop body never executes, so no nodes are processed.

3. Final Answer:

   The loop never runs because current equals head initially. -> Option B

4. Quick Check:

   While loop with current !== head fails at start [OK]

Hint: Use do-while to include first node in circular traversal [OK]

Common Mistakes:

• Using while instead of do-while for circular lists
• Assuming loop runs at least once
• Not checking initial condition carefully

5. Given a circular linked list where each node contains a number, write a TypeScript 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 values, stop when current equals head again.

B. Use a while loop checking current !== null, add values until null is reached.

C. Use a for loop with fixed iterations equal to list length, add values each iteration.

D. Use recursion without a base case to sum nodes.

Solution

1. Step 1: Understand circular list traversal for summation

   Since the list is circular, traversal must stop when we return to the starting node to avoid infinite loops.

2. Step 2: Evaluate each approach

   Use a do-while loop starting at head, add values, stop when current equals head again. uses a do-while loop starting at head and stops when current equals head again, correctly summing all nodes once. Use a while loop checking current !== null, add values until null is reached. checks for null which never occurs in circular lists. Use a for loop with fixed iterations equal to list length, add values each iteration. requires knowing length, which may not be available. Use recursion without a base case to sum nodes. causes infinite recursion.

3. Final Answer:

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

4. Quick Check:

   Do-while loop with stop at head = C [OK]

Hint: Stop traversal when current equals head to avoid infinite loop [OK]

Common Mistakes:

• Using null check in circular list traversal
• Recursing without base case causing stack overflow
• Assuming list length is always known