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

Time Complexity: Delete Node at End

O(n)

Understanding Time Complexity

When we delete a node at the end of a linked list, we want to know how the time taken changes as the list grows.

We ask: How much work does the computer do when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code deletes the last node of a singly linked list by traversing to the second last node and removing the last.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list nodes.
• How many times: It runs once for each node until the second last node, so roughly n-1 times for n nodes.

How Execution Grows With Input

As the list gets longer, the loop runs more times, almost once per node except the last.

Input Size (n)	Approx. Operations
10	About 9 steps through nodes
100	About 99 steps through nodes
1000	About 999 steps through nodes

Pattern observation: The work grows roughly in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete the last node grows directly with the list size.

Common Mistake

[X] Wrong: "Deleting the last node is always quick because it's at the end."

[OK] Correct: We must find the node before the last, which takes time proportional to the list length.

Interview Connect

Understanding this helps you explain how linked lists work and why some operations take longer as data grows.

Self-Check

"What if we kept a pointer to the last node? How would the time complexity change when deleting the last node?"