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.
List: 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 |
The honest answer is almost always ArrayList
LinkedList wins on paper for front insertion, and loses in practice almost everywhere else: contiguous memory means an ArrayList scan is far friendlier to the CPU cache, and shifting elements is a single fast block move. Use ArrayDeque, not LinkedList, when you genuinely need cheap operations at both ends.
Map: 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.
Reaching for Hashtable or Collections.synchronizedMap
Both lock the entire map for every operation, so threads queue behind each other. ConcurrentHashMap locks per bucket and scales far better — it is the correct answer for a shared mutable map.
Sets 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.
Stack and Vector are legacy
Both synchronise every method for a threading model Java left behind, and Stack even iterates bottom-up, which surprises everyone. Use ArrayDeque for a stack and ArrayList for a list.
The gotchas interviewers ask about
ConcurrentModificationException
Removing from a collection while iterating it with a for-each loop throws at the next step. Use Iterator.remove(), or removeIf(), or iterate over a copy.
// Throws ConcurrentModificationException
for (String s : list) {
if (s.isEmpty()) list.remove(s);
}
// Correct, and clearer
list.removeIf(String::isEmpty);Arrays.asList() is fixed size
It returns a view backed by the array, so add() and remove() throw UnsupportedOperationException. Wrap it — new ArrayList<>(Arrays.asList(...)) — when you need a mutable list.
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
| Problem | Pattern | Level |
|---|---|---|
| Build an LRU cache with LinkedHashMap | Access-order map | Medium |
| Find the top k frequent elements | HashMap + PriorityQueue | Medium |
| Deduplicate a list while preserving order | LinkedHashSet | Easy |
| Implement a stack using ArrayDeque | Deque as stack | Easy |
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 this topic solo, or share a room code and battle friends on it.
⚡ Start the Java quiz