Insert at Specific Position in Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Insert at Specific Position in Doubly Linked List

O(n)

Understanding Time Complexity

When inserting a new node at a specific position in a doubly linked list, we want to know how the time needed changes as the list grows.

We ask: How many steps does it take to find the right spot and insert the node?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

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

    newNode->next = temp->next;
    if (temp->next) temp->next->prev = newNode;
    temp->next = newNode;
    newNode->prev = temp;
}
    

This code inserts a new node at a given position by first moving through the list to find the correct spot, then adjusting pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that moves through the list nodes to reach the position before insertion.
• How many times: Up to (pos - 2) times, depending on the position where we insert.

How Execution Grows With Input

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

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 with the position number, so doubling the list size roughly doubles the steps needed.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Inserting at any position in a doubly linked list always takes constant time O(1)."

[OK] Correct: You must first find the position by moving through the list, which takes time proportional to the position number, so it is not always instant.

Interview Connect

Understanding how insertion time depends on position helps you explain trade-offs in linked list operations clearly and confidently.

Self-Check

"What if we kept a pointer to the tail of the list and wanted to insert near the end? How would the time complexity change?"