Pop Using Linked List Node in DSA C - Time & Space Complexity

Time Complexity: Pop Using Linked List Node

O(1)

Understanding Time Complexity

We want to understand how long it takes to remove the first item from a 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.

// Remove the first node from a linked list
Node* pop(Node** head) {
    if (*head == NULL) return NULL;
    Node* temp = *head;
    *head = (*head)->next;
    temp->next = NULL;
    return temp;
}
    

This code removes the first node from the linked list and returns it.

Identify Repeating Operations

• Primary operation: Accessing and updating the head pointer once.
• How many times: Exactly once per pop 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 steps
100	5 steps
1000	5 steps

Pattern observation: The number of steps stays the same as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means removing the first node takes the same short time no matter how big the list is.

Common Mistake

[X] Wrong: "Removing a node takes longer if the list is bigger because you have to look through all nodes."

[OK] Correct: We only remove the first node by changing the head pointer, no need to check other nodes.

Interview Connect

Knowing this helps you explain why linked lists are good for quick removals at the front, a common question in interviews.

Self-Check

"What if we wanted to remove the last node instead? How would the time complexity change?"