Create a Circular Singly Linked List in DSA Javascript - 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 singly linked list, it has no end or null pointer. This structure allows continuous traversal from any node without stopping.

Why it matters

This structure solves the problem of looping through data repeatedly without resetting or restarting. Without it, programs that need to cycle through items endlessly would require extra checks or resets, making them slower and more complex. Circular lists are useful in real-world tasks like music playlists or round-robin scheduling.

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 and circular doubly linked lists for more complex navigation.

Mental Model

Core Idea

A circular singly linked list is a chain of nodes connected end-to-start, allowing endless looping through the list.

Think of it like...

Imagine a group of friends sitting in a circle, each holding hands with the next person, and the last friend holding hands with the first, so you can keep passing a ball around forever without stopping.

Head -> [Node1] -> [Node2] -> [Node3] --|
                  ^                        |
                  |------------------------|

Build-Up - 6 Steps

1

Foundation

Understanding a Single Node Structure

Concept: Learn what a node is and how it stores data and a pointer to the next node.

In JavaScript, a node can be an object with two parts: 'data' to hold the value, and 'next' to point to the next node. For example: const node = { data: 5, next: null }; This node holds the number 5 and currently points to nothing (null).

Result

A single node object with data and a next pointer set to null.

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

2

Foundation

Creating a Simple Singly Linked List

Concept: Build a chain of nodes where each points to the next, ending with null.

Create nodes and link them: const node1 = { data: 1, next: null }; const node2 = { data: 2, next: null }; node1.next = node2; Now node1 points to node2, and node2 points to null, marking the list's end.

Result

A linked list: 1 -> 2 -> null

Seeing how nodes connect linearly helps grasp how lists grow and how traversal works.

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 first node? Commit to your answer.

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

Using the previous list: node2.next = node1; Now, node2 points back to node1, creating a circle. Traversing from node1 will loop endlessly: 1 -> 2 -> 1 -> 2 ...

Result

A circular list: 1 -> 2 -> (back to 1)

Understanding this pointer change is key to creating a circular structure that loops infinitely.

4

Intermediate

Implementing Circular List Class in JavaScript

🤔Before reading on: Do you think the list needs a special pointer to track the last node or just the head? Commit to your answer.

Concept: Create a class to manage nodes and maintain a reference to the last node for easy insertion and circular linking.

