ArrayList and LinkedList: Memory and Cache Architecture

While ArrayList is a dynamic array and LinkedList is a doubly-linked list, the performance difference goes far beyond simple $O(1)$ vs. $O(n)$ complexity. The real impact lies in memory footprint, CPU cache locality, and native instruction efficiency.

1. ArrayList: Continuous Memory & Native Speed

1.1 The Address Formula

ArrayList stores elements in a contiguous Object[] array. Accessing index i is a simple arithmetic operation: TargetAddress = BaseAddress + i * ReferenceSize.

1.2 The 1.5x Expansion Strategy

When the array is full, ArrayList grows by 1.5 times. This expansion factor is chosen to allow the memory allocator to potentially reuse old memory blocks later in the process.

1.3 Native Copying

Resizing uses System.arraycopy(), a native method mapped to C++ memmove. Modern JVMs utilize SIMD instructions to move large chunks of memory at once, making expansion incredibly fast.

2. LinkedList: The Pointer-Chasing Tax

2.1 Memory Overhead

In a 64-bit JVM, a LinkedList Node occupies 24 bytes per element (Header + Prev + Next + Item). An ArrayList reference occupies only 4 bytes.

2.2 Cache Misses

• ArrayList: A CPU cache line holds 16 consecutive references. Accessing the next element is a hit.
• LinkedList: Nodes are scattered. Every node.next jump is likely a Cache Miss, forcing a 100ns fetch from RAM.

3. The "Insertion" Myth

Many claim LinkedList is faster at insertions. This is only true if you already hold the reference (e.g., using an Iterator). To insert at index i from the list head, LinkedList must first traverse to that index, which is $O(n)$. For almost all workloads, ArrayList's $O(n)$ array shift is faster than LinkedList's $O(n)$ pointer chase.