Suggest an editImprove this articleRefine the answer for “What is the complexity of accessing an element by index?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)The complexity of **accessing an element by index** in a linked list is **O(n)** (linear). **Key point:** to reach the node at index `i`, the program must start at `head` and walk through all preceding nodes, so accessing an element by index takes O(n).Shown above the full answer for quick recall.Answer (EN)ImageThe complexity of **accessing an element by index** in a linked list is **O(n)** (linear). --- ### **Why this is so** In a linked list, elements **are not laid out sequentially in memory**, as in an array. Each element (node) stores only: - its own data, - a reference to the **next** node (or also to the previous one, in a doubly linked list). So, to reach the node at index `i`, the program must **start at** `head` **and walk through all preceding nodes**: ```javascript head → [0] → [1] → [2] → [3] ↑ you need to walk through all of this to reach [3] ``` --- ### **Example** If a list contains 1,000 elements, and you need to get the element at index 900, the algorithm has to take **900 steps**. --- ### **Formally** | Operation | Complexity | |---|---| | Access to the first element | **O(1)** | | Access to the last one (via tail) | **O(1)** - if `tail` is stored separately | | Access to the element at index i | **O(n)** | | Average complexity | **O(n/2)** ≈ **O(n)** | --- ### **Comparison with an array** | Structure | Access by index | |---|---| | **Array** | **O(1)** - instant (the address is computed) | | **Linked list** | **O(n)** - you need to walk through all preceding nodes | --- **Summary:** > In a linked list, accessing an element by index takes **O(n)**, > because you need to walk through all preceding nodes, starting from `head`.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.