Create a Circular Singly Linked List in DSA Typescript - Deep Dive

Overview - Create a Circular Singly Linked List

What is it?

A Circular Singly Linked List is a chain of nodes where each node points to the next, and the last node points back to the first node, forming a circle. Unlike a regular linked list, it has no end or null pointer. This structure allows continuous traversal from any node without stopping.

Why it matters

It solves the problem of looping through data repeatedly without resetting or restarting. Without circular lists, you would have to manually restart traversal from the head each time. Circular lists are useful in applications like round-robin scheduling, music playlists, or games where you cycle through players endlessly.

Where it fits

Before learning this, you should understand basic singly linked lists and pointers. After mastering circular singly linked lists, you can explore doubly linked lists, circular doubly linked lists, and advanced data structures like queues and deques.

Mental Model

Core Idea

A circular singly linked list is a chain of nodes connected end-to-start, making a loop with no end.

Think of it like...

Imagine a group of friends sitting in a circle passing a ball; each friend passes it to the next, and the last friend passes it back to the first, so the ball keeps moving endlessly.

Head -> Node1 -> Node2 -> Node3 --+
          ^                        |
          |------------------------+

Build-Up - 7 Steps

1

Foundation

Understanding Node Structure

Concept: Introduce the basic building block: a node with data and a pointer to the next node.

In TypeScript, a node can be a class with two properties: 'data' to store the value and 'next' to point to the next node. For example: class Node { data: number; next: Node | null; constructor(data: number) { this.data = data; this.next = null; } }

Result

You have a simple node that can hold a number and a pointer to another node or null.

Understanding the node structure is essential because the entire list is built by linking these nodes together.

2

Foundation

Creating a Basic Singly Linked List

Concept: Learn how to link nodes in a straight line where the last node points to null.

Create a LinkedList class with a 'head' pointer. Add nodes by linking the last node's 'next' to the new node. Example: class LinkedList { head: Node | null = null; add(data: number) { const newNode = new Node(data); if (!this.head) { this.head = newNode; } else { let current = this.head; while (current.next) { current = current.next; } current.next = newNode; } } }

Result

You can create a chain like 1 -> 2 -> 3 -> null.

Building a simple linked list helps grasp how nodes connect linearly before adding circular behavior.

3

Intermediate

Making the List Circular

🤔Before reading on: Do you think making the list circular means the last node points to null or back to the head? Commit to your answer.

Concept: Change the last node's 'next' pointer to point back to the head node instead of null.

Modify the add method so after adding a new node, the last node's 'next' points to the head, creating a loop: class CircularLinkedList { head: Node | null = null; add(data: number) { const newNode = new Node(data); if (!this.head) { this.head = newNode; newNode.next = this.head; // points to itself } else { let current = this.head; while (current.next !== this.head) { current = current.next!; } current.next = newNode; newNode.next = this.head; } } }

Result

The list looks like 1 -> 2 -> 3 -> back to 1, forming a circle.

Knowing the last node points back to the head is key to creating the circular structure that enables endless traversal.

4

Intermediate

Traversing a Circular List Safely

🤔Before reading on: When traversing a circular list, do you think you stop at null or after visiting all nodes once? Commit to your answer.

Concept: Traversal must detect when it loops back to the start to avoid infinite loops.

To print all nodes, start at head and move to next nodes until you reach head again: print() { if (!this.head) return; let current = this.head; do { console.log(current.data); current = current.next!; } while (current !== this.head); }

Result

Prints all node data exactly once, then stops.

Understanding traversal stopping conditions prevents infinite loops and ensures correct data processing.

5

Intermediate

Inserting Nodes at Different Positions

🤔Before reading on: Do you think inserting at the head in a circular list is the same as in a linear list? Commit to your answer.

Concept: Insertion must update pointers carefully to maintain the circular link, especially when adding at the head.

To insert at head: - Create new node - Find last node - Point last node's next to new node - Point new node's next to old head - Update head to new node Example: insertAtHead(data: number) { const newNode = new Node(data); if (!this.head) { this.head = newNode; newNode.next = this.head; } else { let current = this.head; while (current.next !== this.head) { current = current.next!; } current.next = newNode; newNode.next = this.head; this.head = newNode; } }

