Delete Node at Beginning in DSA C - Time & Space Complexity

Time Complexity: Delete Node at Beginning

O(1)

Understanding Time Complexity

We want to know how the time needed changes when we delete the first node in a linked list.

How does the work grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteAtBeginning(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}
    

This code removes the first node from a linked list by moving the head pointer to the next node and freeing the old first node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and updating the head pointer once.
• How many times: Exactly once per deletion.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	4 steps
100	4 steps
1000	4 steps

Pattern observation: The work stays the same even if the list grows larger.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "Deleting the first node takes longer if the list is bigger because we have to check all nodes."

[OK] Correct: We only change the head pointer and free one node; we do not look at other nodes.

Interview Connect

Understanding this helps you explain how simple operations on linked lists work efficiently, a key skill in many coding tasks.

Self-Check

"What if we had to delete the last node instead? How would the time complexity change?"