Topic 10 of 30 · Intermediate
Collections Framework
List, Set, Map, Queue and choosing the right one.
Concept
The Collections Framework provides ready-made data structures. List keeps order and duplicates; Set rejects duplicates; Map stores key → value; Queue/Deque supports FIFO/LIFO.
ArrayList gives O(1) index access; LinkedList is rarely better. HashMap/HashSet give average O(1) lookup; TreeMap/TreeSet keep keys sorted in O(log n).
Objects used as HashMap keys must correctly override equals() and hashCode().
Cheat sheet
| Need | Use | Lookup |
|---|---|---|
| Ordered, index access | ArrayList | O(1) get |
| Unique items | HashSet | O(1) avg |
| Sorted unique | TreeSet | O(log n) |
| Key → value | HashMap | O(1) avg |
| Insertion-ordered map | LinkedHashMap | O(1) avg |
| Priority | PriorityQueue | O(log n) offer/poll |
Code (Java 21)
import java.util.*;
List<String> names = new ArrayList<>(List.of("Ravi", "Asha", "Ravi"));
Set<String> unique = new HashSet<>(names); // [Ravi, Asha]
Map<String, Integer> freq = new HashMap<>();
for (String n : names) freq.merge(n, 1, Integer::sum);
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2); stack.pop();
PriorityQueue<Integer> minHeap = new PriorityQueue<>(List.of(5, 1, 3));
System.out.println(minHeap.poll()); // 1Remember
- Use ArrayDeque instead of Stack.
- HashMap allows one null key; Hashtable allows none.
- Modifying while iterating → ConcurrentModificationException.
Interview questions
How does HashMap work internally?
It hashes the key to a bucket index in an array. Collisions are stored in a linked list that becomes a red-black tree after 8 entries. It resizes when size exceeds capacity × 0.75.
ArrayList vs LinkedList?
ArrayList: fast random access, amortised O(1) append. LinkedList: O(1) insert/remove at known nodes but O(n) access and poor cache use.
Lesson test
Take an 8-question test on “Collections Framework” — concepts, output prediction, bug spotting and interview questions.