Compare the memory overhead and cache locality of ArrayList and LinkedList. Why do these often matter more than Big-O in practice?

## 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** (typically 64 bytes — several adjacent elements) 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 costs a few cycles; a **cache miss** that goes to RAM can cost hundreds. 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 or 8 bytes each) 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 elements, prefetch kicks in, and misses are rare. (Note: the *referenced objects* themselves may still be scattered on the heap; what's contiguous is the reference array — already a big win, and for primitives-as-objects or `record`-heavy data the locality benefit is real.) ## 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** (12-16 bytes for bookkeeping like the class pointer and mark word). So a node costs roughly the element reference plus ~24-40 bytes of pure overhead — often **~3x** the memory of the equivalent ArrayList slot. Nodes are allocated independently and end up at **scattered heap addresses**. Traversal is **pointer chasing**: read this node, follow its `next` pointer to an unrelated address, almost certainly a cache miss, repeat. Prefetch can't help because the next address isn't predictable. The result: even straightforward iteration — same O(n) as ArrayList — runs several times slower. ## 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 5-10x because one streams contiguous memory (cache hits) and the other chases pointers (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. - **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.