Traversal of Circular Linked List in DSA Javascript - Build from Scratch

Traversal of Circular Linked List

📖 Scenario: You are working on a music playlist app where songs are arranged in a circular linked list. The list loops back to the first song after the last one, allowing continuous play.

🎯 Goal: Build a program to traverse a circular linked list of songs and print each song's name once.

📋 What You'll Learn

Create a circular linked list with exactly 3 nodes named head, each node having a song property with values 'Song A', 'Song B', and 'Song C'.

Add a variable called current to help traverse the list.

Use a do...while loop to traverse the circular linked list starting from head and print each song name exactly once.

Print the song names in order separated by ' -> ' and end with ' -> null'.

💡 Why This Matters

🌍 Real World

Circular linked lists are used in music players, round-robin schedulers, and multiplayer games to cycle through items continuously.

💼 Career

Understanding circular linked lists helps in designing efficient data structures for real-time systems and applications requiring cyclic iteration.

1

Create Circular Linked List Nodes

Create three nodes named node1, node2, and node3 as objects with a song property set to 'Song A', 'Song B', and 'Song C' respectively. Link them to form a circular linked list by setting their next properties. Finally, create a variable head pointing to node1.

DSA Javascript

# Your code here

Hint

Think of each node as a song with a pointer to the next song. The last song points back to the first to make it circular.

2

Add Traversal Pointer

Create a variable called current and set it equal to head. This will help us move through the circular linked list.

DSA Javascript

const node1 = { song: 'Song A' };
const node2 = { song: 'Song B' };
const node3 = { song: 'Song C' };
node1.next = node2;
node2.next = node3;
node3.next = node1;
const head = node1;

# Your code here

Hint

Use let current = head; to start traversal from the first node.

3

Traverse Circular Linked List

Use a do...while loop to traverse the circular linked list starting from current. Inside the loop, print the song property of the current node followed by ' -> '. Move current to the next node. Stop the loop when current is again equal to head.

DSA Javascript

const node1 = { song: 'Song A' };
const node2 = { song: 'Song B' };
const node3 = { song: 'Song C' };
node1.next = node2;
node2.next = node3;
node3.next = node1;
const head = node1;

let current = head;

# Your code here

Hint

Use do...while so the loop runs at least once and stops when you return to the head.

4

Print End of Traversal

After the loop, print 'null' to indicate the end of the traversal.

DSA Javascript

const node1 = { song: 'Song A' };
const node2 = { song: 'Song B' };
const node3 = { song: 'Song C' };
node1.next = node2;
node2.next = node3;
node3.next = node1;
const head = node1;

let current = head;
do {
    process.stdout.write(current.song + ' -> ');
    current = current.next;
} while (current !== head);

# Your code here

Hint

Use console.log('null'); after the loop to show the end.

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