Insert at Beginning Head Insert in DSA Python - 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 bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

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 a new node and updating pointers.
• How many times: This happens once per insert, no loops or traversals involved.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	3 (create node, set next, update head)
100	3 (same steps)
1000	3 (still the same steps)

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 beginning takes a fixed amount of time no matter how big the list is.

Common Mistake

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

[OK] Correct: We only change a few pointers; we do not move or visit other nodes, so time stays constant.

Interview Connect

Knowing that head insertion is quick helps you choose the right method when speed matters in linked lists.

Self-Check

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