Array vs linked list: when does it matter?
An array gives O(1) access by index but O(n) insertion in the middle. A linked list gives O(1) insertion once you hold the node, but O(n) to find anything.
| Operation | Array | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Search by value | O(n) | O(n) |
| Insert or delete at front | O(n) | O(1) |
| Insert or delete at end | O(1)* | O(1) with a tail pointer |
| Insert in the middle | O(n) | O(1) once you are there |
| Memory overhead | None | A pointer per node |
\* Amortised — occasionally the backing array is reallocated and copied.
#Why arrays usually win anyway
Array elements sit next to each other in memory, so reading one pulls its neighbours into CPU cache. Linked list nodes are scattered, so each hop is a potential cache miss — often 100× slower than a cache hit.
In practice, a dynamic array beats a linked list for most workloads even where the complexity table says otherwise. The constants are that different.
#Where linked lists genuinely win
- LRU caches — you must remove a node from the middle and you already hold a pointer to it.
- Anything requiring stable references — array reallocation invalidates pointers; list nodes never move.
- Building the underlying structure of a queue or stack when you cannot pre-size.
#What you actually use
Python's list, JavaScript's Array, C#'s List<T>, Ruby's Array and PHP's array are all dynamic arrays. There is no built-in linked list in most of these languages, and that is not an oversight.
If you need fast operations at both ends, use a deque (collections.deque in Python), which is a linked list of small arrays and gets both properties.