Suggest an editImprove this articleRefine the answer for “What is the complexity of deletion from the middle of a list?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)The complexity of **deletion from the middle of a linked list** is **O(n)** (linear). **Key point:** reassigning references by itself is O(1), but finding the position of the target node takes O(n), and that is what determines the overall complexity.Shown above the full answer for quick recall.Answer (EN)ImageThe 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: 1. **Find** this element, which means walking through the list from `head` to the target node (this is already **O(n)**). 2. **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 ``` 1. Walk to `[20]`, which takes time proportional to the number of nodes. 2. Change the previous node's reference: `[10].next = [30]`. 3. 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.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.