Insert at Beginning Head Insert in DSA C - Time & Space Complexity

Time Complexity: Insert at Beginning Head Insert

O(1)

Understanding Time Complexity

We want to understand how long it takes to add a new item at the start of a linked list.

How does the time needed change as the list grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code adds a new node at the start of a linked list by adjusting pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	4 steps (allocate, assign data, link, update head)
100	4 steps (same as above)
1000	4 steps (same as above)

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

Final Time Complexity

Time Complexity: O(1)

This means adding at the start takes a fixed amount of time no matter how big the list is.

Common Mistake

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

[OK] Correct: We only change the head pointer and the new node's next pointer; no nodes are moved or visited.

Interview Connect

Knowing that inserting at the start is quick helps you choose the right method for fast updates in linked lists.

Self-Check

"What if we changed to insert at the end of the list? How would the time complexity change?"