Performance Characteristics Summary: Big-O Complexities
What you'll learn: You'll get a quick-reference guide to the time complexity of common operations across the major collection types you've been learning.
Why Big-O Matters for Collections
Understanding Big-O notation helps you choose the right collection for your use case. A HashMap might feel "fast," but if you need sorted iteration, that TreeMap's O(log n) lookup becomes your friend. Let's see how the collections you've studied stack up.
Operation Complexity Chart
ArrayList
- add (at end): O(1) amortized
- remove (at end): O(1)
- contains: O(n) — must scan entire list
- get (by index): O(1) — direct array access
LinkedList
- add (at beginning/end): O(1)
- remove (at beginning/end): O(1)
- contains: O(n) — must traverse nodes
- get (by index): O(n) — must walk the chain
HashSet
- add: O(1) average case
- remove: O(1) average case
- contains: O(1) average case — hash lookup magic
TreeSet
- add: O(log n) — maintains sorted red-black tree
- remove: O(log n)
- contains: O(log n) — binary search structure
HashMap
- put: O(1) average case
- remove: O(1) average case
- get: O(1) average case
- containsKey: O(1) average case
TreeMap
- put: O(log n)
- remove: O(log n)
- get: O(log n)
- containsKey: O(log n)
The Pattern
Hash-based structures (HashSet, HashMap) trade memory and unordered storage for blazing O(1) speed. Tree-based structures (TreeSet, TreeMap) keep things sorted at the cost of O(log n) operations. Lists provide indexed access but suffer O(n) searches.
Key Takeaway: Choose ArrayList for indexed access, LinkedList for frequent head/tail operations, HashSet/HashMap for fastest lookups without ordering, and TreeSet/TreeMap when you need sorted iteration with acceptable O(log n) performance.