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

Time Complexity: Delete from End of Doubly Linked List

O(n)

Understanding Time Complexity

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

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code removes the last node from a doubly linked list by walking to the end and unlinking it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through nodes to find the last one.
• How many times: It runs once for each node until the end, so as many times as the list length.

How Execution Grows With Input

As the list gets longer, the time to reach the last node grows in a straight line.

Input Size (n)	Approx. Operations
10	About 10 steps to reach the end
100	About 100 steps to reach the end
1000	About 1000 steps to reach the end

Pattern observation: The steps increase directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Deleting the last node is always quick and takes constant time."

[OK] Correct: Without a pointer to the last node, we must walk through the whole list, so time grows with list length.

Interview Connect

Knowing how linked list operations scale helps you explain your code choices clearly and confidently.

Self-Check

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