class CircularSinglyLinkedList { constructor() { this.last = null; // points to last node } add(data) { const newNode = { data, next: null }; if (!this.last) { newNode.next = newNode; // points to itself this.last = newNode; } else { newNode.next = this.last.next; // first node this.last.next = newNode; this.last = newNode; } } print() { if (!this.last) return ''; let result = ''; let current = this.last.next; // first node do { result += current.data + ' -> '; current = current.next; } while (current !== this.last.next); result += '(back to start)'; return result; } }

Result

A class that can add nodes and print the circular list, e.g., '1 -> 2 -> 3 -> (back to start)'

Tracking the last node simplifies adding new nodes and maintaining the circular link.

5

Advanced

Traversing and Avoiding Infinite Loops

🤔Before reading on: When traversing a circular list, do you think checking for null stops traversal? Commit to your answer.

Concept: Traversal must detect when it returns to the start node to avoid infinite loops, since null is never reached.

To traverse: let current = list.last.next; // start at first node if (!current) return; do { console.log(current.data); current = current.next; } while (current !== list.last.next); This stops after one full circle.

Result

Prints all nodes once without infinite looping.

Knowing how to detect the loop's end is crucial to safely use circular lists.

6

Expert

Handling Edge Cases and Deletion

🤔Before reading on: Do you think deleting the only node in a circular list leaves the list empty or still circular? Commit to your answer.

Concept: Deleting nodes requires careful pointer updates, especially when the list has one node or when deleting the last node.

To delete a node: - If only one node exists and it matches, set last to null. - If deleting last node, update last to previous node. - Update next pointers to skip deleted node. Example deletion method: remove(data) { if (!this.last) return; let current = this.last.next; let prev = this.last; do { if (current.data === data) { if (current === prev) { this.last = null; } else { prev.next = current.next; if (current === this.last) this.last = prev; } return; } prev = current; current = current.next; } while (current !== this.last.next); }

Result

Nodes can be safely removed without breaking the circular structure or causing errors.

Handling edge cases prevents bugs and crashes in real-world circular list usage.

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 the memory references, allowing traversal to continue indefinitely. The list maintains a reference to the last node to efficiently add new nodes and manage the circular link.

Why designed this way?

This design allows constant-time insertion at the end and easy access to the start node via last.next. Alternatives like tracking only the head would make adding nodes at the end slower. Circular linking avoids null checks during traversal, simplifying some algorithms that require repeated cycling.

┌─────────┐    ┌─────────┐    ┌─────────┐
│ Node 1  │ -> │ Node 2  │ -> │ Node 3  │
└─────────┘    └─────────┘    └─────────┘
     ^                                   |
     |-----------------------------------|

Myth Busters - 4 Common Misconceptions

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

Common Belief: A circular singly linked list ends with a null pointer like a regular singly linked list.

Reality: It never has a null pointer; the last node points back to the first node, forming a loop.

Why it matters: Assuming a null end causes infinite loops during traversal if the code expects null to stop.

Quick: Can you traverse a circular singly linked list starting from any node and visit all nodes exactly once? Commit to yes or no.

Common Belief: You must start traversal from the head node to visit all nodes correctly.

Reality: You can start from any node and still visit all nodes exactly once by looping until you return to the start node.

Why it matters: This flexibility is useful in applications like round-robin scheduling but is often overlooked.

Quick: Is it safe to delete nodes in a circular singly linked list the same way as in a regular singly linked list? Commit to yes or no.

Common Belief: Deletion works the same way as in regular singly linked lists without special care.

Reality: Deletion requires special handling of the last node and the case when only one node exists to maintain circularity.

Why it matters: Ignoring this causes broken links or lost references, corrupting the list.

Quick: Does tracking only the head node suffice for efficient insertion in a circular singly linked list? Commit to yes or no.

Common Belief: Only the head node is needed to manage the list efficiently.

Reality: Tracking the last node is important for efficient insertion at the end without traversing the entire list.

Why it matters: Without last node tracking, insertion becomes slower, reducing performance.

Expert Zone

1

The choice to track the last node instead of the head node optimizes insertion but requires careful handling during deletion and traversal.

2

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

3

In some systems, circular lists help avoid null pointer exceptions by design, but this requires disciplined traversal to prevent infinite loops.

When NOT to use

Avoid circular singly linked lists when you need backward traversal or easy access to previous nodes; use doubly linked lists instead. Also, if your application does not require repeated cycling, a regular singly linked list is simpler and less error-prone.

Production Patterns

Circular singly linked lists are used in real-time systems for round-robin task scheduling, in music or video playlists for continuous playback, and in network token ring protocols to pass control tokens in a loop.

Connections

Ring Buffer

Both use circular structures to manage data in a looped fashion.

Understanding circular linked lists helps grasp ring buffers, which use fixed-size arrays with circular indexing for efficient data streaming.

Event Loop in JavaScript

Both involve cycling through tasks or nodes repeatedly without stopping.

Knowing circular lists clarifies how the event loop cycles through callbacks continuously, ensuring non-blocking execution.

Circular Queues in Operating Systems

Circular singly linked lists and circular queues both implement cyclic data structures for scheduling.

Recognizing this connection helps understand how OS schedulers manage processes in a fair, repeating order.

Common Pitfalls

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

Wrong approach:

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

Correct approach:

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

Root cause:

Assuming the list ends with null instead of looping back causes traversal to never stop.

#2 Breaking circular link when adding the first node incorrectly.

Wrong approach:

add(data) {
const newNode = { data, next: null };
if (!this.last) {
this.last = newNode;
} else {
newNode.next = this.last.next;
this.last.next = newNode;
this.last = newNode;
}
}

Correct approach:

add(data) {
const newNode = { data, next: null };
if (!this.last) {
newNode.next = newNode;
this.last = newNode;
} else {
newNode.next = this.last.next;
this.last.next = newNode;
this.last = newNode;
}
}

Root cause:

Failing to point the first node's next to itself breaks the circular structure.

#3 Deleting the last node without updating the last pointer.

Wrong approach:

remove(data) {
// ...
if (current.data === data) {
prev.next = current.next;
// missing update of this.last if current is last
}
}

Correct approach:

remove(data) {
// ...
if (current.data === data) {
prev.next = current.next;
if (current === this.last) this.last = prev;
}
}

Root cause:

Not updating the last pointer causes the list to lose track of its end, corrupting the circular link.

Key Takeaways

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

Tracking the last node simplifies adding new nodes and maintaining the circular structure.

Traversal must detect when it returns to the start node to avoid infinite loops.

Special care is needed when deleting nodes to keep the list circular and consistent.

Circular singly linked lists are powerful for applications requiring repeated cycling through data.

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 stores data in a sorted order automatically.

D. It uses an array internally to store nodes.

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 linked lists

