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 adjusting pointers to skip that node while keeping the loop intact.

Analogy: Imagine people standing in a circle holding hands. Removing one person means the two neighbors hold hands directly, keeping the circle unbroken.

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 3 and keep the list circular without breaking the loop

Step 1: start at head node 1, look for node with value 3

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

Why: We need to find the node to delete by traversing the list

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

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

Why: Check next node to find the node to delete

Step 3: found node 3 as next of 2, update node 2's next to node 4

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

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

Step 4: node 3 is removed, list remains circular: 1 -> 2 -> 4 -> (back to 1)

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

Why: The circle is intact without node 3

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for circular linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode; // points to itself initially
    return newNode;
}

// Function to insert node at end of circular linked list
void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next; // advance to last node
    }
    temp->next = newNode; // last node points to new node
    newNode->next = *head; // new node points to head
}

// Function to delete node with given value from circular linked list
void deleteNode(Node** head, int key) {
    if (*head == NULL) return; // empty list

    Node *curr = *head, *prev = NULL;

    // If head node itself holds the key and list has only one node
    if (curr->data == key && curr->next == *head) {
        free(curr);
        *head = NULL;
        return;
    }

    // If head node holds the key and list has more than one node
    if (curr->data == key) {
        // Find last node to update its next pointer
        Node* last = *head;
        while (last->next != *head) {
            last = last->next; // advance to last node
        }
        last->next = curr->next; // last node points to second node
        *head = curr->next; // head updated to second node
        free(curr); // delete old head
        return;
    }

    // Search for the node to delete
    prev = curr;
    curr = curr->next;
    while (curr != *head && curr->data != key) {
        prev = curr;
        curr = curr->next; // advance curr and prev
    }

    // If node with key found
    if (curr != *head && curr->data == key) {
        prev->next = curr->next; // bypass curr
        free(curr); // delete node
    }
}

// Function to print circular linked list
void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next; // advance to next node
    } while (temp != head);
    printf("(back to head %d)\n", head->data);
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertEnd(&head, 4);

    printf("Original list:\n");
    printList(head);

    deleteNode(&head, 3);

    printf("After deleting node with value 3:\n");
    printList(head);

    return 0;
}

while (temp->next != *head) { temp = temp->next; }

advance temp to last node to insert new node at end

if (curr->data == key && curr->next == *head) { free(curr); *head = NULL; return; }

handle deletion when only one node exists and it matches key

if (curr->data == key) { find last node; update last->next; update head; free old head; return; }

handle deletion when head node matches key and list has multiple nodes

while (curr != *head && curr->data != key) { prev = curr; curr = curr->next; }

search for node with key by traversing list

if (curr != *head && curr->data == key) { prev->next = curr->next; free(curr); }

remove found node by bypassing it and freeing memory

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 only use a few pointers and no extra data structures

vs Alternative: Compared to singly linked list deletion which may require special handling for tail, circular list deletion keeps traversal simple but requires careful pointer updates to maintain the loop

Edge Cases

empty list

function returns immediately without changes

DSA C

if (*head == NULL) return;

list with one node which is the node to delete

node is freed and head set to NULL

DSA C

if (curr->data == key && curr->next == *head) { free(curr); *head = NULL; return; }

deleting the head node in a list with multiple nodes

head pointer updated and last node's next pointer updated to new head

DSA C

if (curr->data == key) { find last node; update last->next; update head; free old head; return; }

node with key 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 from a circular linked list, reach for pointer adjustment pattern because you must keep the loop intact while removing the 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 before deleting the old head

Mistake: Not handling the case when the list has only one node
Fix: Check if the node to delete is the only node and set head to NULL after deletion

Mistake: Stopping traversal too early or infinite loop by not checking circular condition
Fix: Use a do-while or carefully check if current node equals head again to stop traversal

Summary

Deletes a node with a given value from a circular linked list while keeping the list circular.

Use when you need to remove elements from a circular linked list without breaking the loop.

The key is to adjust pointers carefully so the circle remains unbroken after deletion.

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