Delete from Beginning of Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Delete from Beginning of Doubly Linked List

O(1)

Understanding Time Complexity

We want to understand how long it takes to remove the first item from a doubly linked list.

How does the time needed change when the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Delete node from beginning of doubly linked list
void deleteBeginning(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
}
    

This code removes the first node from a doubly linked list and updates pointers accordingly.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single pointer update and node deletion.
• How many times: Exactly once per call, no loops or recursion.

How Execution Grows With Input

Removing the first node always takes the same steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	5-6 steps
100	5-6 steps
1000	5-6 steps

Pattern observation: The number of steps stays the same regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means deleting the first node takes a constant amount of time no matter how large the list is.

Common Mistake

[X] Wrong: "Deleting from the beginning takes longer as the list grows because we have to move through nodes."

[OK] Correct: We only change a few pointers at the start; we do not traverse the list, so time does not grow with list size.

Interview Connect

Knowing that deleting from the start of a doubly linked list is quick helps you explain efficient list operations clearly in interviews.

Self-Check

"What if we changed this to delete from the end of the doubly linked list? How would the time complexity change?"