ArrayList wins at random access and tail-append; LinkedList only wins at head insert/remove. Despite textbook lore, even most "middle insertion" workloads favor ArrayList because the O(n) arraycopy is far faster than the O(n) pointer walk a LinkedList performs to locate the index.
The Numbers
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| get(i) / set(i) | O(1) | O(1) | O(1) | ArrayList — direct array indexing |
| get(i) / set(i) | O(1) | O(n) | O(n) | LinkedList — walks from nearer end (head or tail) |
| add(e) [tail] | O(1) | O(1) amortized | O(n) | ArrayList — worst when grow+copy is needed |
| add(e) [tail] | O(1) | O(1) | O(1) | LinkedList — append to tail pointer |
| add(0, e) [head] | O(n) | O(n) | O(n) | ArrayList — shifts all elements right |
| add(0, e) [head] | O(1) | O(1) | O(1) | LinkedList — head pointer rewrite |
| add(i, e) [middle] | O(1) | O(n) | O(n) | ArrayList — arraycopy of (size-i) elements |
| add(i, e) [middle] | O(1) | O(n) | O(n) | LinkedList — O(n) walk to locate, then O(1) link |
| remove(i) [middle] | O(1) | O(n) | O(n) | ArrayList — arraycopy shift |
| remove(i) [middle] | O(1) | O(n) | O(n) | LinkedList — O(n) walk dominates |
| remove(0) [head] | O(n) | O(n) | O(n) | ArrayList — shift everything left |
| remove(0) [head] | O(1) | O(1) | O(1) | LinkedList — unlink head |
| contains(o) | O(1) | O(n) | O(n) | Both — linear scan |
| iterator next() | O(1) | O(1) | O(1) | Both — but ArrayList has far better cache locality |
The Practical Catch
The table makes LinkedList look competitive for head/middle ops. In real CPUs, it isn't. ArrayList's System.arraycopy is a single intrinsic operating on packed memory — typically billions of elements per second. LinkedList chases pointers across heap-allocated nodes, missing the cache on every step.
// Benchmarks consistently show ArrayList faster for most middle inserts
// up to many thousands of elements, because:
// - arraycopy: 1 cache-friendly bulk move
// - LinkedList: i pointer dereferences + 4 pointer writesA Subtle Iterator Detail
If you're traversing-and-removing with an Iterator, LinkedList's remove is genuinely O(1) per call (it has the node in hand), while ArrayList is still O(n) per remove. But even here, the cache penalty of the walk often dominates.
// LinkedList iterator-based removal: O(n) total
var ll = new LinkedList<>(List.of(1,2,3,4,5));
var it = ll.iterator();
while (it.hasNext()) if (it.next() % 2 == 0) it.remove();
// ArrayList equivalent: O(n^2) but often still faster in practice
// — prefer removeIf which uses a single compaction pass: O(n)
arrayList.removeIf(x -> x % 2 == 0);