Delete a Node from Circular Linked List in DSA Javascript - Deep Dive

Overview - Delete a Node from Circular Linked List

What is it?

A circular linked list is a chain of nodes where the last node points back to the first node, forming a circle. Deleting a node means removing one element from this circle without breaking the loop. This operation updates the links so the list stays connected and circular. It requires careful handling to keep the structure intact.

Why it matters

Without the ability to delete nodes properly, circular linked lists would grow endlessly or become broken, losing their circular nature. This would make them unreliable for tasks like buffering, scheduling, or real-time data processing where circular lists are useful. Proper deletion keeps the list efficient and stable in real applications.

Where it fits

Before learning this, you should understand what linked lists are and how circular linked lists work. After this, you can explore more complex operations like insertion, searching, or using circular lists in algorithms like round-robin scheduling.

Mental Model

Core Idea

Deleting a node from a circular linked list means carefully redirecting the previous node's link to skip the target node, keeping the circle unbroken.

Think of it like...

Imagine a group of friends holding hands in a circle. If one friend leaves, the two friends on either side hold hands directly to keep the circle unbroken.

Head -> Node1 -> Node2 -> Node3 -> Node1 (circle)

To delete Node2:
Head -> Node1 -> Node3 -> Node1 (circle)

Build-Up - 7 Steps

1

Foundation

Understanding Circular Linked Lists

Concept: Learn what makes a linked list circular and how nodes connect in a loop.

A circular linked list is like a normal linked list but the last node points back to the first node instead of null. This means you can start at any node and keep moving forward forever. Each node has two parts: data and a pointer to the next node.

Result

You understand that the list has no end and loops back to the start.

Knowing the circular nature helps you realize why deletion must keep the loop intact, unlike in normal lists where the end is null.

2

Foundation

Basic Node Structure in JavaScript

Concept: Learn how to represent nodes and links in code.

In JavaScript, a node can be an object with 'data' and 'next' properties. For example: const node = { data: 5, next: null }; In a circular list, 'next' of the last node points back to the first node.

Result

You can create nodes and link them to form a circular list.

Understanding node structure is essential before manipulating links for deletion.

3

Intermediate

Finding the Node to Delete

🤔Before reading on: Do you think you must traverse the entire list to find the node to delete, or can you delete it immediately if you have a reference? Commit to your answer.

Concept: Learn how to locate the node to delete by traversing the list.

To delete a node by value, start from the head and move through nodes until you find the node with matching data. Because the list is circular, stop if you come back to the head without finding it. Keep track of the previous node to update its 'next' pointer.

Result

You can find the node to delete or know it doesn't exist.

Knowing how to find the node and its previous node is key to redirecting links correctly.

4

Intermediate

Deleting the Head Node Special Case

🤔Before reading on: Do you think deleting the head node is the same as deleting any other node? Commit to your answer.

Concept: Understand why deleting the head node needs special handling.

If the node to delete is the head, you must find the last node to update its 'next' pointer to the new head (head.next). Then update the head pointer to head.next. If the list has only one node, deleting it means the list becomes empty (null).

Result

You can delete the head without breaking the circular link.

Handling the head node separately prevents breaking the circle or losing the list reference.

5

Intermediate

Deleting a Middle or Last Node

Concept: Learn how to delete nodes other than the head by adjusting links.

For nodes other than the head, once you find the node and its previous node, set previous.next = node.next. This skips the node to delete, removing it from the circle. The list remains circular because links are updated properly.

Result

The node is removed and the list stays connected.

Redirecting the previous node's pointer is the core action that removes a node safely.

6

Advanced

Complete JavaScript Function for Deletion

🤔Before reading on: Do you think the function should handle empty lists, single-node lists, and missing nodes? Commit to your answer.

Concept: Combine all cases into one robust function to delete a node by value.

