Delete Node at Specific Position in DSA C - Time & Space Complexity

Time Complexity: Delete Node at Specific Position

O(n)

Understanding Time Complexity

We want to understand how the time to delete a node at a certain position in a linked list changes as the list grows.

How does the number of steps grow when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteNode(struct Node** head_ref, int position) {
    if (*head_ref == NULL) return;
    struct Node* temp = *head_ref;
    if (position == 0) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) return;
    struct Node* next = temp->next->next;
    free(temp->next);
    temp->next = next;
}
    

This code deletes a node at a given position in a singly linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that moves through the list to reach the node before the one to delete.
• How many times: Up to position - 1 times, depending on the position given.

How Execution Grows With Input

As the list gets longer, deleting a node near the start takes fewer steps, but deleting near the end takes more steps.

Input Size (n)	Approx. Operations (steps to reach position)
10	Up to 9 steps
100	Up to 99 steps
1000	Up to 999 steps

Pattern observation: The number of steps grows roughly in direct proportion to the position, which can be as large as the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete a node grows linearly with the size of the list in the worst case.

Common Mistake

[X] Wrong: "Deleting a node at any position always takes the same constant time."

[OK] Correct: Because we must first find the node before the one to delete, which can take longer if the position is far in the list.

Interview Connect

Understanding how linked list operations scale helps you explain your code clearly and shows you know how data size affects performance.

Self-Check

"What if the list was doubly linked? How would the time complexity of deleting a node at a specific position change?"