skip to content

When would you choose ArrayList over LinkedList, and why does ArrayList usually win in practice?

level: seniorimportance: should knowfreq 75%

answer

  1. ArrayList = contiguous array; LinkedList = scattered nodes
  2. Cache locality -> ArrayList wins iteration/scan
  3. get(i): ArrayList O(1), LinkedList O(n)
  4. LinkedList only helps with node-in-hand inserts
  5. Real choice is ArrayList vs ArrayDeque

basics

~20 s

Use ArrayList for almost everything: fast index access and compact memory. LinkedList only helps for constant-time inserts/removes when you already hold the spot, which is rare, and it uses more memory and is slower to scan.

solid answer

~40 s

ArrayList stores elements in one contiguous Object[]; LinkedList stores each element in a separate node object holding the value plus next/previous references. The practical consequences favor ArrayList: contiguous storage is cache-friendly, so iteration and random access are far faster on real CPUs, and there is no per-element node overhead (~24+ bytes each). ArrayList gives O(1) indexed get/set; LinkedList's get(i) is O(n) because it walks the chain. LinkedList's theoretical advantage is O(1) insert/remove once you hold the node (e.g. via a ListIterator), and O(1) at the head — but to reach an arbitrary position you still walk O(n), and the cache misses make it lose most benchmarks. So: default to ArrayList; for queue/deque-at-the-ends use ArrayDeque (better than both); reach for LinkedList essentially never. The real choice is ArrayList vs ArrayDeque, not ArrayList vs LinkedList.

go deeper

for a junior

Knows ArrayList is the usual default and LinkedList stores items as linked nodes.

for a middle

Compares get/insert complexities and knows ArrayList has O(1) index access while LinkedList does not.

for a senior

Explains cache locality and node overhead, recommends ArrayDeque for ends, and treats LinkedList as almost never the right choice.

for a principal

Articulates why uniform-cost Big-O misleads here, drives decisions by measured behavior and memory hierarchy, and sets team guidance defaulting to ArrayList/ArrayDeque.

## The two layouts Both implement the `List` interface, but store data completely differently: - **ArrayList**: one big contiguous array (`Object[]`). Element i lives at a computable address, packed next to its neighbors. - **LinkedList**: a **doubly-linked list** — each element is wrapped in a separate heap `Node` object containing the value plus a reference to the **next** and **previous** nodes. Nodes are scattered across the heap. ## What 'cache-friendly' means (the deciding factor) Modern CPUs read memory in **cache lines** (~64 bytes) and prefetch sequential memory. When data is **contiguous** (ArrayList), scanning it streams through cache with almost no stalls. When data is **scattered** (LinkedList nodes), each `next` pointer hop is likely a **cache miss** — the CPU waits ~100x longer for main memory. This is why ArrayList iteration crushes LinkedList in real benchmarks, even where Big-O looks equal. ## Operation-by-operation | Operation | ArrayList | LinkedList | |---|---|---| | get(i) / set(i) | O(1) | O(n) (walks the chain) | | add at end | O(1) amortized | O(1) | | add/remove at front | O(n) (shift) | O(1) | | add/remove in middle (by index) | O(n) (shift) | O(n) (walk) + O(1) splice | | add/remove holding the node/iterator | n/a | O(1) | | memory per element | one array slot (~8 bytes ref) | node object: value + 2 refs + object header (~24-40 bytes) | | iteration speed | fast (cache) | slow (pointer chasing) | ## LinkedList's narrow real advantage LinkedList only wins when you do **many insertions/removals at a position you already hold** — typically via a `ListIterator` walking once and editing as it goes, or repeated head operations. Even then, **ArrayDeque** is usually a better queue/deque: it is array-backed (cache-friendly), gives O(1) at both ends, and has lower overhead. So the genuinely useful comparison is **ArrayList vs ArrayDeque**, not ArrayList vs LinkedList. ## Decision guide - Random access / read-heavy / iteration → **ArrayList**. - Append-heavy, read by index → **ArrayList**. - FIFO queue or stack / add-remove at ends → **ArrayDeque**. - Frequent middle insert/remove on huge lists where you hold an iterator → maybe LinkedList, but **measure**; ArrayList often still wins. - Need thread safety → `CopyOnWriteArrayList` (read-heavy) or `Collections.synchronizedList`, or a concurrent queue. ## The principal-level point 'LinkedList is faster for inserts' is a textbook claim that ignores the **memory hierarchy**. In practice, big-O on a uniform-cost model overstates LinkedList. Even Java's own author Josh Bloch has noted LinkedList rarely earns its keep. Default to ArrayList and justify any deviation with a benchmark.

  • If insert/remove at the ends is your pattern, why prefer ArrayDeque over LinkedList?
    ArrayDeque is array-backed, so it has O(1) at both ends like LinkedList but with cache-friendly contiguous storage and no per-node object overhead, making it faster and leaner in practice.
  • Why can two structures have the same Big-O yet very different real speed?
    Big-O on a uniform-cost model ignores the memory hierarchy. Contiguous data streams through CPU cache, while pointer-chasing causes cache misses that can be ~100x slower, so constant factors differ massively.

saying these in an interview costs you the question

  • 'LinkedList is always faster for insertions' (ignores O(n) lookup + cache misses)
  • Claiming LinkedList has O(1) get(i)
  • Recommending LinkedList as a default queue instead of ArrayDeque
  • Ignoring per-node memory overhead
  • Quoting Big-O without considering cache behavior

context

resolving links…