Delete a Node from Circular Linked List in DSA C#

Mental Model

A circular linked list loops back to the start, so deleting a node means reconnecting the previous node to the next, keeping the circle unbroken.

Analogy: 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 intact.

head -> 1 -> 2 -> 3 -> 4 -> (back to head 1)
          ↑                       ↓
          ←-----------------------

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 (circular), delete node with value 3

Goal: Remove node with value 3 and keep the list circular

Step 1: start at head node 1, check if head is node to delete

head -> [1] -> 2 -> 3 -> 4 -> (back to head 1)

Why: We must check if the node to delete is the head to handle special case

Step 2: move to node 2, check if next node is node to delete

head -> 1 -> [2] -> 3 -> 4 -> (back to head 1)

Why: We look ahead to find the node before the one to delete

Step 3: found node 2 points to node 3 (to delete), link node 2 to node 4

head -> 1 -> 2 -> [4] -> (back to head 1)

Why: By skipping node 3, we remove it and keep the circle

Step 4: node 3 is removed, list remains circular without node 3

head -> 1 -> 2 -> 4 -> (back to head 1)

Why: The circle is maintained with node 3 deleted

Result:

head -> 1 -> 2 -> 4 -> (back to head 1)

Annotated Code

DSA C#

using System;

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

public class CircularLinkedList
{
    public Node head = null;

    public void Insert(int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            head = newNode;
            newNode.next = head; // points to itself
            return;
        }
        Node temp = head;
        while (temp.next != head)
        {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.next = head;
    }

    public void DeleteNode(int key)
    {
        if (head == null) return; // empty list

        Node curr = head, prev = null;

        // If head is to be deleted and only one node
        if (head.data == key && head.next == head)
        {
            head = null;
            return;
        }

        // If head is to be deleted and more than one node
        if (head.data == key)
        {
            // find last node to update its next
            Node last = head;
            while (last.next != head)
            {
                last = last.next;
            }
            head = head.next; // move head
            last.next = head; // update last node's next
            return;
        }

        // For other nodes
        prev = head;
        curr = head.next;
        while (curr != head && curr.data != key)
        {
            prev = curr;
            curr = curr.next;
        }

        if (curr != head && curr.data == key)
        {
            prev.next = curr.next; // unlink node
        }
    }

    public void PrintList()
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }
        Node temp = head;
        do
        {
            Console.Write(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        Console.WriteLine("(back to head " + head.data + ")");
    }
}

class Program
{
    static void Main()
    {
        CircularLinkedList cll = new CircularLinkedList();
        cll.Insert(1);
        cll.Insert(2);
        cll.Insert(3);
        cll.Insert(4);

        Console.WriteLine("Original list:");
        cll.PrintList();

        cll.DeleteNode(3);

        Console.WriteLine("After deleting node with value 3:");
        cll.PrintList();
    }
}

if (head == null) return; // empty list

handle empty list edge case

if (head.data == key && head.next == head)

handle single node list where head is to be deleted

if (head.data == key)

handle deletion of head node when list has multiple nodes

while (last.next != head)

find last node to update its next pointer after head deletion

prev = head; curr = head.next; while (curr != head && curr.data != key)

traverse list to find node before the one to delete

