Interview frequency: …
Short answer
Arrays benefit from spatial locality and alignment with CPU cache lines, while linked-list nodes are scattered randomly across the heap.
Explanation
Array elements are stored in contiguous memory. When the processor reads an element, it automatically fetches the surrounding block (usually a 64-byte cache line) into the L1/L2 cache, so the next elements are ready within nanoseconds without accessing RAM. Each linked-list node, by contrast, is allocated at a random memory location and needs an extra pointer, causing repeated cache misses.
Code example
import time
N = 1_000_000
array = list(range(N)) # contiguous: elements share cache lines
class Node:
__slots__ = ("value", "next")
def __init__(self, value, next=None):
self.value, self.next = value, next
head = None
for v in reversed(range(N)):
head = Node(v, head) # nodes are scattered across the heap
def sum_array():
return sum(array)
def sum_linked_list():
total, node = 0, head
while node:
total += node.value
node = node.next # pointer chasing → frequent cache misses
return total
for fn in (sum_array, sum_linked_list):
start = time.perf_counter()
fn()
print(fn.__name__, f"{time.perf_counter() - start:.3f}s")Common mistakes
- Believing that a linked list is always better than an array for O(1) insertion at the beginning, ignoring that node allocation and cache misses make a dynamic array faster in most small practical cases.