Insert at Beginning of Doubly Linked List in DSA C - Time & Space Complexity

Time Complexity: Insert at Beginning of Doubly Linked List

O(1)

Understanding Time Complexity

We want to understand how the time needed to insert a new node at the start of a doubly linked list changes as the list grows.

Specifically, how does the work change when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->prev = NULL;
    newNode->next = *head;
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}
    

This code creates a new node and inserts it at the start of the doubly linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating and linking one new node.
• How many times: Only once per insertion, no loops or repeated traversals.

How Execution Grows With Input

Adding a node at the start always takes the same steps, no matter how long the list is.

Input Size (n)	Approx. Operations
10	About 5 steps
100	About 5 steps
1000	About 5 steps

Pattern observation: The number of steps stays the same regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means inserting at the beginning takes a constant amount of time no matter how big the list is.

Common Mistake

[X] Wrong: "Inserting at the beginning takes longer as the list grows because we have to move all nodes."

[OK] Correct: We only change a few pointers at the start; we do not move or visit other nodes.

Interview Connect

Knowing that insertion at the start is quick helps you explain efficient list operations clearly and confidently.

Self-Check

"What if we changed this to insert at the end of the doubly linked list without a tail pointer? How would the time complexity change?"