All topics
1 / 101
collections
beginner

ArrayList vs LinkedList

Pick the list backed by an array (fast random access) or by a doubly-linked list (fast insert/remove at known nodes).

Both ArrayList and LinkedList hold a list of items. They store those items very differently. ArrayList keeps them side by side in one block of memory, like seats in a row. LinkedList scatters them, and each item holds the address of the next and previous one.

ArrayList = a bookshelf with numbered slots (instantly grab #7). LinkedList = a paper chain (snip and rejoin links easily, but counting to the 7th link takes time).

Key Concepts

1
That difference decides which is faster, and the answer is not the one the textbook table suggests.
2
This is the question that catches people who learned data structures from a table rather than from a machine. On paper LinkedList wins at insertion; in practice ArrayList wins almost everywhere, and explaining why is the whole point of the question.
LinkedListArrayList
3
The structures. ArrayList holds a contiguous Object[] and grows by allocating a larger array — 1.5x in the OpenJDK implementation — and copying. LinkedList is a doubly-linked chain of nodes, each holding an element reference plus two node references.
ArrayListObject[]LinkedList
4
Memory is the first surprise. An ArrayList slot costs one reference: 4 bytes with compressed oops. A LinkedList node costs an object header (16 bytes) plus three references (12 bytes) = ~32-40 bytes per element, eight to ten times more. For a million Integer elements that is roughly 4 MB against 40 MB before counting the boxed values themselves.
ArrayListLinkedListInteger
5
Cache locality is the second, and it dominates. Array elements sit together, so walking one pulls the next several into the CPU cache line for free. Linked nodes are scattered across the heap, so each step is a potential cache miss costing ~100 ns against ~1 ns for an L1 hit. Iterating a large LinkedList can be an order of magnitude slower than the same ArrayList even though both are "O(n)".
LinkedListArrayList
6
The theoretical advantage almost never applies. LinkedList.add(index, e) is O(1) *once you hold the node*, but reaching index i is O(n) traversal, so insertion in the middle is O(n) overall — the same as ArrayList's shift, except ArrayList's shift is System.arraycopy, an intrinsic that moves contiguous memory far faster than pointer chasing. The genuine wins are insertion at the ends and removal through an iterator you already hold.
LinkedList.add(index, e)iArrayListSystem.arraycopy
7
ArrayList has one cost worth naming: growth copies. Adding a million elements from an empty list triggers around 30 reallocations and copies ~2 million element slots in total. new ArrayList<>(expected) removes it, which is the same pre-sizing argument as HashMap.
ArrayListnew ArrayList<>(expected)HashMap
8
What to answer when asked which to use. ArrayList by default. ArrayDeque if you need a queue or stack — it beats LinkedList at both. LinkedList when you genuinely need Deque semantics and removal via iterator in the middle of a large structure, which is rare enough that many codebases have none.
ArrayListArrayDequeLinkedListDeque
9
What the interviewer is probing.1. "Which is faster for insertion?" Probing: whether you repeat the table or reason about machines. Stalls: "LinkedList, it's O(1)." Moves up: O(1) only with the node in hand; finding the position is O(n), and arraycopy beats pointer chasing.
arraycopy
10
2. "Why is iteration slower on LinkedList?" Probing: cache behaviour. Stalls: "It's the same complexity." Moves up: scattered nodes cause cache misses — ~100 ns versus ~1 ns per step.
11
3. "How much more memory?" Probing: concrete numbers. Stalls: "A bit more." Moves up: ~32-40 bytes per node against 4 bytes per array slot, so ~10x for the structure itself.
12
4. "When would you actually pick LinkedList?" Probing: honesty. Stalls: "For frequent inserts." Moves up: rarely — ArrayDeque covers queue and stack use; LinkedList fits iterator-based removal in a large list.
ArrayDequeLinkedList
13
5. "How does ArrayList grow?" Probing: the amortised cost. Stalls: "It doubles." Moves up: 1.5x in OpenJDK; ~30 reallocations reaching a million, avoidable by pre-sizing.
14
  Cost per element (64-bit JVM, compressed oops)
15
    ArrayList slot        reference                        4 B
    LinkedList node       header 16 + item 4 + prev 4
                          + next 4                        28-32 B
                          (aligned)                       ~32-40 B
16
    1,000,000 elements    ArrayList  structure            ~4 MB
                          LinkedList structure          ~32-40 MB
17
  Operation costs, and what actually happens
18
  Operation              ArrayList          LinkedList
  ------------------------------------------------------------------
  get(i)                 O(1)               O(n) traversal
  add(e) at end          O(1) amortised     O(1)
  add(0, e)              O(n) arraycopy     O(1)
  add(mid, e)            O(n) arraycopy     O(n) to find + O(1)
  remove via iterator    O(n) shift         O(1)
  contains(e)            O(n)               O(n), cache-hostile
  Iteration              sequential memory  pointer chasing
19
  Growth cost, empty ArrayList to 1,000,000 elements
    growth factor                              1.5x (OpenJDK)
    reallocations                              ~30
    total slots copied                         ~2,000,000
    with new ArrayList<>(1_000_000)            0
20
  Rule of thumb
    Default to ArrayList. Need a queue or stack -> ArrayDeque.
    LinkedList only for Deque semantics plus iterator removal.
Use cases:PerformanceBig-OData Structures