Traversal of Circular Linked List in DSA Typescript - Execution Trace

Concept Flow - Traversal of Circular Linked List

Start at head node

↓

Visit current node and process data

↓

Move to next node

↓

Check if current node is head again?

No→Repeat visit

Yes↓

Stop traversal

Start from the head node, visit each node, move to the next, and stop when you return to the head.

Execution Sample

DSA Typescript

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

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

Execution Table

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

💡 Traversal stops when current node is head again after full circle

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
current.data	1	2	3	4	1	Traversal ends
current	head (node 1)	node 2	node 3	node 4	node 1	Traversal ends

Key Moments - 3 Insights

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

Because we must visit the head node first before checking if we returned to it, as shown in steps 1 and 10 in the execution_table.

What happens if the list has only one node?

The traversal prints that single node once and stops immediately after, since current.next points back to head, similar to step 9 and 10.

Why does traversal stop when current equals head again?

Because that means we completed a full circle visiting all nodes once, as shown in step 10 where current is head and traversal stops.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current.data at step 5?

A 3

B 2

C 1

D 4

💡 Hint

Check the 'Current Node Data' column at step 5 in the execution_table.

At which step does the traversal move from node 4 back to node 1?

A Step 8

B Step 9

C Step 7

D Step 10

💡 Hint

Look at 'Pointer Changes' and 'Current Node Data' columns around steps 8 and 9.

If the list had only one node, how many times would the loop run?

A 0 times

B 2 times

C 1 time

D Infinite times

💡 Hint

Refer to key_moments about single node traversal and the do-while loop behavior.

Concept Snapshot

Traversal of Circular Linked List:
- Start at head node
- Visit and process current node
- Move to next node
- Stop when current node is head again
- Use do-while loop to ensure head is processed first

Full Transcript

Traversal of a circular linked list starts at the head node. We visit the current node's data, 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 the stopping condition is checked. If the list has only one node, the traversal prints it once and stops immediately after. This process ensures every node is visited exactly once in a circular linked list.

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