skip to content

For ArrayList versus LinkedList, why do memory overhead and cache locality often matter more than Big-O?

level: seniorimportance: should knowfreq 55%

answer

  1. Cache line; a RAM miss dwarfs a hit
  2. LinkedList node = value + next + prev + header
  3. ArrayList contiguous → prefetch-friendly; LinkedList nodes → pointer chasing
  4. Big-O hides constant factors and assumes uniform memory cost
  5. Prefer ArrayDeque over LinkedList

basics

~20 s

LinkedList uses much more memory because every element is a separate object with two extra links. Its nodes can scatter across the heap, so the CPU cache helps less, making it slower in real use even when Big-O looks equal.

solid answer

~50 s

ArrayList stores element references in one contiguous array, so memory overhead is small (just the references plus some spare capacity) and iteration is cache-friendly: the CPU prefetches the neighboring references. LinkedList allocates a separate node per element, carrying the value reference, next and previous references and the object header: 24 bytes against a 4-byte array slot when references are compressed. Worse, nodes can drift to scattered heap addresses, so walking the list means pointer chasing and frequent cache misses. CPUs fetch from main memory far more slowly than from cache, so even a plain O(n) iteration over a LinkedList is typically slower than over an ArrayList. This is why Big-O alone misleads: two O(n) operations can differ enormously in wall-clock time due to constant factors and locality. It is the main reason ArrayList is the practical default and ArrayDeque is preferred over LinkedList for queues.

go deeper

for a junior

Knows LinkedList uses more memory because each element is a separate linked object, and that ArrayList is generally faster.

for a middle

Quantifies the per-node overhead (value + two pointers + header) and explains that scattered nodes hurt iteration speed.

for a senior

Explains cache lines, prefetch, pointer chasing, and why constant factors/locality make two O(n) operations differ greatly in wall-clock time; recommends ArrayDeque.

for a principal

Reasons about allocation/GC pressure, footprint at scale, and hardware-aware data-structure choice; sets conventions and insists on measurement with realistic sizes and JIT-aware benchmarks.

## Background: how memory and the CPU cache work A modern CPU runs far faster than main memory (RAM) can feed it. To cope, it keeps small, fast **caches** between itself and RAM. When the CPU reads an address, it pulls in a whole **cache line** (a fixed-size block holding several adjacent references) at once, betting you'll soon need the neighbors too. This bet is **spatial locality**. It also **prefetches** ahead when it detects a sequential scan. A read served from cache is far cheaper than a **cache miss** that goes to RAM. So *where* data sits in memory often dominates performance more than the abstract operation count. ## ArrayList memory layout `ArrayList` is backed by a single contiguous array of references. For `N` elements it holds one array object plus `N` references (4 bytes each with compressed references, the default on heaps under about 32 GB, and 8 without) plus a bit of **spare capacity** (growth headroom, since it grows in ~1.5x jumps). Overhead is minimal and predictable. Because the references are packed side by side, iterating reads consecutive memory: each cache line brings in several references, prefetch kicks in, and misses on the array are rare. (Note: the *referenced objects* are still separate heap objects, boxed values and records included, and may be scattered; what's contiguous is the reference array, and shuffled elements do cost `ArrayList` some of its lead.) ## LinkedList memory layout `LinkedList` is a chain of `Node` objects. Each node stores: the element reference, a **next** reference, a **prev** reference, plus the JVM **object header** for bookkeeping (8 bytes on JDK 27, where compact object headers are the default; 12 bytes by default on JDK 25 LTS). With compressed references both versions come to a **24-byte node** against a 4-byte array slot: about **6x** per element, or about **5x** for a list grown to a million elements, whose array carries spare capacity. Without compressed references a node is 32 bytes on JDK 27 and 40 on JDK 25, against an 8-byte slot. Counting the elements themselves narrows the gap: for that million-element list with 16-byte `Integer` objects the whole structure costs about 2x. A list of one or two elements is the exception, because the first array of a `new ArrayList<>()` already has 10 slots. Nodes are separate objects with no layout guarantee. A list built in one go often sits close together, but as a list churns its nodes can end up at **scattered heap addresses**. Traversal is **pointer chasing**: read this node, follow its `next` pointer; when the next node is far away that is a cache miss, and a sequential prefetcher has no stride to follow. The result: even straightforward iteration, the same O(n) as ArrayList, is typically slower, and the gap widens as nodes scatter. ## Why this beats Big-O in practice Big-O describes how cost **scales** with size, hiding **constant factors** and assuming all memory access is uniform-cost. Real hardware violates that assumption brutally. Two O(n) loops can differ widely because one streams contiguous memory (cache hits) and the other chases pointers, with more cache misses. LinkedList's theoretical O(1) middle-relink advantage is usually swamped by (a) the O(n) traversal to reach the spot and (b) cache misses during that traversal. Meanwhile its memory bloat increases allocation, GC pressure, and footprint. ## Practical consequences - **Default to ArrayList** — smaller, faster to iterate, friendlier to the cache and GC. - **Prefer `ArrayDeque` over `LinkedList`** for stacks/queues/deques: it's array-backed (good locality) and has no per-node overhead, though it prohibits null elements. - **Reach for LinkedList only** when you specifically need O(1) insert/remove at a position you already hold (e.g. iterator-based removal) and you've measured a benefit. - **Measure, don't assume**: profile with realistic data sizes; microbenchmarks must account for JIT warmup and GC.

  • ArrayList's reference array is contiguous, but the referenced objects can still be scattered. Does locality still help?
    Yes. Streaming the contiguous reference array is itself cache-friendly. Even when target objects are scattered, ArrayList avoids LinkedList's extra hop through a node per element, so it has less pointer chasing to do and uses far less memory.
  • Why is ArrayDeque usually a better choice than LinkedList for a queue?
    ArrayDeque is backed by a circular array: O(1) amortized add/remove at both ends with no per-element node overhead and good cache locality, so its Javadoc calls it likely faster than LinkedList as a queue, and it is leaner. It prohibits null elements, which LinkedList permits.

  • Treating two O(n) operations as equally fast
  • Ignoring the JVM object header and per-node pointer cost
  • Claiming LinkedList saves memory
  • Assuming cache locality is negligible on modern hardware
  • Recommending LinkedList for queues instead of ArrayDeque

compact object headers
Java 25pre-release 24
compact object headers on by default
Java 27

Assumes JDK 27, where compact object headers are on by default (8-byte header); they were experimental in 24 and an opt-in product feature in 25. JDK 25 LTS defaults to a 12-byte header; with compressed references a LinkedList node is 24 bytes on both, and without them 32 on 27 and 40 on 25.

context