   Unlike doubly linked lists, circular singly linked lists have only one pointer per node and form a circle, not a linear chain.

3. Final Answer:

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

4. Quick Check:

   Last node's next = first node [OK]

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

Common Mistakes:

• Confusing circular singly linked list with doubly linked list
• Thinking nodes have two pointers
• Assuming data is sorted automatically

2. Which of the following is the correct way to initialize an empty circular singly linked list in JavaScript?

easy

A. const head = { data: null, next: head };

B. const head = null; // no nodes yet

C. const head = { data: null, next: null };

D. const head = []; // empty array

Solution

1. Step 1: Understand empty list initialization

   An empty circular singly linked list has no nodes, so the head pointer is null.

2. Step 2: Check other options

   const head = { data: null, next: null }; creates a node with null data and next pointer, which is not empty. const head = { data: null, next: head }; references head before assignment, causing error. const head = []; // empty array uses an array, not a linked list.

3. Final Answer:

   const head = null; // no nodes yet -> Option B

4. Quick Check:

   Empty list head = null [OK]

Hint: Empty list means head is null, no nodes created [OK]

Common Mistakes:

• Creating a node with null data instead of null head
• Referencing head before declaration
• Using arrays instead of linked list nodes

3. What will be the output of the following code snippet that creates a circular singly linked list with nodes 1, 2, 3 and prints the list once?

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class CircularSinglyLinkedList {
  constructor() {
    this.head = null;
  }

  append(data) {
    const newNode = new Node(data);
    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;
    }
  }

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

const list = new CircularSinglyLinkedList();
list.append(1);
list.append(2);
list.append(3);
console.log(list.printList());

medium

A. null

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

C. 1 -> 2 -> 3

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Understand append method behavior

   Each new node is added at the end, and its next points to head, maintaining circularity.

2. Step 2: Trace printList method

   printList starts at head and loops until it reaches head again, appending data with ' -> '. Finally adds 'null'. So output is '1 -> 2 -> 3 -> null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option D

4. Quick Check:

   Print once around circle = 1 -> 2 -> 3 -> null [OK]

Hint: Print loops until back to head once, then stops [OK]

Common Mistakes:

• Printing infinite loop by not stopping at head
• Missing 'null' at end
• Printing nodes multiple times

4. Identify the bug in this code snippet that tries to append a node to a circular singly linked list:

append(data) {
  const newNode = new Node(data);
  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. newNode.next should point to this.head when list is empty, not null.

B. The while loop condition should be temp.next === this.head.

C. The head should be set to newNode every time a node is appended.

D. The newNode should not be created inside the append method.

Solution

1. Step 1: Check initialization for empty list

   When list is empty, newNode.next must point to head itself to maintain circularity, not null.

2. Step 2: Verify loop and pointer updates

   The while loop and pointer updates are correct; only the initial next pointer is wrong.

3. Final Answer:

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

4. Quick Check:

   Empty list node next = head, not null [OK]

Hint: Empty list node next must loop to itself [OK]

Common Mistakes:

• Setting newNode.next to null breaks circular link
• Wrong while loop condition
• Resetting head incorrectly

5. You want to insert a new node with value 4 after the node with value 3 in a circular singly linked list. Given the list: 3 -> 1 -> 2 -> (back to 3), which code snippet correctly performs this insertion?

hard

A. let temp = head;
while (temp.next !== head) {
temp = temp.next;
}
const newNode = new Node(4);
temp.next = newNode;
newNode.next = head;

B. const newNode = new Node(4);
newNode.next = head;
head.next = newNode;

C. let temp = head;
while (temp.data !== 3) {
temp = temp.next;
}
const newNode = new Node(4);
newNode.next = temp.next;
temp.next = newNode;

D. head = new Node(4);
head.next = oldHead;

Solution

1. Step 1: Locate node with value 3

   Traverse from head until temp.data equals 3 to find the correct insertion point.

2. Step 2: Insert new node after node 3

   Create newNode with data 4, set newNode.next to temp.next, then set temp.next to newNode to insert correctly.

3. Final Answer:

   Traverse from head until finding node with value 3, then insert new node after it. -> Option C

4. Quick Check:

   Insert after node 3 by adjusting pointers [OK]

Hint: Find node 3, insert new node by pointer swap [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating pointers correctly
• Replacing head incorrectly