Delete by Value in Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Delete by Value in Doubly Linked List

O(n)

Understanding Time Complexity

When deleting a node by value in a doubly linked list, we want to know how long it takes as the list grows.

We ask: How does the time to find and delete a value change with list size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through nodes to find the value.
• 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 search may take longer because it might 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 by value grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Deleting by value is always fast because we just remove one node."

[OK] Correct: You must first find the node, which can take time proportional to the list size if the value is near the end or missing.

Interview Connect

Understanding this helps you explain how searching affects deletion speed in linked lists, a common topic in coding interviews.

Self-Check

"What if the list was sorted? How would that change the time complexity of deleting by value?"