Course contentsShow
← Java
Lesson 1043 of 2,87024. List ImplementationsFree lesson

Cache Locality and Performance Impact

ArrayList benefits from CPU cache locality; LinkedList nodes scattered in heap hurt performance.

Cache Locality and Performance Impact

You'll learn: Why ArrayList often outperforms LinkedList in practice, even when Big-O analysis suggests otherwise—thanks to how CPUs cache memory.

The CPU Cache Advantage

Modern CPUs don't fetch data one byte at a time from main memory. Instead, they load chunks of nearby memory into ultra-fast cache storage. When you access one array element, the CPU typically loads neighboring elements into cache "for free."

ArrayList benefits enormously from this: Because its backing array stores elements in contiguous memory, accessing list.get(0) often brings list.get(1), list.get(2), and many more into cache automatically. When you iterate through an ArrayList, you're reading from lightning-fast cache memory most of the time.

LinkedList suffers here: Each node is a separate object allocated somewhere in the heap—potentially far from the previous and next nodes. Accessing node.next likely triggers a cache miss, forcing the CPU to fetch from slow main memory. Every iteration step may require a new memory fetch.

The Real-World Impact

This is why ArrayList often wins even for operations where LinkedList has better Big-O complexity. Adding to the beginning? LinkedList is O(1) vs ArrayList's O(n)—but if you're only adding a few items, ArrayList's cache-friendly operations can complete faster than LinkedList's scattered memory accesses.

Think of it like reading a book where all pages are bound together (ArrayList) versus following clues scattered across different buildings in a city (LinkedList). Even if the clue hunt has fewer "steps," walking between buildings takes far longer.

Key Takeaway:
Cache locality gives ArrayList a significant real-world performance advantage beyond theoretical time complexity—prefer ArrayList unless you have specific, measured reasons to use LinkedList.