Interview Prep Zoneby CuriouserLabs

Question 3 of 5 · senior level

ArrayList vs LinkedList — when is each appropriate? Why does Big-O alone mislead here?

🎤 Say this first

Almost always ArrayList. Its backing array gives O(1) indexed access and — thanks to cache locality and amortized growth — faster iteration and usually faster inserts than LinkedList in practice. LinkedList's O(1) insert/remove only applies at a known node (via its Iterator or Deque ends); getting to position i is O(n) with terrible cache behavior. Big-O ignores constants, memory layout and per-node overhead — which dominate on real hardware.

The full picture

OperationArrayListLinkedListReality check
get(i)O(1)O(n)no contest
add at endO(1) amortizedO(1)ArrayList still wins — no node allocation
insert middleO(n) shiftO(n) traverse + O(1) linkSystem.arraycopy is vectorized; ArrayList often wins anyway
memory/element~4–8 bytes ref~40+ bytes (node + 2 refs + header)LinkedList also scatters nodes → cache misses

The senior takeaway: mechanical sympathy. CPUs prefetch contiguous memory; an ArrayList scan streams through cache lines, while a LinkedList chases pointers to random heap addresses. Legitimate LinkedList niches are rare — it's a decent Deque, but ArrayDeque beats it there too. If you're inserting/removing heavily at both ends or mid-iteration, consider ArrayDeque, or re-think the algorithm (often a different data structure — ring buffer, gap buffer, or just collect-then-rebuild — is the real answer).

🔄 Likely follow-up questions

  • How does ArrayList grow, and what does that mean for a loop of a million adds without pre-sizing?
  • Why was LinkedList's author himself quoted as preferring ArrayList?
  • What's the difference between subList and a copy — and the aliasing bug it invites?