Insert at Middle Specific Position in DSA C - Time & Space Complexity

Time Complexity: Insert at Middle Specific Position

O(n)

Understanding Time Complexity

When we insert a new item at a specific middle position in a list, it takes some steps to find the right spot and then add the item.

We want to know how the time needed grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) return; // position out of bounds

    newNode->next = temp->next;
    temp->next = newNode;
}
    

This code inserts a new node at a given position in a singly linked list by first moving to the node before that position.

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 insertion point.
• How many times: Up to (position - 2) times, which depends on the input position.

How Execution Grows With Input

As the list gets longer, the number of steps to reach the insertion point grows roughly in proportion to the position.

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

Pattern observation: The time grows linearly as the position increases within the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows in a straight line with the size of the list or the position where we insert.

Common Mistake

[X] Wrong: "Inserting at the middle is always very fast and takes constant time."

[OK] Correct: Because we must first walk through the list to find the right spot, which takes time proportional to the position.

Interview Connect

Understanding how insertion time depends on position helps you explain and reason about linked list operations clearly in interviews.

Self-Check

"What if we had a pointer directly to the middle node? How would the time complexity change?"