How fast are common Java data structures (10M operations)?

HashMap vs TreeMap vs ArrayList vs LinkedList

HashMap.get() → ~140 ms

TreeMap.get() → ~420 ms

ArrayList.get(i) → ~40 ms

LinkedList.get(i) → ~2.5 s

Insertion (10M elements):

ArrayList.add() → ~180 ms

HashMap.put() → ~300 ms

LinkedList.add() → ~900 ms

Why:

ArrayList = contiguous memory, cache-friendly

HashMap = hashing + pointer chasing

TreeMap = O(log n) + rebalancing

LinkedList = worst cache locality + pointer traversal

PS: These are baseline costs. Once you know this, you stop misusing LinkedList forever.