What is the complexity of deletion from the middle of a list?
The complexity of deletion from the middle of a linked list is O(n) (linear).
Why this is so
To delete an element from the middle, you need to:
- Find this element, which means walking through the list from
headto the target node (this is already O(n)). - Reassign references:
- the previous node must now point to the one after the deleted node,
- and the deleted node "drops out" of the chain.
This second operation is O(1), but finding the position is O(n), and that is what determines the overall complexity.
Example
javascript
head → [10] → [20] → [30] → [40]
↑ delete this one- Walk to
[20], which takes time proportional to the number of nodes. - Change the previous node's reference:
[10].next = [30]. - Node
[20]is deleted.
If a reference to the node being deleted already exists
If the program already has a direct reference to the target node (rather than an index), then deletion is done in O(1), simply by reassigning references.
Formally
| Scenario | Complexity |
|---|---|
| Deletion by index (the node needs to be found) | O(n) |
| Deletion by a direct reference to the node | O(1) |
Comparison with an array
| Structure | Deletion from the middle |
|---|---|
| Array | O(n) - shifting all elements |
| Linked list | O(n) - finding the node (or O(1), if already found) |
Summary:
Deletion from the middle of a linked list takes O(n), because you need to walk to the target node before you can change the references.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.