function deleteNode(head, key) { if (!head) return null; // empty list let curr = head, prev = null; // Single node case if (head.data === key && head.next === head) { return null; } // Find node to delete do { if (curr.data === key) { if (prev) { prev.next = curr.next; if (curr === head) head = curr.next; } else { // Deleting head node let last = head; while (last.next !== head) { last = last.next; } last.next = head.next; head = head.next; } return head; } prev = curr; curr = curr.next; } while (curr !== head); return head; // key not found }

Result

The function deletes the node if found, returns updated head, or returns null if list becomes empty.

A complete function must handle all edge cases to keep the circular list valid after deletion.

7

Expert

Performance and Edge Case Surprises

🤔Before reading on: Do you think deleting a node in a circular list is always O(n) time? Commit to your answer.

Concept: Explore performance limits and tricky edge cases in deletion.

Deletion requires traversal to find the node, so worst-case time is O(n). However, if you have a direct reference to the node and its previous node, deletion is O(1). Edge cases include deleting from a single-node list, deleting the head, and deleting a node not present. Forgetting to update the last node's pointer when deleting the head breaks the circle.

Result

You understand when deletion is fast or slow and what mistakes break the list.

Knowing these details helps write efficient and bug-free deletion code in real systems.

Under the Hood

Internally, each node stores a pointer to the next node. Deletion works by changing the 'next' pointer of the node before the target node to point to the node after the target. In a circular list, the last node points back to the head, so deleting the head requires updating the last node's pointer to the new head. Memory-wise, the removed node becomes unreachable and can be cleaned up by garbage collection.

Why designed this way?

Circular linked lists were designed to allow continuous looping without null ends, useful for cyclic tasks. Deletion must preserve this loop, so the design forces careful pointer updates. Alternatives like doubly linked lists add backward links but increase complexity and memory use. Circular lists balance simplicity and continuous traversal.

┌─────────┐     ┌─────────┐     ┌─────────┐
│ Node 1  │────▶│ Node 2  │────▶│ Node 3  │
└─────────┘     └─────────┘     └─────────┘
     ▲                              │
     │                              ▼
     └──────────────────────────────┘

To delete Node 2:

┌─────────┐     ┌─────────┐
│ Node 1  │────▶│ Node 3  │
└─────────┘     └─────────┘
     ▲              │
     │              ▼
     └──────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think deleting the head node in a circular linked list is the same as deleting any other node? Commit to yes or no.

Common Belief: Deleting the head node is just like deleting any other node; no special steps are needed.

Reality: Deleting the head node requires updating the last node's pointer to the new head to keep the list circular.

Why it matters: If you don't update the last node's pointer, the list breaks and traversal can enter an infinite loop or crash.

Quick: Do you think you can delete a node without knowing its previous node in a singly circular linked list? Commit to yes or no.

Common Belief: You can delete any node if you find it, without needing to know the previous node.

Reality: In singly linked lists, you must know the previous node to update its 'next' pointer; otherwise, you cannot remove the target node.

Why it matters: Trying to delete without the previous node leads to broken links and lost nodes.

Quick: Do you think deleting a node from an empty circular linked list is safe and does nothing? Commit to yes or no.

Common Belief: Deleting from an empty list is safe and just returns null or the same list.

Reality: You must check for empty lists before deletion to avoid errors or crashes.

Why it matters: Ignoring empty checks causes runtime errors in real programs.

Quick: Do you think deleting a node not present in the list changes the list? Commit to yes or no.

Common Belief: Trying to delete a node not in the list will remove something or change the list.

Reality: If the node isn't found, the list remains unchanged.

Why it matters: Assuming deletion always changes the list can cause bugs in logic and data handling.

Expert Zone

1

When deleting the head, updating the last node's pointer is critical; missing this causes subtle bugs that are hard to detect.

2

If you have a direct pointer to the node and its previous node, deletion can be done in O(1) time, which is a big optimization in some systems.

3

In multi-threaded environments, deleting nodes requires synchronization to avoid corrupting the circular links.

When NOT to use

Circular linked lists are not ideal when you need fast random access or backward traversal; doubly linked lists or arrays are better. Also, if memory overhead is critical, simpler data structures might be preferred.

Production Patterns

Circular linked lists are used in real-time systems for round-robin scheduling, buffering streaming data, and implementing cyclic queues. Deletion is often combined with insertion in these systems to maintain a fixed-size buffer.

Connections

Doubly Linked List

Builds-on

Understanding deletion in circular singly linked lists helps grasp the added complexity and flexibility of doubly linked lists, which allow backward traversal and easier deletion.

Garbage Collection

Depends-on

Deleting a node removes references to it, allowing garbage collection to reclaim memory automatically, which is crucial in languages like JavaScript.

Round-Robin Scheduling (Operating Systems)

Application

Circular linked lists model the cyclic order of tasks in round-robin scheduling, where deletion corresponds to removing completed or terminated tasks.

Common Pitfalls

#1 Not updating the last node's pointer when deleting the head node.

Wrong approach:

function deleteNode(head, key) {
if (!head) return null;
let curr = head, prev = null;
do {
if (curr.data === key) {
if (prev) {
prev.next = curr.next;
} else {
head = curr.next; // Missing last node update
}
return head;
}
prev = curr;
curr = curr.next;
} while (curr !== head);
return head;
}

Correct approach:

function deleteNode(head, key) {
if (!head) return null;
let curr = head, prev = null;
if (head.data === key && head.next === head) {
return null;
}
do {
if (curr.data === key) {
if (prev) {
prev.next = curr.next;
if (curr === head) head = curr.next;
} else {
let last = head;
while (last.next !== head) {
last = last.next;
}
last.next = head.next;
head = head.next;
}
return head;
}
prev = curr;
curr = curr.next;
} while (curr !== head);
return head;
}

Root cause:

Misunderstanding that the last node's pointer must be updated to maintain the circular link.

#2 Trying to delete a node without tracking the previous node in a singly linked list.

Wrong approach:

function deleteNode(head, key) {
let curr = head;
while (curr && curr.data !== key) {
curr = curr.next;
}
if (curr) {
curr = curr.next; // Incorrect: does not update previous node's next
}
return head;
}

Correct approach:

function deleteNode(head, key) {
if (!head) return null;
let curr = head, prev = null;
do {
if (curr.data === key) {
if (prev) {
prev.next = curr.next;
} else {
// handle head deletion
}
return head;
}
prev = curr;
curr = curr.next;
} while (curr !== head);
return head;
}

Root cause:

Not realizing that in singly linked lists, you must update the previous node's pointer to remove a node.

#3 Not checking for empty list before deletion.

Wrong approach:

function deleteNode(head, key) {
let curr = head;
// No check for null head
do {
if (curr.data === key) {
// deletion logic
}
curr = curr.next;
} while (curr !== head);
return head;
}

Correct approach:

function deleteNode(head, key) {
if (!head) return null;
let curr = head;
do {
if (curr.data === key) {
// deletion logic
}
curr = curr.next;
} while (curr !== head);
return head;
}

Root cause:

Overlooking the possibility of an empty list leads to runtime errors.

Key Takeaways

A circular linked list loops back to the start, so deleting nodes must keep this loop intact.

Deleting the head node is special because you must update the last node's pointer to the new head.

You need to track the previous node to delete a node safely in a singly linked list.

Edge cases like empty lists and single-node lists require careful handling to avoid errors.

Efficient deletion depends on knowing the node and its previous node; otherwise, traversal is needed.

Practice

1. What happens when you delete the head node from a circular linked list with multiple nodes?

easy

A. The head moves to the next node and the list remains circular

B. The list becomes empty immediately

C. The last node points to null breaking the circle

D. The list throws an error and stops

Solution

1. Step 1: Understand the head deletion in circular list

   When the head node is deleted, the next node becomes the new head.

2. Step 2: Maintain circular link

   The last node's next pointer is updated to point to the new head, keeping the list circular.

3. Final Answer:

   The head moves to the next node and the list remains circular -> Option A

4. Quick Check:

   Head deletion updates head and last node pointer [OK]

Hint: Head deletion shifts head and keeps circle intact [OK]

Common Mistakes:

• Assuming list becomes empty after head deletion
• Breaking the circular link by setting last node to null
• Not updating the last node's next pointer

2. Which of the following is the correct syntax to delete a node with value `key` from a circular linked list in JavaScript?

easy

A. function deleteNode(head) { /* code */ }

B. function deleteNode(key, head) { /* code */ }

C. function deleteNode(head, key) { /* code */ }

D. function deleteNode() { /* code */ }

Solution

1. Step 1: Identify function parameters for deletion

   The function needs the head of the list and the key value to delete the correct node.

2. Step 2: Confirm correct parameter order

   The common and clear order is (head, key) to access the list and the target value.

3. Final Answer:

   function deleteNode(head, key) { /* code */ } -> Option C

4. Quick Check:

   Parameters: head and key in order [OK]

Hint: Function needs head and key parameters in order [OK]

Common Mistakes:

• Swapping parameter order causing confusion
• Missing key parameter to identify node
• Using no parameters making deletion impossible

3. What will be the output after deleting node with value 3 from this circular linked list: 1 -> 3 -> 5 -> 7 -> (back to 1)?
<pre>function deleteNode(head, key) { if (!head) return null; let curr = head, prev = null; do { if (curr.data === key) { if (prev) prev.next = curr.next; else { let temp = head; while (temp.next !== head) temp = temp.next; head = curr.next; temp.next = head; } break; } prev = curr; curr = curr.next; } while (curr !== head); return head; } // After deletion, print list starting from head

medium

A. 1 -> 5 -> 7 -> (back to 1)

B. 3 -> 5 -> 7 -> (back to 3)

C. 1 -> 3 -> 5 -> 7 -> (back to 1)

D. 5 -> 7 -> 1 -> (back to 5)

Solution

1. Step 1: Locate node with value 3

   The code loops through nodes and finds node with data 3.

2. Step 2: Delete node 3 and update links

   Since node 3 is not head, prev.next skips node 3 and points to node 5, maintaining circular link.

3. Final Answer:

   1 -> 5 -> 7 -> (back to 1) -> Option A

4. Quick Check:

   Node 3 removed, list links updated [OK]

Hint: Skip deleted node by linking previous to next [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Deleting head incorrectly when key is not head
• Breaking circular link by missing last node update

4. Identify the bug in this code snippet for deleting a node from a circular linked list:

function deleteNode(head, key) {
  if (!head) return null;
  let curr = head;
  while (curr.next !== head) {
    if (curr.next.data === key) {
      curr.next = curr.next.next;
      return head;
    }
    curr = curr.next;
  }
  return head;
}

medium

A. Infinite loop due to missing break

B. Does not handle deletion when head node has the key

C. Deletes multiple nodes with the key instead of one

D. Returns null even if list is not empty

Solution

1. Step 1: Analyze loop and deletion logic

   The loop checks curr.next for key but never checks head node itself.

2. Step 2: Identify missing head deletion case

   If head node contains key, this code does not delete it, causing incorrect behavior.

3. Final Answer:

   Does not handle deletion when head node has the key -> Option B

4. Quick Check:

   Head node deletion missing in logic [OK]

Hint: Always check head node separately for deletion [OK]

Common Mistakes:

• Ignoring head node deletion case
• Assuming loop covers all nodes including head
• Not updating head pointer when head is deleted

5. Given a circular linked list with nodes 10 -> 20 -> 30 -> 40 -> (back to 10), how would you delete the last node (40) and maintain the circular structure? Choose the correct approach.

hard

A. Swap last node data with head and delete head

B. Set head to null directly to delete last node

C. Change last node's next to null to break the circle

D. Traverse to node before last, set its next to head, and delete last node

Solution

1. Step 1: Find node before last node

   Traverse list until node.next.next equals head, identifying node before last.

2. Step 2: Update next pointer and delete last node

   Set node before last's next pointer to head, removing last node and keeping list circular.

3. Final Answer:

   Traverse to node before last, set its next to head, and delete last node -> Option D

4. Quick Check:

   Update second last node's next to head [OK]

Hint: Link second last node directly to head [OK]

Common Mistakes:

• Breaking circle by setting next to null
• Deleting head instead of last node
• Not updating pointers causing broken list