How do get, add, and contains differ in cost across List, Set, and Map implementations?
ArrayList gives indexed get in O(1) and amortized O(1) append, but contains scans in O(n). LinkedList is O(1) only at the ends; indexed get and contains are O(n). HashMap and HashSet average O(1) for all three, degrading to O(log n) inside a treeified bucket and to O(n) with a degenerate hashCode. TreeMap and TreeSet are O(log n) for every operation, in exchange for sorted order.
- ✗Believing
LinkedListindexes inO(1)because it is a linked structure - ✗Quoting
HashMapasO(1)worst-case, ignoring collisions and a badhashCode - ✗Forgetting that
containson anyListis a linear scan, not a hashed lookup
- →Why is
ArrayListappend amortizedO(1)rather than plainO(1)? - →When does
LinkedListactually beatArrayListdespite worse cache locality?
Complexity table
| Operation | ArrayList | LinkedList | HashMap / HashSet | TreeMap / TreeSet |
|---|---|---|---|---|
get by key/index | O(1) | O(n) | O(1) average | O(log n) |
add | amortized O(1) (append) | O(1) at the ends | O(1) average | O(log n) |
contains | O(n) | O(n) | O(1) average | O(log n) |
| iteration order | insertion | insertion | not guaranteed | sorted |
Why ArrayList.add is amortized O(1). The array grows by doubling: one insertion occasionally costs O(n) to copy, but that cost is spread across all the cheap insertions before it.
Where hashing degrades. HashMap's average O(1) rests on a well-spread hashCode. If every key lands in one bucket, a lookup walks the chain — O(n). Since Java 8 an overlong chain in a large-enough table becomes a red-black tree, bounding the worst case at O(log n).
What ordering costs. TreeMap/TreeSet pay O(log n) on every operation because they keep keys sorted — which is what lets them answer range queries (headMap, subSet) that hashed structures cannot answer at all.
⚠️ The classic trap: LinkedList does not index quickly. get(i) walks the links from the nearer end — O(n). Its strength is insertion and removal at the ends or through an iterator you already hold.
