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

Concept Flow - Delete a Node from Circular Linked List

Start at head

↓

Check if list empty?

Yes→Stop: Nothing to delete

No↓

Traverse nodes to find target

↓

Found node to delete?

No→Stop: Node not found

Yes↓

Adjust pointers to remove node

↓

If node is head, update head

↓

If only one node, list becomes empty

↓

Delete node and update size

↓

Done

Start from head, check if list is empty, traverse to find node, adjust pointers to remove it, update head if needed, handle single node case, then finish.

Execution Sample

DSA C++

void deleteNode(Node*& head, int key) {
  if (!head) return;
  Node *curr = head, *prev = nullptr;
  do {
    if (curr->data == key) break;
    prev = curr;
    curr = curr->next;
  } while (curr != head);
  if (curr->data != key) return; // not found
  if (head->next == head) { // single node
    delete head;
    head = nullptr;
    return;
  }
  if (prev == nullptr) { // delete head
    Node* last = head;
    while (last->next != head) last = last->next;
    last->next = head->next;
    Node* temp = head;
    head = head->next;
    delete temp;
  } else {
    prev->next = curr->next;
    delete curr;
  }
}

This code searches for a node with given key in a circular linked list, handles special cases (empty, not found, single node, head), and deletes the node by adjusting pointers.

Execution Table

Step	Operation	Current Node	Prev Node	Nodes in List	Pointer Changes	Visual State
1	Start at head	10	null	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
2	Check if list empty	10	null	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
3	Compare current data with key=30	10	null	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
4	Move prev=10, curr=20	20	10	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
5	Compare current data with key=30	20	10	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
6	Move prev=20, curr=30	30	20	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
7	Found node with key=30	30	20	10 -> 20 -> 30 -> 40 -> (back to 10)	None	10 -> 20 -> 30 -> 40 -> (head)
8	Adjust prev->next to curr->next	30	20	10 -> 20 -> 40 -> (back to 10)	20->next = 40	10 -> 20 -> 40 -> (head)
9	If curr is head? No	30	20	10 -> 20 -> 40 -> (back to 10)	None	10 -> 20 -> 40 -> (head)
10	Delete node 30	null	null	10 -> 20 -> 40 -> (back to 10)	Free node 30	10 -> 20 -> 40 -> (head)
11	Done	null	null	10 -> 20 -> 40 -> (back to 10)	None	10 -> 20 -> 40 -> (head)

💡 Node with key 30 found and deleted; list updated with 3 nodes remaining.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	Final
head	10	10	10	10	10
curr	10	20	30	30	null
prev	null	10	20	20	null
list size	4	4	4	3	3

Key Moments - 3 Insights

Why do we use a do-while loop instead of a while loop to traverse?

Because the list is circular, we must check the current node before moving to next to avoid skipping the head node. See execution_table steps 3-6 where traversal starts at head and loops until back to head.

What happens if the node to delete is the head?

We must update the head pointer to the next node after deletion. In this example, at step 9, since curr is not head, head remains same. If it was head, we would update head to curr->next.

How do we handle deleting the only node in the list?

If the list has one node and it matches the key, after deletion the list becomes empty (head = null). This is a special case not shown here but important to check before deletion.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'curr' at Step 6?

A 10

B 30

C 20

D 40

💡 Hint

Check the 'Current Node' column at Step 6 in the execution_table.

At which step does the list size decrease?

A Step 4

B Step 10

C Step 8

D Step 11

💡 Hint

Look at the 'list size' variable in variable_tracker after each step.

If the node to delete was the head (10), what pointer change would happen?

A head updated to head->next

B prev->next points to head

C curr set to null immediately

D No pointer changes needed

💡 Hint

Refer to key_moments about head node deletion and execution_table step 9.

Concept Snapshot

Delete Node in Circular Linked List:
- Start at head, check empty list
- Traverse nodes with do-while to find key
- If found, adjust prev->next to skip node
- If deleting head, update head pointer
- Handle single node case (list empty after deletion)
- Free deleted node memory

Full Transcript

To delete a node from a circular linked list, start at the head node. If the list is empty, stop immediately. Use a do-while loop to traverse the list because the list loops back to head. At each node, check if the node's data matches the key to delete. If found, adjust the previous node's next pointer to skip the current node, effectively removing it from the list. 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 matches the key, after deletion the list becomes empty. Finally, free the memory of the deleted node. The example shows deleting node with value 30 from list 10 -> 20 -> 30 -> 40 -> (back to 10), resulting in 10 -> 20 -> 40 -> (back to 10).

