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

Traversal of Circular Linked List

📖 Scenario: Imagine you have a group of friends sitting around a round table. You want to greet each friend one by one, starting from a specific person and going around the table until you come back to the same person.

🎯 Goal: You will create a circular linked list representing friends sitting around a table, then write code to visit each friend exactly once in order.

📋 What You'll Learn

Create a circular linked list with exactly 4 nodes named 'Alice', 'Bob', 'Charlie', and 'Diana'.

Add a variable to keep track of the starting node called head.

Write a traversal loop that visits each node starting from head and stops after visiting all nodes once.

Print the names of the friends in the order they are visited.

💡 Why This Matters

🌍 Real World

Circular linked lists are useful in real-world situations like managing players in a board game turn order or scheduling tasks that repeat in a cycle.

💼 Career

Understanding circular linked lists helps in software development roles that involve data structure design, game development, and systems programming where cyclic data flows are common.

1

Create Circular Linked List Nodes

Create a class called Node with a name property of type string and a next property of type Node | null. Then create four nodes named alice, bob, charlie, and diana with names 'Alice', 'Bob', 'Charlie', and 'Diana' respectively.

DSA Typescript

// Define Node class and create four nodes named alice, bob, charlie, and diana
// Your code here

Hint

Define a class with name and next properties. Then create four instances with the given names.

2

Link Nodes to Form Circular List

Link the nodes to form a circular linked list by setting alice.next = bob, bob.next = charlie, charlie.next = diana, and diana.next = alice. Also, create a variable called head and set it to alice.

DSA Typescript

class Node {
  name: string;
  next: Node | null;

  constructor(name: string) {
    this.name = name;
    this.next = null;
  }
}

const alice = new Node('Alice');
const bob = new Node('Bob');
const charlie = new Node('Charlie');
const diana = new Node('Diana');

// Link nodes to form a circular linked list and set head to alice
// Your code here

Hint

Set each node's next to the next friend, and the last node's next back to the first node. Then assign head to the first node.

3

Traverse the Circular Linked List

Create a variable called current and set it to head. Use a do-while loop to visit each node starting from current. Inside the loop, print the name of the current node, then move current to current.next. Stop the loop when current is equal to head again.

DSA Typescript

class Node {
  name: string;
  next: Node | null;

  constructor(name: string) {
    this.name = name;
    this.next = null;
  }
}

const alice = new Node('Alice');
const bob = new Node('Bob');
const charlie = new Node('Charlie');
const diana = new Node('Diana');

alice.next = bob;
bob.next = charlie;
charlie.next = diana;
diana.next = alice;

const head = alice;

// Traverse the circular linked list and print each name
// Your code here

Hint

Use a do-while loop to print each node's name and move to the next node until you return to the head.

4

Print the Traversal Result

Run the program to print the names of the friends in the order they are visited starting from head.

DSA Typescript

class Node {
  name: string;
  next: Node | null;

  constructor(name: string) {
    this.name = name;
    this.next = null;
  }
}

const alice = new Node('Alice');
const bob = new Node('Bob');
const charlie = new Node('Charlie');
const diana = new Node('Diana');

alice.next = bob;
bob.next = charlie;
charlie.next = diana;
diana.next = alice;

const head = alice;

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

// Run the program to see the output
// Your code here

Hint

Run the code and check the console output to see the names printed in order.

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