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.