Result

New node becomes the head, and the circle remains intact.

Knowing how to update the last node's pointer when changing the head is crucial to keep the list circular.

6

Advanced

Deleting Nodes Without Breaking the Circle

🤔Before reading on: When deleting the head node, do you think you just move head to next or also update the last node's pointer? Commit to your answer.

Concept: Deletion requires updating pointers so the circle stays connected, especially when removing the head or the only node.

To delete a node: - If list empty, do nothing - If deleting head: - Find last node - If only one node, set head to null - Else, last node's next points to head.next - Update head to head.next - Else, find node before target and update its next Example: delete(data: number) { if (!this.head) return; let current = this.head; let prev = null; do { if (current.data === data) { if (prev) { prev.next = current.next; } else { // deleting head let last = this.head; while (last.next !== this.head) { last = last.next!; } if (this.head === this.head.next) { this.head = null; } else { last.next = this.head.next; this.head = this.head.next; } } return; } prev = current; current = current.next!; } while (current !== this.head); }

Result

Node is removed, and the circular structure remains intact.

Understanding pointer updates during deletion prevents breaking the circle or losing nodes.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: Do you think circular lists always improve performance over linear lists? Commit to your answer.

Concept: Recognize edge cases like empty list, single node, and performance trade-offs in circular lists.

Edge cases: - Empty list: head is null - Single node: node's next points to itself Performance: - Circular lists allow continuous cycling without reset - But searching can be slower since no null to stop early - Careful pointer updates needed to avoid infinite loops Example: Traversing an empty list prints nothing; traversing single node prints once. Optimizations include keeping a tail pointer to avoid full traversal when adding nodes.

Result

Robust circular list handles all cases without errors and performs well with optimizations.

Knowing edge cases and performance helps build reliable, efficient circular lists in real systems.

Under the Hood

Internally, each node stores a reference (pointer) to the next node's memory location. In a circular singly linked list, the last node's pointer loops back to the first node's memory address instead of null. This creates a cycle in memory references, allowing traversal to continue indefinitely. The runtime follows these pointers step-by-step, so careful pointer updates are critical to avoid infinite loops or broken links.

Why designed this way?

Circular lists were designed to model continuous cycles naturally, such as round-robin processes. The circular pointer eliminates the need for special end-of-list checks, simplifying repeated traversals. Alternatives like linear lists require manual resets or extra state to loop, which can be error-prone. Circular lists trade off complexity in pointer management for seamless cycling.

+---------+    +---------+    +---------+
| Node 1  | -> | Node 2  | -> | Node 3  |
+---------+    +---------+    +---------+
     ^                                    |
     |------------------------------------+

Myth Busters - 3 Common Misconceptions

Quick: Does a circular singly linked list have a null pointer? Commit yes or no.

Common Belief: The last node in a circular singly linked list points to null like in a regular list.

Reality: The last node points back to the head node, creating a loop with no null pointer.

Why it matters: Assuming a null pointer causes infinite loops during traversal because the stopping condition is never met.

Quick: When deleting the head node, is it enough to just move the head pointer? Commit yes or no.

Common Belief: Deleting the head node only requires moving the head pointer to the next node.

Reality: You must also update the last node's next pointer to the new head to maintain the circle.

Why it matters: Failing to update the last node breaks the circular link, causing traversal errors or crashes.

Quick: Is traversal in a circular list always faster than linear lists? Commit yes or no.

Common Belief: Circular lists always improve traversal speed because they loop continuously.

Reality: Traversal can be slower because you must check for the loop condition explicitly and cannot rely on null to stop early.

Why it matters: Misunderstanding performance can lead to inefficient algorithms or infinite loops in production.

Expert Zone

1

Maintaining a tail pointer alongside the head can optimize insertion and deletion by avoiding full traversal to find the last node.

2

Circular singly linked lists can be used to implement efficient queues with constant-time enqueue and dequeue operations.

3

Careful handling of single-node lists is crucial since the node points to itself, which can cause subtle bugs if not accounted for.

When NOT to use

