What's the difference between ArrayList and LinkedList?
Quick Answer
ArrayList is backed by a resizable array: O(1) random access by index, but O(n) insert/remove in the middle (elements must shift). LinkedList is a doubly-linked list: O(1) insert/remove at known positions (given a reference), but O(n) random access since it must traverse from an end. ArrayList is the default choice for most use cases due to better cache locality and lower per-element memory overhead.
Detailed Answer
Both implement List, but with very different internal structures and performance profiles:
ArrayList | LinkedList | |
|---|---|---|
| Backing structure | resizable array | doubly-linked list of nodes |
get(index) | O(1) | O(n) — must walk from the nearer end |
add/remove at end | amortized O(1) | O(1) |
add/remove in the middle | O(n) — shifts elements | O(1) once you have the node/iterator position, O(n) to find it |
| Memory overhead | compact (just the array + slack) | extra per-element node objects (prev/next pointers) |
| Cache locality | good (contiguous memory) | poor (nodes scattered on heap) |
In practice, ArrayList is almost always the better default: even "insert in the middle" workloads are often faster with ArrayList in real benchmarks because array shifting is a cheap, cache-friendly System.arraycopy, whereas LinkedList's node-chasing defeats CPU cache prefetching. LinkedList mainly earns its keep when you need a Deque (stack/queue operations at both ends) or frequent insert/remove via an existing ListIterator without index lookups.
LinkedList also implements Deque, so it's commonly used as a stack or queue, though ArrayDeque is now generally preferred for that purpose (lower overhead, no null elements allowed which avoids ambiguity).