Arrays and linked lists solve the same surface problem: storing a collection of elements. But the way each one does it produces radically different trade-offs. Choosing wrong isn't a syntax error — it's a design error that scales badly.
Arrays: contiguous memory
An array occupies one continuous block of memory. Each element sits immediately after the previous one, with no gaps.
So given any element's index, computing its memory address takes a single operation:
dirección = dirección_base + (índice × tamaño_de_elemento)
Reaching array[42] is exactly as fast as reaching array[0]. No traversal, no pointers to follow. It's guaranteed O(1).
const nums = [10, 20, 30, 40, 50]
console.log(nums[3]) // 40 — one operation, no matter how big the array is
The cost is insertion and deletion. If you insert in the middle, you have to shift every element after it to make room. If you delete from the middle, you have to close the gap. Both operations are O(n) in the worst case.
// Insert at position 2 of an array of 1 million elements:
// → the elements at positions 2 through 999,999 all shift one place forward
nums.splice(2, 0, 99) // O(n) — not O(1)
Fixed size. A low-level array (as in C, or Java without wrappers) has its size fixed at declaration time. It can't grow. This isn't a language bug — it's the direct consequence of contiguous memory: there's no guarantee the bytes after the array are available.
Linked lists: pointers instead of contiguity
A linked list doesn't occupy one continuous block. Each element lives at its own memory address and holds a pointer to the next one.
// Conceptual structure of a node
{
value: 10,
next: → { value: 20, next: → { value: 30, next: null } }
}
The direct consequence: there is no access by index. To reach element 42, you have to start at the first one and follow 42 pointers. That's O(n).
What is O(1) is inserting or deleting at the head of the list. Nothing shifts — you just redirect pointers.
// Insert at the head of a linked list:
const nuevoNodo = { value: 99, next: cabeza }
cabeza = nuevoNodo
// Two operations, no matter how big the list is
Inserting or deleting at any position is also O(1) if you already hold the pointer to the previous node. The work is in finding that node — which is O(n).
Singly vs. doubly linked list
A singly linked list has one pointer, to the next node. Traversal goes forward only.
A doubly linked list has pointers to the previous node and the next one. Traversal is bidirectional, and deleting a known node is O(1) without having to find the one before it.
// Doubly linked list node
{
value: 30,
prev: → nodo_anterior,
next: → nodo_siguiente
}
The cost: twice the memory overhead per node, and more complexity in every operation that modifies the list.
Cache locality: why arrays win in practice
There's one factor asymptotic complexity doesn't capture: the processor cache.
When the CPU reads a memory address, it automatically loads a block of neighboring bytes into cache (a cache line). If the next access falls inside that same cache line, it's instant. If it doesn't, you get a cache miss — and going out to RAM is orders of magnitude slower.
Arrays are cache-friendly. The elements are contiguous, so walking an array is a run of cache hits.
Linked lists are cache-unfriendly. The nodes are scattered across memory. Every pointer you follow probably points at an address that isn't in cache. Walking a linked list of a million elements can be dramatically slower than walking the equivalent array, even though both are O(n) on paper.
In real benchmarks, an array can be 5x to 10x faster than a linked list for traversal, even when the asymptotic complexity is identical.
Dynamic arrays: the bridge between the two worlds
In practice, most code uses dynamic arrays — arrays that grow automatically when they fill up. They're ArrayList in Java, vector in C++, and lists in Python.
Internally, a dynamic array is a static array with reserved capacity. When it fills up, it creates a bigger array (usually double the size), copies every element across, and discards the original.
That copy costs O(n), but it happens so rarely that the amortized cost of insertion is still O(1) (as we saw in the previous article). Access by index stays O(1).
Dynamic arrays capture the best of static arrays — fast access, cache locality — without the fixed-size ceiling. That's why they're the default structure in almost every modern language.
The comparison that matters
| Operation | Array | Linked list |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at the head | O(n) | O(1) |
| Insert at the tail | O(1) amortized | O(1) with a tail pointer |
| Insert in the middle | O(n) | O(1) with a pointer to the previous node |
| Deletion | O(n) | O(1) with a pointer to the previous node |
| Cache locality | Excellent | Poor |
| Memory overhead | None | One pointer per node (two, if doubly) |
| Dynamic size | Requires a copy | Native |
When to use each one
Use arrays (or dynamic arrays) when:
- You need frequent access by index
- You walk the collection sequentially
- The size is relatively stable, or grows mostly at the end
- Cache locality matters (almost always)
Use linked lists when:
- You insert and delete frequently at the head or in the middle, and you hold pointers to those nodes
- The size varies dramatically and the dynamic array's copy overhead is unacceptable
- You're implementing higher-level structures — stacks, queues, and many kinds of trees are built on top of linked lists
In practice, most production code uses arrays or dynamic arrays almost all the time. Linked lists show up when the insertion/deletion problem is critical enough to justify giving up direct access and cache locality.
The simple rule: when in doubt, start with your language's dynamic array. Switch to a linked list only when you have concrete evidence that insertions are the bottleneck.