Notes › Java
Java Collections Framework
The Collections Framework (java.util) gives ready-made data structures. Interfaces describe what a structure does; classes implement how.
Iterable
└ Collection
├ List → ArrayList, LinkedList, Vector
├ Set → HashSet, LinkedHashSet, TreeSet
└ Queue → PriorityQueue, ArrayDeque (Deque)
Map (separate) → HashMap, LinkedHashMap, TreeMap, Hashtable
Always declare with the interface: List<String> names = new ArrayList<>(); — easy to switch implementations later.
List — ordered, allows duplicates, index access
| ArrayList | LinkedList | |
|---|---|---|
| Inside | dynamic array | doubly linked list |
get(i) |
O(1) | O(n) |
add at end |
O(1) amortised | O(1) |
| add/remove in the middle | O(n) (shifting) | O(1) once you're there, but finding the spot is O(n) |
| Memory | compact | extra pointers per node |
Use ArrayList almost always.
List<Integer> a = new ArrayList<>(List.of(5, 3, 8));
a.add(1); a.get(0); a.set(0, 9); a.remove(Integer.valueOf(3)); // remove by value, not index!
Collections.sort(a); a.contains(8); a.size();
Set — no duplicates
| HashSet | LinkedHashSet | TreeSet | |
|---|---|---|---|
| Order | none | insertion order | sorted |
| add/contains/remove | O(1) avg | O(1) avg | O(log n) |
| Inside | HashMap | HashMap + linked list | red-black tree |
TreeSet extras: first(), last(), floor(x), ceiling(x), headSet, tailSet.
Map — key → value
| HashMap | LinkedHashMap | TreeMap | |
|---|---|---|---|
| Order | none | insertion (or access → LRU cache) | sorted by key |
| get/put | O(1) avg | O(1) avg | O(log n) |
| null key | one allowed | one allowed | not allowed |
Map<String, Integer> freq = new HashMap<>();
for (String w : words) freq.merge(w, 1, Integer::sum); // count words
freq.getOrDefault("java", 0);
freq.putIfAbsent("go", 0);
freq.computeIfAbsent("x", k -> new ArrayList<>()); // map of lists pattern
for (Map.Entry<String, Integer> e : freq.entrySet()) System.out.println(e.getKey() + "=" + e.getValue());
How HashMap works (asked in almost every Java interview)
hashCode()of the key → spread → index =hash & (capacity − 1)into an array of buckets.- Collisions are stored in the same bucket as a linked list; since Java 8, a bucket with more than 8 entries (and capacity ≥ 64) becomes a red-black tree → worst case O(log n) instead of O(n).
- Default capacity 16, load factor 0.75: when size > 12 it resizes to double and rehashes.
getfinds the bucket, then compares keys withequals.
That's why keys must override both equals and hashCode consistently, and why mutable keys are dangerous (change a field → the key is in the "wrong" bucket).
HashMap vs Hashtable vs ConcurrentHashMap: Hashtable is old and fully synchronized (slow); HashMap isn't thread-safe; ConcurrentHashMap is thread-safe with fine-grained locking — use it for shared maps.
Queue, Deque and PriorityQueue
Deque<Integer> stack = new ArrayDeque<>(); // use instead of Stack
stack.push(1); stack.pop(); stack.peek();
Queue<Integer> q = new ArrayDeque<>(); // FIFO
q.offer(1); q.poll(); q.peek();
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue: offer/poll O(log n), peek O(1). Iterating it does not give sorted order.
Comparable vs Comparator
| Comparable | Comparator | |
|---|---|---|
| Method | compareTo(T o) inside the class |
compare(a, b) outside |
| Orders | one natural order | as many as you like |
record Student(String name, int marks) {}
students.sort(Comparator.comparingInt(Student::marks).reversed().thenComparing(Student::name));
Avoid a - b in comparators — it can overflow; use Integer.compare(a, b).
Iterating and removing safely
Removing inside a for-each loop throws ConcurrentModificationException (fail-fast iterators). Use:
list.removeIf(x -> x % 2 == 0);
// or an explicit Iterator: it.next(); it.remove();
Useful utilities
Collections.sort / reverse / shuffle / max / min / frequency / unmodifiableList, Arrays.asList (fixed size!), List.of (immutable), Arrays.sort (dual-pivot quicksort for primitives, TimSort for objects).
What to use when
| Need | Use |
|---|---|
| list with fast index access | ArrayList |
| unique items, fast lookup | HashSet |
| keep insertion order | LinkedHashSet / LinkedHashMap |
| sorted keys, floor/ceiling | TreeSet / TreeMap |
| counting / grouping | HashMap |
| stack or queue | ArrayDeque |
| always get min or max | PriorityQueue |
| shared between threads | ConcurrentHashMap, CopyOnWriteArrayList |
Interview one-liners
- ArrayList is backed by an array (O(1) get); LinkedList by nodes (O(n) get).
- HashMap: array of buckets, linked list → red-black tree after 8 collisions, resize at 0.75 load.
- HashSet is a HashMap with dummy values.
- Fail-fast iterators throw ConcurrentModificationException.
- Related: Java OOP Concepts, Hashing, Java docs.