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 only 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 at a known node, but get(i) is O(n) (it walks the chain), and every element is a separate heap node with two pointers, so it has poor cache locality and high memory overhead. In practice ArrayList wins almost always because the constant factors and cache behavior dominate; even 'lots of middle inserts' is often faster on ArrayList because the array shift is a tight memcpy. The realistic case for LinkedList is queue/deque semantics — but ArrayDeque beats it there too. 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 elements sit next to each other in memory. 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 lives in its own *node* object holding 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) *if you hold the node* | | 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 + 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 is 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 benchmarks usually show ArrayList beating LinkedList even on workloads that 'theoretically' favor the linked list. ## Resizing and capacity ArrayList's only real weakness is growth: 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)). - **Queue/Deque** usage (add/remove at both ends). But here **`ArrayDeque`** — a resizable circular array — is almost always faster and lighter than LinkedList, so prefer it. ## The practical rule **Default to `ArrayList`.** Reach for `LinkedList` only for a measured front-insertion-heavy, no-random-access workload, 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.

saying these in an interview costs you the question

  • 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.

context

resolving links…