if (curr != head && curr.data == key) { prev.next = curr.next; // unlink node }

unlink the node to delete by skipping it in the circle

Output

Original list:

1 -> 2 -> 3 -> 4 -> (back to head 1)

After deleting node with value 3:

1 -> 2 -> 4 -> (back to head 1)

Complexity Analysis

Time: O(n) because in worst case we traverse all nodes once to find the node to delete

Space: O(1) because we use only a few pointers regardless of list size

vs Alternative: Compared to a singly linked list, circular list requires careful pointer updates to maintain the circle, but deletion time remains O(n)

Edge Cases

empty list

function returns immediately without error

DSA C#

if (head == null) return; // empty list

single node list where node to delete is head

head is set to null, list becomes empty

DSA C#

if (head.data == key && head.next == head)

deleting head node in multi-node list

head moves to next node and last node's next pointer updates to new head

DSA C#

if (head.data == key)

node to delete not found

list remains unchanged

DSA C#

while (curr != head && curr.data != key)

When to Use This Pattern

When you see a problem asking to delete a node in a circular linked list, reach for the pointer update pattern that keeps the circle intact by linking the previous node to the next node.

Common Mistakes

Mistake: Not updating the last node's next pointer when deleting the head node
Fix: Find the last node and update its next pointer to the new head after deletion

Mistake: Not handling the single node list case where head points to itself
Fix: Check if head.next == head and delete by setting head to null

Mistake: Stopping traversal too early or infinite loop by not checking for full circle
Fix: Use condition curr != head to stop traversal after full circle

Summary

Deletes a node from a circular linked list by reconnecting pointers to maintain the circle.

Use when you need to remove a specific node from a circular linked list without breaking its circular nature.

The key is to carefully update the previous node's next pointer and handle special cases like deleting the head or single node.

Practice

1. What happens when you delete the only node in a circular linked list?

easy

A. The list becomes a linear linked list.

B. The list still contains one node pointing to itself.

C. The list becomes empty (null).

D. The list throws an error.

Solution

1. Step 1: Understand the structure of a single-node circular linked list

   In a circular linked list with one node, the node points to itself.

2. Step 2: Delete the only node

   Removing this node leaves no nodes, so the list becomes empty (null).

3. Final Answer:

   The list becomes empty (null). -> Option C

4. Quick Check:

   Deleting the only node empties the list [OK]

Hint: Deleting last node empties the list, no nodes remain [OK]

Common Mistakes:

• Assuming list still has one node after deletion
• Thinking list becomes linear instead of empty
• Expecting an error on deletion

2. Which of the following is the correct way to update the head pointer when deleting the head node in a circular linked list?

easy

A. head = head.next;

B. head = null;

C. head = head.prev;

D. head = head.next.next;

Solution

1. Step 1: Identify the new head after deleting the current head

   When deleting the head node, the new head should be the next node in the list.

2. Step 2: Update the head pointer

   Assign head to head.next to point to the next node.

3. Final Answer:

   head = head.next; -> Option A

4. Quick Check:

   New head is next node after deletion [OK]

Hint: After deleting head, move head pointer to next node [OK]

Common Mistakes:

• Setting head to null incorrectly
• Using head.prev which is invalid in singly circular list
• Skipping updating head pointer

3. What will be the output after deleting node with value 3 from the circular linked list: 1 -> 2 -> 3 -> 4 -> (back to 1)?

Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = head;
// Delete node with value 3
// After deletion, print list starting from head

medium

A. 2 -> 3 -> 4 -> (back to 2)

B. 1 -> 2 -> 3 -> 4 -> (back to 1)

C. 1 -> 2 -> (back to 1)

D. 1 -> 2 -> 4 -> (back to 1)

Solution

1. Step 1: Identify node to delete and its previous node

   Node with value 3 is after node with value 2.

2. Step 2: Update previous node's next pointer

   Set node 2's next to node 4, skipping node 3.

3. Final Answer:

   1 -> 2 -> 4 -> (back to 1) -> Option D

4. Quick Check:

   Node 3 removed, list links 2 to 4 [OK]

Hint: Link previous node to next of deleted node [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Deleting wrong node
• Breaking circular link

4. Given this code snippet to delete a node from a circular linked list, what is the bug?

Node current = head;
while (current.next != head && current.next.data != key) {
    current = current.next;
}
if (current.next.data == key) {
    current.next = current.next.next;
}

medium

A. Does not handle deleting the head node correctly.

B. Does not update head pointer after deletion.

C. Deletes multiple nodes instead of one.

D. Infinite loop if key not found.

Solution

1. Step 1: Analyze deletion logic

   The code finds the node before the target and skips the target node.

2. Step 2: Check head pointer update

   If the deleted node is head, head pointer is not updated, causing inconsistency.

3. Final Answer:

   Does not update head pointer after deletion. -> Option B

4. Quick Check:

   Head pointer must update if head node deleted [OK]

Hint: Always update head if deleted node is head [OK]

Common Mistakes:

• Ignoring head pointer update
• Assuming deletion always non-head
• Not checking if key exists

5. You have a circular linked list with nodes: 10 -> 20 -> 30 -> 40 -> (back to 10). You want to delete the node with value 10 (head node). Which steps correctly delete the head and maintain the circular structure?

hard

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

B. Set head to null directly.

C. Set head to head.next without changing last node's next.

D. Remove head and leave last node pointing to null.

Solution

1. Step 1: Find the last node in the circular list

   Traverse nodes until node.next == head to find last node (node with value 40).

2. Step 2: Update last node's next pointer and head

   Set last node's next to head.next (node 20), then update head to head.next.

3. Final Answer:

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

4. Quick Check:

   Last node points to new head, list remains circular [OK]

Hint: Update last node's next and move head to next node [OK]

Common Mistakes:

• Not updating last node's next pointer
• Setting head to null incorrectly
• Breaking circular link by pointing to null