Delete Node by Value in DSA C - Time & Space Complexity

Time Complexity: Delete Node by Value

O(n)

Understanding Time Complexity

We want to know how the time needed to delete a node by value changes as the list grows.

How does the number of steps grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteNodeByValue(Node** head, int value) {
    Node* temp = *head;
    Node* prev = NULL;
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // value not found
    if (prev == NULL) *head = temp->next; // delete head
    else prev->next = temp->next;
    free(temp);
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the 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 gets longer, the search takes more steps because it may check more nodes.

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

Pattern observation: The number of steps grows 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 by value always takes constant time because we just remove it."

[OK] Correct: We must first find the node by checking nodes one by one, which can take time proportional to the list size.

Interview Connect

Understanding how searching affects deletion time helps you explain linked list operations clearly and confidently.

Self-Check

"What if the list was doubly linked? How would the time complexity of deleting a node by value change?"