Why contiguous Data Structures (DS) are faster than non-contiguous DS

Daksh Goel — Sun, 20 Sep 2026 09:25:18 +0000

Summary:

The massive performance gap between contiguous DS and node-base structures is due to CPU Cache lines and spatial locality.

Deep Dive:

RAM Bottleneck:

CPU is very fast, but RAM is slow. To prevent CPU from idling, CPU is fitted with CPU Caches (L1, L2, L3).

This includes 2 major things:

Spatial Locality: States that, if a program accesses a specific memory address, it will almost certainly need the data at the immediately adjacent address very soon.

Cache Lines: Because of spatial locality, CPU grabs a fixed-size block of contiguous memory all at once. Generally it's 64 bytes long contiguous block in modern machines.

Contiguous Memory DS (eg. Arrays):

Perfect spatial locality.

When you read the first item (say, 4-byte integer) in an array, the CPU fetches a 64-byte cache line from RAM. This brings first integer + the next 15 integer immediately. When the loop moves to the 2nd, 3rd, ..... items, the CPU doesn't have to wait for RAM; the data is already present in the L1-cache (a cache hit). You only suffer a slow RAM fetch once every 16 steps.

Non-contiguous Memory DS (eg. Linked List):

Linked List nodes are dynamically allocated, meaning they are scattered randomly across the heap wherever there happens to be free space.

When you ask for the first node, the CPU fetches a 64-byte cache line from RAM. However, because the next node is stored at a completely different, random memory address, the rest of that cache line is filled with unrelated data.