skip to content

When would you choose ArrayList over LinkedList, and when (if ever) the reverse?

level: middleimportance: must knowfreq 78%

answer

  1. ArrayList = contiguous array, O(1) get, cache-friendly
  2. LinkedList = nodes + 2 pointers, O(n) get, cache-miss
  3. Big-O hides constants; memcpy beats pointer chasing
  4. Default ArrayList; LinkedList is niche
  5. For queue/deque prefer ArrayDeque over LinkedList

basics

~20 s

Use ArrayList almost always: it's a resizable array, fast for indexing and iteration, and cache-friendly. LinkedList mainly helps if you add/remove a lot at the very front or use it as a queue/deque — and even then ArrayDeque is usually better.

solid answer

~50 s

ArrayList is backed by a contiguous array: get(i) is O(1), iteration is fast and cache-friendly, and appends are amortized O(1). Its weakness is inserting/removing in the middle (O(n) shifting) and a costly resize when it grows. LinkedList is a doubly-linked list: O(1) insert/remove at the ends or through a ListIterator already in position, but get(i) is O(n) (it walks the chain), and every element gets its own heap node with two pointers, so it has poor cache locality and high memory overhead. In practice ArrayList usually wins because the constant factors and cache behavior dominate; even 'lots of middle inserts' reached by index is often faster on ArrayList because the array shift is a tight memcpy. The realistic case for LinkedList is queue/deque semantics — but ArrayDeque is likely to beat it there too, unless you need null elements. So: default to ArrayList; reach for LinkedList rarely.

code

java · 13 lines
java
// Random access: ArrayList shines
List<Integer> a = new ArrayList<>(1_000_000);
long sum = 0;
for (int i = 0; i < a.size(); i++) sum += a.get(i); // O(1) each

// Same loop on a LinkedList is a trap:
List<Integer> l = new LinkedList<>();
for (int i = 0; i < l.size(); i++) sum += l.get(i); // each get is O(n) -> O(n^2)!
// (Use an iterator/for-each on a LinkedList, never index it.)

// Queue/deque: prefer ArrayDeque over LinkedList
Deque<Integer> q = new ArrayDeque<>();
q.addFirst(1); q.addLast(2); q.pollFirst();

go deeper

for a junior

Knows ArrayList is the usual default and that it's array-backed with fast get(i).

for a middle

Gives the cost table, explains the front-insert vs random-access trade-off, and avoids indexing a LinkedList.

for a senior

Reasons about constant factors, cache locality, memory overhead, and resizing; recommends ArrayDeque over LinkedList for deque use.

for a principal

Treats it as a measurement-driven decision, considers GC pressure from many node allocations, and standardizes ArrayList/ArrayDeque defaults across a codebase.

## What each one is Both implement the **`List`** interface (ordered sequence, duplicates allowed, positional access), so they're interchangeable through that contract. The difference is the internal storage. - **`ArrayList`** wraps a single **contiguous array** (a backing array). The references sit next to each other in memory; the objects they point to live elsewhere on the heap. It tracks a `size`; when the array fills, it allocates a bigger one (typically ~1.5×) and copies everything over — this is **resizing**. - **`LinkedList`** is a **doubly-linked list**: each element has its own *node* object holding a reference to the value plus two references (`prev`, `next`). Nodes are scattered across the heap; the list keeps pointers to the first and last node. ## Cost profiles (Big-O *and* constant factors) | Operation | ArrayList | LinkedList | |---|---|---| | `get(i)` / `set(i)` | **O(1)** | O(n) — walks from an end | | append at end | amortized **O(1)** | O(1) | | insert/remove at index 0 | O(n) (shift all) | O(1) (the list keeps `first` and `last`) | | insert/remove in middle | O(n) (shift) | O(n) to *find* + O(1) to relink | | iteration | fast (cache-friendly) | slower (pointer chasing) | | memory per element | ~ one slot | value reference + 2 pointers + object header | **Big-O is not the whole story.** Big-O hides constant factors. ArrayList's O(n) middle insert is a single bulk `System.arraycopy` (essentially a `memcpy` the CPU loves). LinkedList's O(1) relink first needs an O(n) *traversal* to reach the spot, and each step risks a cache miss because the next node could be anywhere in memory. **Cache locality** — keeping data the CPU is about to use physically close so it stays in fast cache — strongly favors the contiguous array. This is why ArrayList usually wins when the position is reached by index, even though the linked list's relink alone is O(1). Where the position is already in hand (at the front, or at a `ListIterator`), LinkedList's O(1) holds and ArrayList pays its shift. ## Resizing and capacity Growth is ArrayList's other cost: each resize copies the whole array. If you know the size up front, pre-size with `new ArrayList<>(expectedSize)` to avoid repeated copies. Amortized over many appends, growth is still O(1) per element. ## When LinkedList actually helps - Frequent insert/remove at the **front** of a large list where you don't need random access (LinkedList front ops are O(1); ArrayList front ops are O(n)). - Inserts or removes through a `ListIterator` already in position (LinkedList relinks in O(1); ArrayList shifts the tail each time). - **Queue/Deque** usage (add/remove at both ends). But here **`ArrayDeque`** — a resizable circular array — is likely to be faster and is lighter than LinkedList, so prefer it unless you need `null` elements, which it prohibits. ## The practical rule **Default to `ArrayList`.** Reach for `LinkedList` for a measured workload dominated by front insertion or edits through a positioned `ListIterator`, with no random access, and even for queue/deque prefer `ArrayDeque`. Many experienced engineers go their whole career rarely needing LinkedList. The interview answer that scores is: 'ArrayList by default for cache locality and O(1) indexing; LinkedList is niche and usually outclassed by ArrayDeque for its supposed strengths.'

  • Why can indexing a LinkedList in a for-loop be O(n²)?
    Each get(i) walks from an end to position i (O(n)); doing that for every i across the whole list multiplies to O(n²). Iterate with an iterator/for-each (O(n) total) instead of indexing.
  • If you mostly add to the front and never random-access, is LinkedList the answer?
    It's the textbook case, but ArrayDeque (a circular array) usually still wins for front/back operations with far less memory overhead and better cache behavior. Measure before committing to LinkedList.

ArrayList is a row of numbered lockers in a wall — jump straight to locker 50, but inserting one in the middle means shifting everyone down. LinkedList is a paper chain where each link points to the next — you can splice in a new link instantly, but to find link 50 you must finger your way along all 50.

  • Claiming LinkedList is 'faster for inserts' without noting you must first traverse O(n) to reach the spot.
  • Recommending LinkedList for a queue/deque without mentioning ArrayDeque.
  • Indexing a LinkedList in a counted for-loop (accidental O(n²)).
  • Ignoring cache locality and memory overhead and reasoning purely from Big-O.

ArrayDeque
Java 1.6

context