Arrays and linked lists both store an ordered sequence of values, and nearly every computer science course teaches them back to back — yet the decision of which one to reach for in real code trips up even experienced developers. The two structures make opposite tradeoffs: an array packs values into contiguous memory for fast, predictable access; a linked list scatters nodes across memory and connects them with pointers for fast splicing. Picking correctly means matching the tradeoff to the actual access pattern, not the one assumed by habit.
What changed in 2026
- Modern CPUs widened the performance gap further. Cache lines, prefetching, and SIMD-friendly memory layouts all favor contiguous data, so the real-world penalty for pointer-chasing in a linked list has grown, not shrunk, compared to a decade ago.
- Most languages default toward arrays already. Python lists, JavaScript arrays, Java ArrayList, Rust Vec, and Go slices are all dynamic arrays under the hood — opting into a linked list is a deliberate choice, which is itself a signal about how rarely production code needs one.
- Intrusive linked lists remain common in systems code. Kernels, embedded systems, and lock-free queues still use linked lists heavily, because avoiding allocation and copy costs matters more than cache locality in those contexts.
How the two structures actually differ
An array stores its elements in one contiguous block of memory. The address of element i is computed directly (base + i * element_size), so reading or writing any index is O(1) with no traversal.
A linked list stores each value in its own node, along with a pointer to the next node (and, for a doubly linked list, the previous one too). Nodes can live anywhere in memory. Reaching element i means starting at the head and following i pointers — O(n).
Array: [10][20][30][40][50] one block, indexable directly
Linked list: 10 -> 20 -> 30 -> 40 -> 50 scattered nodes, pointer-chained
Complexity comparison
| Operation |
Array (dynamic) |
Linked list |
| Read by index |
O(1) |
O(n) |
| Search by value |
O(n) |
O(n) |
| Insert/delete at end |
O(1) amortized |
O(1) with a tail pointer |
| Insert/delete at start |
O(n) |
O(1) |
| Insert/delete at a known node |
O(n), shifting |
O(1) |
| Memory overhead |
Low, values only |
Higher, pointer per node |
| Cache locality |
Excellent |
Poor |
When each one genuinely wins
Reach for an array when the workload mostly reads, iterates, or indexes — dashboards, data processing, or a plain list of records where lookups matter more than mid-sequence inserts. It is the correct default.
Reach for a linked list when the code repeatedly inserts or removes at a position it already holds a reference to, and random access is not needed. The textbook example is an LRU cache usage-order list, an undo/redo history, or a scheduler ready queue — cases where splicing at a known node happens far more often than jumping to an arbitrary index.
The scenario matrix
| Scenario |
Better choice |
Why |
| Iterating over all elements |
Array |
Sequential memory access, cache-friendly |
| Random access by index |
Array |
O(1) versus O(n) |
| Frequent inserts at a known node |
Linked list |
O(1) splice, no shifting |
| Undo/redo history |
Linked list, often doubly |
Constant-time push/pop at both ends |
| Queue with unknown final size |
Either, deque preferred |
Most languages deque beats both extremes |
| Small, fixed-size collections |
Array |
Pointer overhead is not worth it below a few hundred elements |
Common mistakes
Assuming O(1) insertion makes a linked list faster overall. Insertion is only O(1) once positioned at the right node. Getting there usually costs O(n), the same as an array shift — the O(n) cost has just moved from one step to another.
Ignoring Big-O notation constants. A linked list O(1) operations carry real overhead — pointer dereferencing, cache misses, allocation — that a dynamic array amortized O(1) append usually beats in wall-clock time despite sharing the same asymptotic class.
Defaulting to a linked list out of interview habit. Coding interviews overuse linked lists because they test pointer manipulation cleanly, not because the structure reflects how often it is the right production choice.
FAQ
Is a dynamic array, like a Python list, still an array for this comparison?
Yes. Dynamic arrays occasionally reallocate and copy to grow, but reads stay O(1) and the cache-locality argument holds; the comparison is unchanged.
Do doubly linked lists change any of this?
They add O(1) removal without a separate previous-node lookup and O(1) insertion before a known node, at the cost of a second pointer per node. The core access-pattern argument stays the same.
Which one should be used for a queue?
Neither extreme, usually — a ring-buffer-backed deque, as most standard libraries provide, gives O(1) push/pop at both ends with array-level cache locality, beating a plain linked list in practice.
Where to go next