Course contents
Java Collections Framework: Choosing the Right Structure
"Which collection would you use?" is a design question wearing a syntax costume. The interviewer wants to hear the access pattern drive the choice — and to hear you name the cost you are accepting in exchange.
01List: ArrayList or LinkedList
| Operation | ArrayList | LinkedList |
|---|---|---|
get(i) | O(1) | O(n) |
add() at the end | O(1) amortised | O(1) |
add(0, x) | O(n) | O(1) |
remove(i) | O(n) | O(n) to find, O(1) to unlink |
| Memory per element | One slot | Slot plus two pointers plus node header |
02Map: Hash, Linked or Tree
| Implementation | Order | Get / put | Use when |
|---|---|---|---|
HashMap | None | O(1) average | The default — you only need lookup |
LinkedHashMap | Insertion order | O(1) average | Order must be stable, or building an LRU cache |
TreeMap | Sorted by key | O(log n) | You need sorted iteration or range queries |
ConcurrentHashMap | None | O(1) average | Multiple threads write to it |
TreeMap earns its extra log factor with methods a hash map cannot offer: firstKey(), floorKey(), headMap(), subMap(). If a problem asks for "the largest key not exceeding x", that is a TreeMap signal.
03Sets and queues
HashSet— O(1) membership, no order. The default set.LinkedHashSet— O(1) membership, insertion order preserved. Useful for deduplicating while keeping order.TreeSet— O(log n), sorted, withfirst(),ceiling()and range views.ArrayDeque— O(1) at both ends; the right choice for a stack or a queue.PriorityQueue— a binary heap; O(log n) insert and remove, O(1) peek at the smallest. The top-k workhorse.
04The gotchas interviewers ask about
// Throws ConcurrentModificationException
for (String s : list) {
if (s.isEmpty()) list.remove(s);
}
// Correct, and clearer
list.removeIf(String::isEmpty);One more, worth saying before you are asked: any object used as a HashMap key or in a HashSet must implement equals() and hashCode() consistently, and must not be mutated afterwards.
Key takeaways
- ArrayList is the default List; LinkedList rarely wins outside a whiteboard.
- HashMap by default, LinkedHashMap for order, TreeMap for sorted and range queries.
- ConcurrentHashMap for shared mutable maps; Hashtable and synchronizedMap lock everything.
- Use removeIf or Iterator.remove — never remove inside a for-each loop.
Practice problems
Tagged by pattern, so you can tell whether you learned the idea or just the example.
- Build an LRU cache with LinkedHashMapAccess-order mapMedium
- Find the top k frequent elementsHashMap + PriorityQueueMedium
- Deduplicate a list while preserving orderLinkedHashSetEasy
- Implement a stack using ArrayDequeDeque as stackEasy
Frequently asked questions
What is the difference between ArrayList and LinkedList?
ArrayList is backed by a resizable array: O(1) indexed access, O(n) insertion at the front, and excellent cache behaviour. LinkedList is a doubly linked list: O(1) insertion at the ends, O(n) access by index, and more memory per element.
When should I use a TreeMap instead of a HashMap?
When you need keys in sorted order, or range operations such as floorKey, headMap and subMap. You pay O(log n) per operation instead of O(1) average for that capability.
What causes a ConcurrentModificationException?
Structurally modifying a collection while iterating it with a for-each loop. The iterator detects the modification count changed and fails fast. Use Iterator.remove() or removeIf() instead.
Test yourself on Java
Reading is not recall. Take a timed quiz on Java solo, or share a room code and battle friends on it.