Delete a Node from Circular Linked List in DSA C# - Execution Trace

Concept Flow - Delete a Node from Circular Linked List

Start at head node

↓

Check if list is empty?

Yes→Stop: Nothing to delete

No↓

Find node with target value

↓

Is node found?

No→Stop: Node not found

Yes↓

Is node the only node?

Yes→Set head to null

No↓

Adjust pointers to remove node

↓

Update head if needed

↓

Node deleted, list updated

↓

End

Start from head, check if list is empty, find node to delete, adjust pointers carefully, update head if needed, then finish.

Execution Sample

DSA C#

Node DeleteNode(Node head, int key) {
  if (head == null) return null;
  Node curr = head, prev = null;
  do {
    if (curr.data == key) break;
    prev = curr;
    curr = curr.next;
  } while (curr != head);
  // deletion logic here
  return head;
}

This code searches for the node with the given key in the circular linked list and prepares to delete it.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list: 10 -> 20 -> 30 -> 40 -> (back to 10)	10 -> 20 -> 30 -> 40 -> (back to 10)	head points to 10	10 -> 20 -> 30 -> 40 -> (back to 10)
2	Search for node with value 30	10 -> 20 -> 30 -> 40 -> (back to 10)	curr moves: 10 -> 20 -> 30, prev moves: null -> 10 -> 20	curr at 30, prev at 20
3	Delete node 30 by linking prev.next to curr.next	10 -> 20 -> 40 -> (back to 10)	20.next changed from 30 to 40	10 -> 20 -> 40 -> (back to 10)
4	Check if deleted node was head (no), head unchanged	10 -> 20 -> 40 -> (back to 10)	head still at 10	10 -> 20 -> 40 -> (back to 10)
5	End of deletion	10 -> 20 -> 40 -> (back to 10)	No pointer changes	10 -> 20 -> 40 -> (back to 10)

💡 Node with value 30 found and deleted, list updated with 3 nodes remaining.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
head	points to 10	points to 10	points to 10	points to 10
curr	points to 10	points to 30	points to 30 (deleted)	points to 30 (deleted)
prev	null	points to 20	points to 20	points to 20

Key Moments - 3 Insights

Why do we use a do-while loop instead of a while loop when searching?

Because the list is circular, we must check the current node before moving to next. The do-while ensures we check all nodes including head again to stop if not found, as shown in step 2 of execution_table.

What happens if the node to delete is the head node?

If the node to delete is head, after adjusting pointers, we update head to the next node to keep the list connected. This is important to maintain the circular structure.

Why do we link prev.next to curr.next to delete the node?

Because in a singly linked circular list, to remove a node, we must bypass it by linking the previous node's next pointer to the node after the current one, effectively removing current from the chain, as shown in step 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, where is the 'curr' pointer pointing?

A Node with value 20

B Node with value 30

C Node with value 10

D Node with value 40

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 2 in execution_table.

At which step does the list size reduce from 4 nodes to 3 nodes?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Nodes in List' column in execution_table to see when the node is removed.

If the node to delete was the head node (value 10), what pointer would need to be updated?

A prev.next to point to head.next

B head to point to head.next

C curr to point to prev

D No pointer needs updating

💡 Hint

Refer to key_moments about updating head when deleting the head node.

Concept Snapshot

Delete Node in Circular Linked List:
- Start at head, check empty list
- Use do-while to find node
- If found, link prev.next to curr.next
- If deleting head, update head pointer
- Handle single-node list by setting head to null
- Maintain circular links after deletion

Full Transcript

To delete a node from a circular linked list, start at the head node. If the list is empty, stop. Use a do-while loop to find the node with the target value, moving through nodes until you find it or return to head. If the node is found, adjust the previous node's next pointer to skip the node to delete. If the node to delete is the head, update the head pointer to the next node. If the list has only one node and it is deleted, set head to null. This keeps the circular linked list connected and updated after deletion.

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