Avoid circular singly linked lists when you need backward traversal or easy node removal from the end; use doubly linked lists instead. Also, if your application requires frequent random access, arrays or other data structures are better.

Production Patterns

Circular singly linked lists are used in real-time systems for round-robin task scheduling, in multimedia applications for looping playlists, and in multiplayer games to cycle through players. They often pair with tail pointers for efficient updates.

Connections

Queue Data Structure

Circular singly linked lists can implement queues efficiently by cycling through nodes.

Understanding circular lists helps grasp how queues manage elements in a fixed cycle without shifting data.

Ring Buffer (Circular Buffer)

Both use circular structures to reuse space and cycle through data continuously.

Knowing circular linked lists clarifies how ring buffers manage fixed-size data streams without reallocations.

Round-Robin Scheduling (Operating Systems)

Circular lists model the continuous cycling of processes in round-robin CPU scheduling.

Seeing circular lists in OS scheduling reveals how data structures directly influence system behavior.

Common Pitfalls

#1 Infinite loop during traversal due to missing loop stop condition.

Wrong approach:

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

Correct approach:

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

Root cause:

Assuming the list ends with null like a linear list, but circular lists loop back to head.

#2 Breaking the circle when deleting the head node by not updating the last node's pointer.

Wrong approach:

list.head = list.head.next; // without updating last node's next

Correct approach:

let last = list.head;
while (last.next !== list.head) {
last = last.next!;
}
last.next = list.head.next;
list.head = list.head.next;

Root cause:

Forgetting the last node must point to the new head to maintain circularity.

#3 Adding a node without linking it back to head, breaking the circle.

Wrong approach:

current.next = newNode;
newNode.next = null; // breaks circular link

Correct approach:

current.next = newNode;
newNode.next = list.head; // maintains circular link

Root cause:

Not updating the new node's next pointer to head breaks the loop.

Key Takeaways

A circular singly linked list connects the last node back to the first, forming a loop with no end.

Traversal requires special care to stop after one full cycle to avoid infinite loops.

Insertion and deletion must update pointers carefully to maintain the circular structure.

Edge cases like empty lists and single-node lists need explicit handling to prevent bugs.

Circular lists are powerful for applications needing continuous cycling, but they require mindful pointer management.

Practice

1. What is a key characteristic of a circular singly linked list compared to a regular singly linked list?

easy

A. The last node points back to the first node, forming a circle.

B. Each node has two pointers, one to the next and one to the previous node.

C. It uses an array internally to store nodes.

D. The list always has a fixed size.

Solution

1. Step 1: Understand the structure of a circular singly linked list

   In a circular singly linked list, the last node's next pointer points back to the first node, creating a loop.

2. Step 2: Compare with other list types

   Regular singly linked lists end with a null pointer, doubly linked lists have two pointers per node, and arrays are not linked lists.

3. Final Answer:

   The last node points back to the first node, forming a circle. -> Option A

4. Quick Check:

   Circular list last node points to head = A [OK]

Hint: Remember: circular means last node links back to first [OK]

Common Mistakes:

• Thinking circular means doubly linked
• Assuming last node points to null
• Confusing arrays with linked lists

2. Which of the following TypeScript code snippets correctly initializes an empty circular singly linked list?

easy

A. let head: Node = null; head.next = head;

B. let head: Node | null = null;

C. let head: Node | null = new Node(null); head.next = null;

D. let head: Node = new Node(null); head.next = head;

Solution

1. Step 1: Understand initialization of circular singly linked list

   For an empty circular singly linked list with one node, the node's next pointer should point to itself.

2. Step 2: Analyze each option

   let head: Node = new Node(null); head.next = head; creates a node and sets its next to itself, correctly forming a circular list with one node. let head: Node | null = null; sets head to null (empty list, but not circular). let head: Node | null = new Node(null); head.next = null; sets next to null (not circular). let head: Node = null; head.next = head; tries to assign next on null (error).

3. Final Answer:

   let head: Node = new Node(null); head.next = head; -> Option D

4. Quick Check:

   One node points to itself = A [OK]

Hint: One node circular list points next to itself [OK]

Common Mistakes:

• Setting next to null instead of self
• Assigning next on null variable
• Not creating a node before linking

