skip to content

Given a real-world scenario, how do you decide between ArrayList and LinkedList — and why is ArrayList almost always the right default?

level: middleimportance: must knowfreq 70%

answer

  1. Default = ArrayList
  2. Match the dominant operation to the structure
  3. Front/end add-remove → ArrayDeque, not LinkedList
  4. LinkedList niche = O(1) iterator removal on large lists
  5. 'LinkedList is better for inserts' is a myth (search is still O(n))

basics

~20 s

Use ArrayList by default — it's faster for reading by index and uses less memory. Only consider LinkedList for constant adds or removes at or near the start, at the end, or through an iterator. At the ends, ArrayDeque is usually better.

solid answer

~50 s

Start from ArrayList as the default: most code builds a list, iterates it, and looks things up by index, all of which ArrayList does fast and cheaply. Choose based on the dominant operation. If you do lots of random access by index or mostly iterate, ArrayList wins on both speed and memory. LinkedList only has an edge when you frequently insert/remove at the ends, near the front, or at a position you already hold via an iterator, because that skips or shortens the O(n) search. But for queue/stack/deque needs ArrayDeque is likely faster and leaner than LinkedList, and for bulk filtering ArrayList's removeIf is linear too. So the honest rule is: default to ArrayList, use ArrayDeque for end-based add/remove, and pick LinkedList mainly for the narrow iterator-removal case, after measuring. Don't choose based on the myth that LinkedList is 'better for insertions.'

go deeper

for a junior

Defaults to ArrayList and can say it's faster for reading by index and uses less memory.

for a middle

Picks based on the dominant operation, knows the front-insert and iterator-removal cases, and knows to reach for ArrayDeque for queues.

for a senior

Debunks the insertion myth, weighs memory/cache and realistic data sizes, suggests removeIf/rebuild alternatives, and insists on measurement before deviating from ArrayList.

for a principal

Establishes team defaults and review guidance, frames the choice in terms of workload profiling, allocation/GC impact, and API boundaries (program to List), avoiding premature micro-optimization.

## The decision framework Choosing a `List` implementation is about matching your **dominant operations** to the structure's strengths. Both implement the same `List` interface, so switching later is usually a one-line change. ### Step 1: Default to ArrayList The vast majority of list usage is: add items (usually at the end), iterate over them, and occasionally fetch by index. `ArrayList` is excellent at all three — O(1) index access, amortized O(1) append, and cache-friendly iteration with low memory. So **start there** and only deviate with a concrete reason. ### Step 2: Identify your dominant operation - **Random access by index** (`list.get(i)` in a hot loop): ArrayList, definitively — it's O(1) vs LinkedList's O(n). - **Plain iteration**: ArrayList — better cache locality means it's faster even at the same Big-O. - **Append at end**: both are fine; ArrayList is amortized O(1). - **Frequent add/remove at the front**: ArrayList front-ops are O(n) (shifting). This is the classic case people cite for LinkedList — but the right answer is usually **ArrayDeque** (array-backed, amortized O(1) at both ends, great locality). - **Remove/insert while iterating** (you hold an `Iterator` at the spot): LinkedList's relink is O(1) here, vs ArrayList's O(n) shift. This is LinkedList's main genuine niche, though for a bulk filter `ArrayList.removeIf` is linear too. - **Queue/stack/deque** (add/remove at ends): use **ArrayDeque**, not LinkedList, unless you need null elements, which ArrayDeque prohibits. ### Step 3: Account for memory and cache LinkedList costs far more memory (each element is a 24-byte node with two pointers + object header, against a 4-byte slot when references are compressed), and its nodes can scatter across the heap, so even iteration can suffer cache misses. ArrayList is compact and contiguous. This is why LinkedList's theoretical advantages rarely show up in benchmarks — and why ArrayList is the practical default. ### Step 4: Debunk the myth The statement "LinkedList is better for insertions" is misleading. Inserting at an **arbitrary index** requires first **finding** that index — O(1) for ArrayList, O(n) traversal for LinkedList. So both are O(n) for index-based insertion, and ArrayList's contiguous shift usually beats LinkedList's traversal-plus-cache-misses. LinkedList only wins when you skip or shorten the search (ends, positions near the front, or an iterator cursor). ## Worked examples - **A list of search results rendered in a UI**: build once, iterate, index occasionally → **ArrayList**. - **A work queue: producers add, consumers poll from the front**: → **ArrayDeque** (not LinkedList). - **Filtering a list in place**: → **ArrayList with `removeIf`** (linear: it marks matches, then compacts). **LinkedList**'s asymptotic edge is over a hand-written `Iterator.remove()` loop on ArrayList, which shifts on every removal; measure. - **Lookup table accessed by index thousands of times**: → **ArrayList**. ## The honest rule of thumb 1. **Default: ArrayList.** 2. **Need a queue/stack/deque (ends only): ArrayDeque.** 3. **Need O(1) removal while iterating a large list: consider LinkedList, after measuring.** 4. Never choose LinkedList just because of the 'better insertion' myth — and don't micro-optimize without profiling realistic data.

  • A teammate wants LinkedList for a queue because 'add/remove is O(1).' What do you suggest?
    ArrayDeque. It's also O(1) amortized at both ends but is array-backed, so it has no per-node overhead and better cache locality, and its Javadoc calls it likely faster than LinkedList as a queue. The exception is a queue that must hold nulls, which ArrayDeque prohibits.
  • You must remove every element matching a predicate from a 10-million-element list in one pass. Which list, and is there a simpler option?
    LinkedList gives O(1) removals via Iterator.remove(), avoiding repeated shifts. But often simpler: build a new ArrayList with the survivors, or use removeIf, which on ArrayList marks matches in one pass and compacts in a second, linear overall with no per-removal shift. Measure both.

  • Reflexively picking LinkedList 'because of insertions' without measuring
  • Forgetting ArrayDeque exists as the better deque/queue
  • Choosing based on Big-O alone, ignoring locality and memory
  • Assuming switching later is hard (it's a one-liner via the List interface)
  • Using LinkedList for index-heavy access

context