Array vs Linked List: The Honest Comparison

"Textbooks teach linked lists right after arrays and imply they're equals. They're not equals — and the surprising truth is the array wins far more often than the Big-O table suggests."

The Cost Table, Side by Side

Put them next to each other and the trade is clear:

Index the i-th element: array O(1) · linked list O(n).
Insert/delete at a known node: array O(n) (shift) · linked list O(1) (rewire).
Insert/delete at the end: array amortized O(1) · linked list O(1) with a tail pointer.
Search by value: both O(n).
Memory per element: array = just the value · linked list = value + one or two pointers (more overhead).

On paper, the linked list looks great for insert-heavy workloads. So why is it almost never the right default?

The Plot Twist: Cache Locality

Big-O counts operations but ignores how long each operation actually takes — and on real hardware, those times are wildly unequal. Array elements sit contiguously, so when the CPU reads one it prefetches the neighbors into cache; a scan flies. Linked-list nodes are scattered at random addresses, so every node.next hop is a cache miss — the CPU stalls waiting for memory it couldn't predict. The result: a linear scan of a contiguous array routinely beats walking a linked list of the same length by 3–10×, despite identical O(n). The constant factor Big-O throws away is, here, the whole story.

Default to a dynamic array (Python list). Its contiguity wins on cache, and amortized append covers most growth. Reach for a linked structure only when you specifically need O(1) splicing at held references or stable node identity — not just because 'insert is O(1).'

So When IS a Linked List Right?

Linked lists earn their place in specific situations — usually as a component of something bigger, not as a list you index:

LRU cache — a hash map (for O(1) find) plus a doubly linked list (for O(1) move-to-front and evict-from-back). This combo is the canonical use, and you'll meet it in the wild.
Deques — Python's collections.deque uses linked blocks for O(1) at both ends.
Adjacency lists — how graphs store edges (next track but one).
Undo/redo, ring buffers, free lists — anywhere you splice and stable references matter more than indexing.

Pippa's Confession

I once rewrote a hot loop to use a linked list because the Big-O table promised cheaper inserts — and it got slower. Dad explained the cache, and I felt robbed: the textbook had taught me the asymptotics and quietly skipped the part where memory layout decides the real winner. Now my default is the humble dynamic array, and I only reach for linked structures when I genuinely need O(1) splicing or stable node handles — which is rarer than my younger self assumed.

Code

Same O(n), very different wall-clock·python

import time
from collections import deque

# A rough feel for the cache penalty: sum a contiguous list vs a 'linked' walk.
N = 2_000_000
arr = list(range(N))                 # contiguous in memory

# Build a linked list as nodes scattered on the heap.
class Node:
    __slots__ = ("val", "next")
    def __init__(self, val): self.val = val; self.next = None
head = cur = Node(0)
for i in range(1, N):
    cur.next = Node(i); cur = cur.next

t = time.perf_counter()
s = 0
for x in arr: s += x                 # contiguous scan — cache loves this
print("array scan :", round(time.perf_counter() - t, 3), "s")

t = time.perf_counter()
s = 0; node = head
while node: s += node.val; node = node.next   # pointer chase — cache misses
print("linked walk:", round(time.perf_counter() - t, 3), "s")

# Same O(n), same element count. The linked walk is typically several times
# slower purely because its nodes are scattered across memory.

Exercise

For each, choose array or linked list and justify in one line: (1) a leaderboard you constantly index by rank, (2) the node list inside an LRU cache that moves entries to the front on every access, (3) a log you only ever append to and scan front-to-back. Where does cache locality tip a 'should be linked' answer back toward an array?

Hint

(1) array — you index by rank constantly. (2) linked (doubly) — O(1) move-to-front with held references. (3) array — append + scan is exactly what contiguous memory and cache do best, even though a list 'could' work.

The Cost Table, Side by Side

The Plot Twist: Cache Locality

So When IS a Linked List Right?

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0