What is the complexity of accessing an element by index?

The complexity of accessing an element by index in a linked list is O(n) (linear).

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]

If a list contains 1,000 elements, and you need to get the element at index 900, the algorithm has to take 900 steps.

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)

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.

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.