📚 Java Collections Framework — List, Set, Map, Queue
Master the Java Collections Framework — ArrayList vs LinkedList, HashSet vs TreeSet, HashMap vs TreeMap, Queue/Deque, when to use each, and Big-O performance. With examples.
The Collections Framework is Java's library of data structures. Knowing which to pick is half of practical Java.
📋 List — ordered, indexed, allows duplicates
- ArrayList — backed by an array. O(1) random access, O(1) amortized append, O(n) middle insert. Default choice.
- LinkedList — doubly linked. O(1) insert/remove at ends, O(n) random access. Rarely better than ArrayList.
🔢 Set — no duplicates
- HashSet — O(1) add/contains, no order.
- LinkedHashSet — insertion order preserved.
- TreeSet — sorted, O(log n), backed by a red-black tree.
🗺️ Map — key → value
- HashMap — O(1) average get/put, no order. The workhorse.
- LinkedHashMap — insertion (or access) order.
- TreeMap — sorted by key, O(log n).
📥 Queue / Deque
- ArrayDeque — fast stack and queue.
- PriorityQueue — heap-ordered, O(log n) for min/max.
⚙️ How HashMap works (the #1 interview question)
Keys are hashed to buckets. Good hashCode() spreads keys; equals() resolves collisions. Since Java 8, a bucket with many collisions converts from a linked list to a balanced tree (O(log n) worst case). Always override hashCode() and equals() together for custom keys.
💻 Code Examples
HashMap word count
Map<String,Integer> count = new HashMap<>();
for (String w : List.of("a","b","a")) {
count.merge(w, 1, Integer::sum);
}
System.out.println(count);Output:
{a=2, b=1}TreeSet keeps sorted, unique
Set<Integer> s = new TreeSet<>(List.of(5, 1, 3, 1, 5));
System.out.println(s);Output:
[1, 3, 5]
ArrayDeque as a stack
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
System.out.println(stack.pop());Output:
2
⚠️ Common Mistakes
- Using LinkedList by default — ArrayList is faster for almost all real workloads (cache locality).
- Forgetting to override hashCode() with equals() for custom map/set keys — lookups silently fail.
- Modifying a collection while iterating with for-each — ConcurrentModificationException; use Iterator.remove or removeIf.
- Using a HashMap when you need ordering — choose LinkedHashMap (insertion) or TreeMap (sorted).
🎯 Interview Questions
Real questions asked at top product and service-based companies.
Q1.What's the difference between ArrayList and LinkedList?Beginner
ArrayList is array-backed: O(1) random access, O(1) amortized append, O(n) middle insert/remove. LinkedList is node-based: O(1) insert/remove at ends but O(n) random access. ArrayList wins in practice due to cache locality.
Q2.How does HashMap work internally?Intermediate
It stores entries in buckets indexed by key.hashCode(). Collisions in a bucket form a linked list, which Java 8+ converts to a balanced tree when it grows large (treeify). get/put are O(1) average, O(log n) worst case. Requires consistent hashCode()/equals().
Q3.What's the difference between HashSet, LinkedHashSet and TreeSet?Intermediate
HashSet: O(1), unordered. LinkedHashSet: O(1), preserves insertion order. TreeSet: O(log n), sorted (natural or by Comparator).
Q4.When would you use a Map vs a List?Beginner
Use a List for an ordered sequence accessed by index or iterated. Use a Map for key→value lookups where you retrieve values by a unique key in O(1) (HashMap).
Q5.Why must you override hashCode() whenever you override equals()?Advanced
Hash-based collections (HashMap, HashSet) locate objects by hashCode first, then confirm with equals. If equals says two objects are equal but their hashCodes differ, they land in different buckets and the collection breaks (duplicates, failed lookups).
🧠 Quick Summary
- List (ordered, duplicates): ArrayList default, LinkedList rarely.
- Set (unique): HashSet, LinkedHashSet (order), TreeSet (sorted).
- Map (key→value): HashMap default, LinkedHashMap, TreeMap (sorted).
- Queue/Deque: ArrayDeque (stack/queue), PriorityQueue (heap).
- Override hashCode() + equals() together for custom keys.