Why this matters
- The textbook answer — "LinkedList for insertions, ArrayList for reads" — is misleading, and knowing why marks the difference between memorised and understood.
ArrayListgrowth is the mechanism behind a surprising amount of garbage in list-heavy code, and one constructor argument removes it.- These two are the most frequently compared classes in Java interviews.
How each one stores elements
get(i) is instant. Inserting in the middle shifts everything after it.
get(i) walks from an end. Insert is pointer surgery.
ArrayListwraps anObject[]. Element i sits at offset i, so indexed access is a single calculation. Inserting in the middle shifts everything after it.LinkedListis a doubly linked list of nodes. Each node holds the element plus a reference forward and backward. Reaching index i means walking i links.
Cost, honestly
| Aspect | Operation | ArrayList vs LinkedList |
|---|---|---|
| get(i) / set(i) | O(1) | O(n) — must walk to the position |
| add at end | Amortised O(1) | O(1) |
| add or remove at index 0 | O(n) — shifts everything | O(1) |
| add or remove in the middle | O(n) shift | O(n) to find, then O(1) to relink |
| contains / indexOf | O(n) | O(n) |
| Memory per element | One slot, plus spare capacity | A node object with two references |
| Cache behaviour | Excellent — contiguous | Poor — nodes scattered on the heap |
get(i) / set(i)
OperationO(1)ArrayList vs LinkedListO(n) — must walk to the positionadd at end
OperationAmortised O(1)ArrayList vs LinkedListO(1)add or remove at index 0
OperationO(n) — shifts everythingArrayList vs LinkedListO(1)add or remove in the middle
OperationO(n) shiftArrayList vs LinkedListO(n) to find, then O(1) to relinkcontains / indexOf
OperationO(n)ArrayList vs LinkedListO(n)Memory per element
OperationOne slot, plus spare capacityArrayList vs LinkedListA node object with two referencesCache behaviour
OperationExcellent — contiguousArrayList vs LinkedListPoor — nodes scattered on the heap
LinkedList's middle insertion is only O(1) once you are already there, which an index-based call never is.
How ArrayList grows
The internal array has a capacity that is usually larger than the size. When it fills, a new
larger array is allocated and the contents copied.
Growth is roughly 1.5× the current capacity. That makes the amortised cost of add constant, because
the occasional expensive copy is spread across many cheap appends. But each copy allocates a full array
and leaves the old one for the garbage collector.
Practical consequences
- Pre-size when you can.
new ArrayList<>(expected)eliminates every intermediate array. size()is not capacity. A list of 3 elements may hold an array of 10.removenever shrinks the array. CalltrimToSize()on the concreteArrayListif a large list has shrunk permanently.clear()nulls the slots but keeps the capacity, which is efficient for reuse.
The rest of this guide is part of Pro
Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.
Still to come · 5 sections
- Removing while iterating
- remove has two overloads
- CopyOnWriteArrayList
- Other list operations worth knowing
- Common misreadings
Test yourself
Answer these before moving on — recall is what makes it stick.