Delete a Node from Circular Linked List in DSA C - Time & Space Complexity

Time Complexity: Delete a Node from Circular Linked List

O(n)

Understanding Time Complexity

When deleting a node from a circular linked list, we want to know how the time needed changes as the list grows.

We ask: How many steps does it take to find and remove the node?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteNode(Node** head, int key) {
    if (*head == NULL) return;
    Node *curr = *head, *prev = NULL;
    do {
        if (curr->data == key) {
            if (prev != NULL) prev->next = curr->next;
            else {
                // Find the last node to update its next pointer
                Node* last = *head;
                while (last->next != *head) {
                    last = last->next;
                }
                *head = curr->next;
                last->next = *head;
            }
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    } while (curr != *head);
}
    

This code searches for a node with a given value and deletes it from the circular linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the circular linked list nodes one by one.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the number of nodes to check grows too.

Input Size (n)	Approx. Operations
10	Up to 10 node checks
100	Up to 100 node checks
1000	Up to 1000 node checks

Pattern observation: The steps grow roughly in direct proportion to the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete a node grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Deleting a node in a circular linked list always takes constant time because we just remove it."

[OK] Correct: We must first find the node, which can take time proportional to the list size, so deletion is not always instant.

Interview Connect

Understanding this helps you explain how linked list operations scale and shows you can analyze real code efficiently.

Self-Check

"What if the list had a pointer to the node before the one to delete? How would the time complexity change?"