Memory — Why Structures Have Different Speeds

Two structures can have identical Big O and differ by a factor of ten in practice. Big O counts operations; it does not know that some operations wait on memory. This post is the part the complexity table leaves out.

Stack and heap

Java puts your data in two places.

int count = 5;                        // the value 5 lives on the stack
int[] numbers = new int[1000];        // `numbers` is a reference on the stack;
                                      // the 1000 ints are on the heap

This is why recursion has a depth limit and a loop does not: each call keeps a frame on that small stack until it returns.

Contiguous versus scattered

Here is the fact that the complexity table cannot express.

An int[1_000_000] is one block of four million bytes. Element 500 is immediately after element 499, always.

A linked list of a million integers is a million separate Node objects, allocated whenever they were created and sitting wherever the allocator had room. Following the list means jumping around the heap.

Both are O(n) to scan. They are not remotely the same speed, and the reason is the cache.

Cache lines

Your CPU does not read one byte from RAM. It reads a cache line — 64 bytes on essentially every current machine — into a cache that is far faster than main memory. Roughly:

Main memory is on the order of a hundred times slower than L1. So the question that decides real performance is not how many elements you touch, it is how often you have to go out to RAM to get them.

Now put the two layouts against that. An int is 4 bytes, so one 64-byte cache line holds 16 consecutive array elements. Scanning an array, one trip to memory serves the next sixteen reads — and the hardware prefetcher, noticing the straight-line access pattern, fetches the following lines before you ask.

Walking a linked list, each node is somewhere else. Every step is potentially its own trip to main memory, and the prefetcher cannot help because it cannot guess the next address until the current node has been read. That is pointer chasing, and it is why the array wins by a wide margin at the same O(n).

What a node actually costs

The other half of the story is size. On a 64-bit JVM with compressed references — the default for heaps under 32 GB — a linked list node holding one int costs roughly:

Against 4 bytes per element in an int[]. The linked list uses about six times the memory to store the same numbers — and worse, it is Integer objects rather than ints, because generics cannot hold primitives, so each value is itself a separate 16-byte heap object with its own reference to chase.

Six times the memory means six times as many cache lines to hold the same data, which means the cache holds a sixth as much of it. The layout penalty compounds.

// Contiguous, 4 bytes per element, no boxing.
int[] values = new int[1000];

// A List cannot hold primitives, so every element is a boxed Integer object:
// the ArrayList's own array holds 1000 references, and each points at a separate
// 16-byte object elsewhere on the heap.
List<Integer> boxed = new ArrayList<>();

What to do with this

1. Prefer arrays and ArrayList by default. Contiguous layout is usually worth more than the theoretical advantage of a linked structure.
2. Use primitive arrays in hot loops. int[] over List<Integer> where it matters — you avoid both the boxing and the chasing.
3. Size collections up front when you know roughly how many elements are coming. new ArrayList<>(10_000) skips a chain of resize-and-copy.
4. Do not conclude that linked lists are useless. O(1) insertion at a known position is real, and it is what makes LinkedHashMap's eviction order cheap.

⚠️ And do not over-apply it

All of the above is a tiebreaker between structures with the same complexity. It never beats choosing the right complexity class. A linked list with a hash index will demolish a contiguous array that you scan linearly, every time, no matter how cache-friendly the array is — O(1) beats O(n) long before cache behaviour gets a vote.

Get the complexity right first. Which is what Big O is for.