Why this matters
- The framework has dozens of classes, and picking by habit rather than by shape is how an application ends up doing linear scans where a hash lookup would do.
- Interviews reliably ask you to justify a choice, and "I always use ArrayList" is not a justification.
- Knowing the interface you should declare — as opposed to the class you instantiate — is what keeps code swappable.
The shape of the framework
Two roots, not one. Collection covers things holding single elements; Map holds pairs and is
deliberately separate because its operations have a different shape.
The four interfaces that matter
List— ordered by position, duplicates allowed, indexed access. Use when sequence matters.Set— no duplicates, usually no positional access. Use when membership is the question.Queue/Deque— ordered for processing, with access at the ends. Use for pipelines, buffers and stacks.Map— unique keys mapped to values. Use when you look things up by something other than position.
Choosing, in four questions
| Aspect | What you need | Reach for |
|---|---|---|
| An ordered list, mostly read by index | ArrayList | O(1) indexed access, cache-friendly |
| Heavy insertion and removal at the ends | ArrayDeque | Faster than LinkedList in practice |
| Uniqueness, order irrelevant | HashSet | O(1) membership test |
| Uniqueness, insertion order kept | LinkedHashSet | Predictable iteration |
| Uniqueness, sorted | TreeSet | O(log n), plus range queries |
| Key-value lookup | HashMap | O(1) average get and put |
| Key-value, sorted keys | TreeMap | O(log n), navigable |
| Key-value across threads | ConcurrentHashMap | Concurrent reads, segmented writes |
| Highest-priority item first | PriorityQueue | A binary heap, O(log n) insert |
An ordered list, mostly read by index
What you needArrayListReach forO(1) indexed access, cache-friendlyHeavy insertion and removal at the ends
What you needArrayDequeReach forFaster than LinkedList in practiceUniqueness, order irrelevant
What you needHashSetReach forO(1) membership testUniqueness, insertion order kept
What you needLinkedHashSetReach forPredictable iterationUniqueness, sorted
What you needTreeSetReach forO(log n), plus range queriesKey-value lookup
What you needHashMapReach forO(1) average get and putKey-value, sorted keys
What you needTreeMapReach forO(log n), navigableKey-value across threads
What you needConcurrentHashMapReach forConcurrent reads, segmented writesHighest-priority item first
What you needPriorityQueueReach forA binary heap, O(log n) insert
These nine cover the overwhelming majority of real code.
Cost at a glance
The operation that dominates your code is the one to optimise for.
| Aspect | Operation | Cost by implementation |
|---|---|---|
| get by index | ArrayList O(1) | LinkedList O(n) |
| add at end | ArrayList amortised O(1) | LinkedList O(1) |
| add or remove at front | ArrayList O(n) | ArrayDeque O(1) |
| contains | ArrayList O(n) | HashSet O(1), TreeSet O(log n) |
| get by key | HashMap O(1) average | TreeMap O(log n) |
| iterate in sorted order | TreeMap O(n), free | HashMap requires sorting first |
get by index
OperationArrayList O(1)Cost by implementationLinkedList O(n)add at end
OperationArrayList amortised O(1)Cost by implementationLinkedList O(1)add or remove at front
OperationArrayList O(n)Cost by implementationArrayDeque O(1)contains
OperationArrayList O(n)Cost by implementationHashSet O(1), TreeSet O(log n)get by key
OperationHashMap O(1) averageCost by implementationTreeMap O(log n)iterate in sorted order
OperationTreeMap O(n), freeCost by implementationHashMap requires sorting first
ArrayList's amortised O(1) append hides an occasional O(n) array copy when it grows.
The rest of this guide is part of Pro
Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.
Still to come · 6 sections
- Declare the interface, instantiate the class
- Immutable and unmodifiable collections
- Null tolerance differs
- Methods on the interfaces themselves
- Legacy classes to avoid
- Common misreadings
Test yourself
Answer these before moving on — recall is what makes it stick.
- What are collection factory methods (List.of, Set.of, Map.of) introduced in Java 9? How do they differ from Arrays.asList?
- Explain the Iterator pattern. How is it implemented in the Java Collections Framework?
- Differentiate between Collections.unmodifiableList(), List.of(), and Collections.singletonList().