Practice

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

easy

A. The list becomes empty (head points to null).

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

C. The list becomes a linear linked list.

D. The list throws an error and stops.

Solution

1. Step 1: Understand single-node circular list

   A circular linked list with one node points to itself.

2. Step 2: Delete the only node

   Removing this node leaves no nodes, so head becomes null.

3. Final Answer:

   The list becomes empty (head points to null). -> Option A

4. Quick Check:

   Single node deleted = empty list [OK]

Hint: Deleting last node empties list, head = null [OK]

Common Mistakes:

• Assuming list still has one node after deletion
• Not updating head to null
• Confusing circular with linear list after deletion

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

easy

A. void deleteNode(Node head, int key) { /* code */ }

B. void deleteNode(Node* head, int key) { /* code */ }

C. void deleteNode(Node*& head, int key) { /* code */ }

D. void deleteNode(int key, Node* head) { /* code */ }

Solution

1. Step 1: Understand pointer passing in C++

   To modify the head pointer itself, pass it by reference (Node*& head).

2. Step 2: Check parameter order and types

   Function should accept head reference first, then key to delete.

3. Final Answer:

   void deleteNode(Node*& head, int key) { /* code */ } -> Option C

4. Quick Check:

   Pass head by reference to modify it [OK]

Hint: Pass head as reference to update list head [OK]

Common Mistakes:

• Passing head by value (won't update original list)
• Wrong parameter order
• Passing head as object, not pointer or reference

3. Given the circular linked list: 10 -> 20 -> 30 -> (back to 10), what is the list after deleting node with value 20?

medium

A. 10 -> 20 -> 30 -> (back to 10)

B. 10 -> 30 -> (back to 10)

C. 20 -> 30 -> (back to 20)

D. 30 -> 10 -> (back to 30)

Solution

1. Step 1: Identify node to delete

   Node with value 20 is between 10 and 30.

2. Step 2: Remove node 20 and link 10 to 30

   Update 10's next pointer to 30, maintaining circular link.

3. Final Answer:

   10 -> 30 -> (back to 10) -> Option B

4. Quick Check:

   Deleted 20, linked 10 to 30 [OK]

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

Common Mistakes:

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

4. What is wrong with this code snippet for deleting a node from a circular linked list?

void deleteNode(Node*& head, int key) {
  if (!head) return;
  Node* curr = head;
  while (curr->next != head && curr->next->data != key) {
    curr = curr->next;
  }
  if (curr->next->data == key) {
    Node* temp = curr->next;
    curr->next = temp->next;
    delete temp;
  }
}

medium

A. Does not handle deleting the head node correctly.

B. Does not check if list is empty.

C. Deletes node without updating pointers.

D. Infinite loop due to wrong while condition.

Solution

1. Step 1: Analyze deletion logic

   Code searches for node before target and deletes next node.

2. Step 2: Check head deletion case

   If node to delete is head, head pointer is not updated, causing errors.

3. Final Answer:

   Does not handle deleting the head node correctly. -> Option A

4. Quick Check:

   Head deletion needs special handling [OK]

Hint: Update head if deleted node is head [OK]

Common Mistakes:

• Ignoring head node deletion
• Not updating head pointer
• Assuming node always exists

5. You have a circular linked list: 5 -> 15 -> 25 -> 35 -> (back to 5). You want to delete the node with value 5 (head node). Which steps correctly update the list?

hard

A. Swap head data with next node and delete next node.

B. Delete head node directly without updating last node's next.

C. Set head to null without deleting any node.

D. Find last node (35), set its next to head's next (15), update head to 15.

Solution

1. Step 1: Locate last node

   Traverse list to find node pointing to head (value 35).

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

   Set last node's next to head's next (node with value 15).

3. Step 3: Update head pointer

   Set head to head's next (15) to maintain circular list.

4. Final Answer:

   Find last node (35), set its next to head's next (15), update head to 15. -> Option D

5. Quick Check:

   Update last node and head to delete head node [OK]

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

Common Mistakes:

• Not updating last node's next pointer
• Not updating head pointer
• Deleting head without fixing links