3. Given the following TypeScript code for a circular singly linked list, what will be the output after inserting nodes with values 1, 2, and 3 in order?

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

class CircularList {
  head: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head;
    } else {
      let temp = this.head;
      while (temp.next !== this.head) {
        temp = temp.next!;
      }
      temp.next = newNode;
      newNode.next = this.head;
    }
  }

  print() {
    if (!this.head) return '';
    let result = '';
    let temp = this.head;
    do {
      result += temp.value + ' -> ';
      temp = temp.next!;
    } while (temp !== this.head);
    result += 'null';
    return result;
  }
}

const list = new CircularList();
list.insert(1);
list.insert(2);
list.insert(3);
console.log(list.print());

medium

A. 1 -> 2 -> 3 -> 1 -> null

B. 1 -> 2 -> 3 -> 1

C. 1 -> 2 -> 3 -> null

D. 1 -> 2 -> 3

Solution

1. Step 1: Trace insertions and list structure

   Insert 1: head points to node 1, node 1 next points to itself.
   Insert 2: find last node (1), set last node's next to new node 2, new node 2 next points to head (1).
   Insert 3: find last node (2), set last node's next to new node 3, new node 3 next points to head (1).

2. Step 2: Trace print method output

   Print starts at head (1), prints 1 -> 2 -> 3 -> then stops when it reaches head again, appends 'null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option C

4. Quick Check:

   Print stops at head, adds null = B [OK]

Hint: Print stops when node loops back to head [OK]

Common Mistakes:

• Printing extra head node again
• Missing 'null' at end
• Infinite loop without stopping condition

4. Identify the bug in this TypeScript method for inserting a node into a circular singly linked list:

insert(value: number) {
  const newNode = new Node(value);
  if (!this.head) {
    this.head = newNode;
    newNode.next = null;
  } else {
    let temp = this.head;
    while (temp.next !== this.head) {
      temp = temp.next!;
    }
    temp.next = newNode;
    newNode.next = this.head;
  }
}

medium

A. The method does not create a new node correctly.

B. newNode.next should point to head, not null, when list is empty.

C. The while loop condition should be temp.next === null.

D. The head should be set to null after insertion.

Solution

1. Step 1: Analyze insertion when list is empty

   When the list is empty, newNode.next is set to null, breaking circular property. It should point to head to form a circle.

2. Step 2: Check loop condition and other logic

   The while loop correctly finds the last node by checking temp.next !== head. Other parts are correct.

3. Final Answer:

   newNode.next should point to head, not null, when list is empty. -> Option B

4. Quick Check:

   Empty list node next must point to itself = C [OK]

Hint: Empty list node next must point to itself, not null [OK]

Common Mistakes:

• Setting next to null breaks circular link
• Wrong loop condition causes infinite loop
• Resetting head incorrectly

5. You want to implement a method delete(value: number) to remove a node with a given value from a circular singly linked list. Which approach correctly handles deleting the head node while maintaining the circular structure?

hard

A. Find the last node, set its next to head.next, then update head to head.next.

B. Set head to null directly without updating any other node.

C. Set head.next to null and keep head unchanged.

D. Remove the node by setting head to head.next without updating last node's next.

Solution

1. Step 1: Understand deleting head in circular list

   To delete the head, we must update the last node's next pointer to the new head (head.next) to maintain the circle.

2. Step 2: Analyze each option

   Find the last node, set its next to head.next, then update head to head.next. correctly finds last node, updates its next to head.next, then moves head to head.next.
   Set head to null directly without updating any other node. breaks the list by setting head to null without fixing last node.
   Set head.next to null and keep head unchanged. breaks the circle by setting head.next to null.
   Remove the node by setting head to head.next without updating last node's next. moves head but leaves last node pointing to old head, breaking the circle.

3. Final Answer:

   Find the last node, set its next to head.next, then update head to head.next. -> Option A

4. Quick Check:

   Last node next updated to new head = D [OK]

Hint: Update last node's next when deleting head [OK]

Common Mistakes:

• Not updating last node's next pointer
• Setting head to null without cleanup
• Breaking circular link by null assignments