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 deleting head, update head pointer

↓

Free node memory

↓

Done

Start at head, check if list is empty, traverse to find node, adjust pointers to remove it, update head if needed, then free memory.

Execution Sample

DSA C

void deleteNode(Node** head, int key) {
  if (*head == NULL) return;
  Node *curr = *head, *prev = NULL;
  do {
    if (curr->data == key) break;
    prev = curr;
    curr = curr->next;
  } while (curr != *head);
  if (curr->data != key) return;
  if (prev == NULL) {
    if (curr->next == *head) {
      *head = NULL;
    } else {
      Node *last = *head;
      while (last->next != *head) last = last->next;
      last->next = curr->next;
      *head = curr->next;
    }
  } else {
    prev->next = curr->next;
  }
  free(curr);
}

Deletes a node with given key from a circular linked list if it exists.

Execution Table

Step	Operation	Current Node Data	Prev Node Data	Pointer Changes	Visual State
1	Start at head	1	NULL	None	1 -> 2 -> 3 -> 4 -> (back to 1)
2	Check if list empty	1	NULL	None	1 -> 2 -> 3 -> 4 -> (back to 1)
3	Check if current node data == key (3)?	1	NULL	No match	1 -> 2 -> 3 -> 4 -> (back to 1)
4	Move prev to current, current to next	2	1	None	1 -> 2 -> 3 -> 4 -> (back to 1)
5	Check if current node data == key (3)?	2	1	No match	1 -> 2 -> 3 -> 4 -> (back to 1)
6	Move prev to current, current to next	3	2	None	1 -> 2 -> 3 -> 4 -> (back to 1)
7	Check if current node data == key (3)?	3	2	Match found	1 -> 2 -> 3 -> 4 -> (back to 1)
8	Adjust pointers: prev->next = curr->next	3	2	2->next = 4	1 -> 2 -> 4 -> (back to 1)
9	If deleting head? No (head=1)	3	2	Head unchanged	1 -> 2 -> 4 -> (back to 1)
10	Free node with data 3	3	2	Node 3 removed	1 -> 2 -> 4 -> (back to 1)
11	Done	-	-	-	1 -> 2 -> 4 -> (back to 1)

💡 Node with data 3 found and deleted; list updated accordingly.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	Final
curr	Node(1)	Node(2)	Node(3)	Node(3)	Node(3) (deleted)
prev	NULL	Node(1)	Node(2)	Node(2)	Node(2)
head	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)

Key Moments - 3 Insights

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

Because the list is circular, we must check the current node before moving to next to avoid skipping the head node. The do-while ensures we visit the head node at least once (see steps 3-7 in execution_table).

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

If deleting the head, we must update the head pointer to the next node to keep the list accessible. In this example, the deleted node is not head (step 9), so head remains unchanged.

Why do we adjust prev->next to curr->next when deleting?

Because we remove curr from the chain, prev must point to curr's next to keep the list connected. This pointer change is shown in step 8.

Visual Quiz - 3 Questions

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

A Node with data 3

B Node with data 2

C Node with data 4

D NULL

💡 Hint

Check the 'curr' column in variable_tracker after step 6.

At which step does the pointer 'prev->next' get updated to remove the node?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at the 'Pointer Changes' column in execution_table.

If the node to delete was the head node (data 1), what would change in the execution?

A Head pointer would be updated to next node

B No pointer changes needed

C List would become empty immediately

D Deletion would not be possible

💡 Hint

Refer to key_moments about deleting the head node.

Concept Snapshot

Delete Node in Circular Linked List:
- Start at head, check empty list
- Traverse nodes using do-while to find target
- If found, adjust prev->next to skip target
- Update head if deleting head node
- Free memory of deleted node
- List remains circular after deletion

Full Transcript

To delete a node from a circular linked list, we start at the head and check if the list is empty. We then traverse the list using a do-while loop to find the node with the target data. Once found, we adjust the previous node's next pointer to skip the node to delete, effectively removing it from the list. If the node to delete is the head, we update the head pointer to the next node to maintain access. Finally, we free the memory of the deleted node. The list remains circular after deletion, connecting the last node back to the head.

Practice

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

easy

A. The list becomes empty (head = 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

Solution

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

   It has one node whose next pointer points to itself.

2. Step 2: Delete the only node

   After deletion, no nodes remain, so the head pointer must be set to NULL to indicate an empty list.

3. Final Answer:

   The list becomes empty (head = NULL) -> Option A

4. Quick Check:

   Single node deleted means empty list [OK]

Hint: Deleting last node empties list, set head to NULL [OK]

Common Mistakes:

• Not setting head to NULL after deleting the only node
• Assuming list still has one node after deletion
• Confusing circular list with linear list after deletion

2. Which of the following is the correct syntax to delete the head node in a circular linked list in C?

easy

A. head = NULL; free(head);

B. head->next = NULL; free(head);

C. free(head); head = NULL;

D. Node* oldHead = head; head = head->next; free(oldHead);

Solution

1. Step 1: Understand deletion of head node in circular linked list

   We must move head pointer to next node and free the old head node.

2. Step 2: Check syntax correctness

   Node* oldHead = head; head = head->next; free(oldHead); correctly assigns head to head->next and frees the old head pointer stored separately.

3. Final Answer:

   Node* oldHead = head; head = head->next; free(oldHead); -> Option D

4. Quick Check:

   Move head, free old node [OK]

Hint: Move head to next, then free old head [OK]

Common Mistakes:

• Freeing head before moving pointer
• Setting next pointer to NULL breaks circular link
• Freeing NULL pointer

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. 20 -> 30 -> (back to 20)

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

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

Solution

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

   Node with value 20 is between 10 and 30.

2. Step 2: Adjust pointers to remove node 20

   Set 10's next pointer to 30, skipping 20, maintaining circular link.

3. Final Answer:

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

4. Quick Check:

   Removed 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 by setting next to NULL
• Deleting wrong node

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

void deleteNode(Node** head, int key) {
  Node* curr = *head;
  Node* prev = NULL;
  while (curr->data != key) {
    prev = curr;
    curr = curr->next;
  }
  prev->next = curr->next;
  free(curr);
}

medium

A. It does not handle deleting the head node correctly

B. It frees the wrong node

C. It causes infinite loop always

D. It sets head to NULL incorrectly

Solution

1. Step 1: Analyze deletion logic for head node

   If the node to delete is head, prev is NULL, so prev->next causes error.

2. Step 2: Identify missing head update

   Code does not update *head when deleting head node, causing incorrect list state.

3. Final Answer:

   It does not handle deleting the head node correctly -> Option A

4. Quick Check:

   Head deletion needs special handling [OK]

Hint: Check if node to delete is head before pointer update [OK]

Common Mistakes:

• Not updating head pointer when deleting head
• Dereferencing NULL prev pointer
• Not checking if node exists before deletion

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

hard

A. Set head to head->next, free old head, leave last node's next unchanged

B. Find last node, set its next to head->next, free head, update head to head->next

C. Free head, set head to NULL, list becomes empty

D. Set head->next to NULL, free head, update head to next node

Solution

1. Step 1: Locate last node in circular list

   Traverse nodes until node whose next points to head is found (node with value 20).

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

   Set last node's next to head->next (node with value 10), free old head, and update head pointer to head->next.

3. Final Answer:

   Find last node, set its next to head->next, free head, update head to head->next -> Option B

4. Quick Check:

   Last node points to new head after deletion [OK]

Hint: Update last node's next before freeing head [OK]

Common Mistakes:

• Not updating last node's next pointer
• Freeing head before updating pointers
• Breaking circular link by setting next to NULL