What is the complexity of inserting at the beginning of a list?
The complexity of inserting at the beginning of a linked list is O(1) (constant).
Why this is so
To add an element at the beginning of the list, you do not need to walk through the entire list. It is enough to:
- Create a new node.
- Set its
next(reference to the next node) to the oldhead. - Move
headto this new node.
Example:
javascript
Before:
head → [10] → [20] → [30]
After inserting 5:
head → [5] → [10] → [20] → [30]These three steps take constant time, regardless of the length of the list.
Formally
| Operation | Complexity |
|---|---|
| Insertion at the beginning | O(1) |
| Insertion in the middle | O(n) - you need to reach the target position |
| Insertion at the end | O(1), if there is a tail; otherwise O(n) |
Why this matters
This is one of the main advantages of linked lists over arrays:
- In an array, insertion at the beginning requires shifting all elements → O(n).
- In a list, it is enough to change a couple of references → O(1).
Summary:
Inserting a new element at the beginning of a linked list takes O(1), because you only need to reassign a single
headreference, without traversing the rest of the nodes.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.