Collections Framework — Cheat Sheet
Java A–Z · 10 topics. Download the PDF or the Instagram carousel and share it.
Cheat Sheet · AiCanCode.org
Collections Framework
Java A–Z10 topicsQuick revision reference
1
Generics
- ✓Generics catch type errors at compile time — no ClassCastException, no manual casts
- ✓PECS: Producer Extends (read), Consumer Super (write) — guides wildcard choice
- ✓Type erasure: <T> becomes Object at runtime; List<String> and List<Integer> are the same class
- ✓Cannot do instanceof with parameterised types, or create generic arrays (new T[])
- ✓Bounded wildcard <? extends Number> allows reading; <? super Integer> allows writing
- ✓Static fields cannot use the class-level type parameter — they are shared across all instances
Pair.java / GenericsDemo.java
// Generic class — works for any type T
public class Pair<T, U> {
private final T first;
private final U second;
public Pair(T first, U second) {
this.first = first;
this.second = second;
}
public T getFirst() { return first; }
public U getSecond() { return second; }
@Override public String toString() {
return "(" + first + ", " + second + ")";
}
// Generic method — declares its own <V> independent of class T, U
public static <V> Pair<V, V> of(V value) {
return new Pair<>(value, value);
}
}
// Generic interface
interface Repository<T, ID> {
T findById(ID id);
void save(T entity);
}
public class GenericsDemo {
// Standalone generic method
static <T extends Comparable<T>> T max(T a, T b) {
return a.compareTo(b) >= 0 ? a : b;
}
public static void main(String[] args) {
Pair<String, Integer> person = new Pair<>("Alice", 30);
System.out.println(person); // (Alice, 30)
System.out.println(person.getFirst().toUpperCase()); // ALICE — no cast!
Pair<Double, Double> coords = Pair.of(3.14);
System.out.println(coords); // (3.14, 3.14)
System.out.println(max(10, 20)); // 20
System.out.println(max("apple", "banana")); // banana
}
}2
Collections Overview
- ✓Collection hierarchy: Iterable → Collection → List/Set/Queue; Map is separate
- ✓ArrayList is the best default List; ArrayDeque is the best Stack and Queue
- ✓HashSet/HashMap O(1) average; TreeSet/TreeMap O(log n) sorted; LinkedHashSet/LinkedHashMap insertion order
- ✓Map.Entry gives both key and value in entrySet() iteration
- ✓computeIfAbsent(), merge(), putIfAbsent() are essential modern Map patterns
- ✓List.of(), Set.of(), Map.of() (Java 9+) create compact, immutable collections
CollectionHierarchy.java
import java.util.*;
public class CollectionHierarchy {
public static void main(String[] args) {
// List — ordered, index-based
List<String> list = new ArrayList<>(List.of("banana", "apple", "cherry"));
list.add("date");
Collections.sort(list);
System.out.println(list); // [apple, banana, cherry, date]
// Set — no duplicates
Set<String> set = new HashSet<>(list);
set.add("apple"); // duplicate — silently ignored
System.out.println(set.size()); // 4
// Queue — FIFO
Queue<String> queue = new ArrayDeque<>(List.of("first", "second", "third"));
System.out.println(queue.poll()); // first
System.out.println(queue.peek()); // second (doesn't remove)
// All are Collections — polymorphic utility methods work on all
System.out.println(Collections.frequency(list, "apple")); // 1
Collections.shuffle(list);
// Iterable — enhanced for-each works on all
for (String s : set) System.out.print(s + " ");
System.out.println();
// Convert between collections
List<String> fromSet = new ArrayList<>(set);
Set<String> fromList = new LinkedHashSet<>(list); // preserves order, dedupes
}
}3
ArrayList
- ✓ArrayList is backed by Object[] — O(1) get/set, amortised O(1) add at end, O(n) insert/remove in middle
- ✓Default capacity is 10; growth factor is ~1.5× — use ensureCapacity() for large batch inserts
- ✓Never remove by index in a forward loop — use Iterator.remove() or removeIf() instead
- ✓subList() returns a view backed by the original — mutations to the view affect the original
- ✓ArrayList is fail-fast: structural modification during for-each throws ConcurrentModificationException
- ✓For thread safety use CopyOnWriteArrayList (read-heavy) or Collections.synchronizedList() (write-heavy)
ArrayListDemo.java
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Iterator;
public class ArrayListDemo {
public static void main(String[] args) {
// Constructors
List<String> list = new ArrayList<>(); // default capacity 10
List<String> sized = new ArrayList<>(100); // pre-sized
List<String> copy = new ArrayList<>(List.of("a", "b")); // copy constructor
// Adding
list.add("apple");
list.add("banana");
list.add("cherry");
list.add(1, "avocado"); // insert at index 1 — O(n)
System.out.println(list); // [apple, avocado, banana, cherry]
// Getting & setting — O(1)
System.out.println(list.get(2)); // banana
list.set(2, "blueberry");
System.out.println(list.get(2)); // blueberry
// Removing
list.remove(0); // by index — O(n)
list.remove("cherry"); // by value — O(n)
System.out.println(list); // [avocado, blueberry]
// Bulk operations
List<String> more = List.of("date", "elderberry");
list.addAll(more);
list.addAll(0, List.of("fig")); // insert all at index 0
System.out.println(list); // [fig, avocado, blueberry, date, elderberry]
// Searching
System.out.println(list.contains("date")); // true
System.out.println(list.indexOf("date")); // 3
System.out.println(list.size()); // 5
System.out.println(list.isEmpty()); // false
// Sub-list view (backed by original!)
List<String> sub = list.subList(1, 4);
System.out.println(sub); // [avocado, blueberry, date]
sub.clear(); // modifies the original list too
System.out.println(list); // [fig, elderberry]
}
}4
LinkedList
- ✓LinkedList implements both List and Deque — it is a doubly-linked list
- ✓O(1) addFirst/addLast/removeFirst/removeLast; O(n) get(index) — must traverse from nearest end
- ✓Higher memory overhead than ArrayList: ~40 bytes per node vs ~4 bytes per reference slot
- ✓Prefer ArrayDeque over LinkedList for stacks and queues — faster and more cache-friendly
- ✓ListIterator allows O(1) add/remove/set during traversal without ConcurrentModificationException
- ✓LinkedList is fail-fast just like ArrayList — do not structurally modify from outside while iterating
LinkedListDemo.java
import java.util.LinkedList;
import java.util.Deque;
import java.util.Queue;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
// ── As a List ─────────────────────────────────────────────────
list.add("banana"); // O(1) — adds at tail
list.add("cherry");
list.add(0, "apple"); // O(n) — must traverse to index 0
System.out.println(list); // [apple, banana, cherry]
System.out.println(list.get(1)); // banana — O(n) traversal
System.out.println(list.size()); // 3
// ── As a Deque (double-ended queue) ──────────────────────────
LinkedList<Integer> deque = new LinkedList<>();
deque.addFirst(2); // [2]
deque.addFirst(1); // [1, 2]
deque.addLast(3); // [1, 2, 3]
deque.addLast(4); // [1, 2, 3, 4]
System.out.println(deque.peekFirst()); // 1 — does not remove
System.out.println(deque.peekLast()); // 4 — does not remove
System.out.println(deque.removeFirst()); // 1
System.out.println(deque.removeLast()); // 4
System.out.println(deque); // [2, 3]
// ── As a Queue (FIFO) ─────────────────────────────────────────
Queue<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
queue.offer("third");
System.out.println(queue.poll()); // first (removes head)
System.out.println(queue.peek()); // second (views head, no remove)
// ── As a Stack (LIFO) ─────────────────────────────────────────
Deque<String> stack = new LinkedList<>();
stack.push("a"); stack.push("b"); stack.push("c");
System.out.println(stack.pop()); // c (LIFO)
}
}5
HashMap
- ✓HashMap uses hash table with chaining; Java 8+ treeifies buckets with ≥8 entries to O(log n)
- ✓Default capacity 16, load factor 0.75 — rehash doubles the table; pre-size for large maps
- ✓Keys must correctly implement hashCode() + equals() — bad hashing degrades all ops to O(n)
- ✓merge() is the cleanest way to count/aggregate; computeIfAbsent() is best for group-by maps
- ✓Null allowed: one null key, any number of null values — ConcurrentHashMap forbids both
- ✓For thread safety: ConcurrentHashMap (concurrent reads/writes), not the legacy Hashtable
HashMapInternals.java
import java.util.HashMap;
import java.util.Map;
public class HashMapInternals {
// Bad hashCode — all keys land in bucket 0 → O(n) performance
static class BadKey {
int value;
BadKey(int v) { value = v; }
@Override public int hashCode() { return 0; } // always 0!
@Override public boolean equals(Object o) {
return o instanceof BadKey bk && bk.value == value;
}
}
// Good hashCode — spreads keys across buckets
static class GoodKey {
int value;
GoodKey(int v) { value = v; }
@Override public int hashCode() { return Integer.hashCode(value); }
@Override public boolean equals(Object o) {
return o instanceof GoodKey gk && gk.value == value;
}
}
public static void main(String[] args) {
// Basic operations
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 90);
map.put("Bob", 85);
map.put("Carol", 92);
map.put("Alice", 95); // update existing key
System.out.println(map.get("Alice")); // 95
System.out.println(map.containsKey("Dave")); // false
System.out.println(map.containsValue(85)); // true
System.out.println(map.size()); // 3
// null key and null value are allowed (one null key)
map.put(null, 0);
System.out.println(map.get(null)); // 0
// Pre-size to avoid rehash — new HashMap<>(expectedSize / 0.75 + 1)
Map<String, String> presized = new HashMap<>(100); // for ~75 entries
// Internal bucket count is always power of 2
// HashMap capacity 16 → threshold 12 → at 13 entries, doubles to 32
}
}6
TreeMap
- ✓TreeMap is backed by a Red-Black tree — all ops are O(log n); HashMap is O(1) average
- ✓Keys must implement Comparable or a Comparator must be provided at construction
- ✓Iteration always returns keys in sorted ascending order
- ✓floorKey/ceilingKey/lowerKey/higherKey enable O(log n) nearest-key lookups
- ✓subMap/headMap/tailMap return live views — changes to the view affect the original
- ✓Ideal for: sorted key iteration, range scans, event schedulers, price-tier lookups
TreeMapBasics.java
import java.util.*;
public class TreeMapBasics {
public static void main(String[] args) {
// Natural ordering (String Comparable — alphabetical)
TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 88);
scores.put("Alice", 95);
scores.put("Bob", 82);
scores.put("Diana", 91);
// Always iterates in sorted key order
scores.forEach((k, v) -> System.out.println(k + " → " + v));
// Alice → 95 | Bob → 82 | Charlie → 88 | Diana → 91
System.out.println(scores.firstKey()); // Alice
System.out.println(scores.lastKey()); // Diana
// SortedMap views (still backed by original)
SortedMap<String, Integer> bToD = scores.subMap("Bob", "Diana");
System.out.println(bToD); // {Bob=82, Charlie=88} — "Diana" exclusive
SortedMap<String, Integer> upToC = scores.headMap("Charlie");
System.out.println(upToC); // {Alice=95, Bob=82} — "Charlie" exclusive
SortedMap<String, Integer> fromC = scores.tailMap("Charlie");
System.out.println(fromC); // {Charlie=88, Diana=91}
// Custom Comparator — reverse order
TreeMap<String, Integer> reversed = new TreeMap<>(Comparator.reverseOrder());
reversed.putAll(scores);
System.out.println(reversed.firstKey()); // Diana
}
}7
HashSet & LinkedHashSet
- ✓HashSet is backed by HashMap — O(1) add/remove/contains; no guaranteed order
- ✓LinkedHashSet is backed by LinkedHashMap — same O(1) performance, insertion order preserved
- ✓add() returns false (not an exception) when a duplicate is detected
- ✓Set operations: addAll (union), retainAll (intersection), removeAll (difference)
- ✓Never mutate fields used in hashCode() while an object is stored in a Set or as a Map key
- ✓Use LinkedHashSet to de-duplicate a list while preserving the order of first appearances
HashSetDemo.java
import java.util.*;
public class HashSetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
// add() returns true on new element, false on duplicate
System.out.println(set.add("apple")); // true
System.out.println(set.add("banana")); // true
System.out.println(set.add("apple")); // false — already present
System.out.println(set.size()); // 2
// contains — O(1) average (vs ArrayList O(n))
System.out.println(set.contains("banana")); // true
System.out.println(set.contains("cherry")); // false
// Remove
set.remove("banana");
System.out.println(set); // [apple] — order not guaranteed
// Bulk operations
Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4, 5));
Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6, 7));
// Union
Set<Integer> union = new HashSet<>(a);
union.addAll(b);
System.out.println(union); // [1, 2, 3, 4, 5, 6, 7]
// Intersection
Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);
System.out.println(intersection); // [3, 4, 5]
// Difference (a - b)
Set<Integer> diff = new HashSet<>(a);
diff.removeAll(b);
System.out.println(diff); // [1, 2]
// Subset check
System.out.println(b.containsAll(Set.of(3, 4))); // true
}
}8
TreeSet
- ✓TreeSet is backed by a TreeMap — O(log n) all ops; elements always in sorted order
- ✓Equality in TreeSet is determined by compareTo (not equals) — compareTo==0 means duplicate
- ✓floor/ceiling/lower/higher give O(log n) nearest-element lookups
- ✓subSet/headSet/tailSet return live views — mutations propagate to the original
- ✓pollFirst/pollLast remove and return boundary elements in O(log n)
- ✓Use TreeSet over HashSet when sorted iteration or range queries are required
TreeSetBasics.java
import java.util.*;
public class TreeSetBasics {
public static void main(String[] args) {
// Natural order (Integer Comparable)
TreeSet<Integer> numbers = new TreeSet<>(Set.of(5, 2, 8, 1, 9, 3, 5));
System.out.println(numbers); // [1, 2, 3, 5, 8, 9] — sorted, no duplicate 5
System.out.println(numbers.first()); // 1
System.out.println(numbers.last()); // 9
System.out.println(numbers.size()); // 6
// Sorted String set
TreeSet<String> words = new TreeSet<>(
List.of("banana", "apple", "cherry", "avocado"));
System.out.println(words); // [apple, avocado, banana, cherry]
// Custom Comparator — sort by string length, then alphabetically
TreeSet<String> byLength = new TreeSet<>(
Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
byLength.addAll(words);
System.out.println(byLength); // [apple, banana, avocado, cherry]
// PITFALL: compareTo == 0 means duplicate, even if equals() differs
TreeSet<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Apple");
caseInsensitive.add("apple"); // treated as duplicate — compareTo returns 0
System.out.println(caseInsensitive.size()); // 1, not 2!
}
}9
Stack & Deque
- ✓Always use ArrayDeque instead of the legacy Stack class — faster, not synchronized
- ✓ArrayDeque is a circular resizable array — O(1) amortised at both ends, better cache locality than LinkedList
- ✓ArrayDeque does not permit null elements; LinkedList does
- ✓Stack API: push/pop/peek (head); Queue API: offer/poll/peek (tail in, head out)
- ✓offerXxx/pollXxx/peekXxx return null on empty; addXxx/removeXxx/getXxx throw NoSuchElementException
- ✓Monotonic stack (ArrayDeque) solves Next Greater Element, Largest Rectangle, and similar in O(n)
ArrayDequeDemo.java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
public class ArrayDequeDemo {
public static void main(String[] args) {
// ── As a STACK (LIFO) ─────────────────────────────────────────
Deque<String> stack = new ArrayDeque<>();
stack.push("first"); // addFirst()
stack.push("second");
stack.push("third");
System.out.println(stack.peek()); // third — view top, no remove
System.out.println(stack.pop()); // third — remove top
System.out.println(stack.pop()); // second
System.out.println(stack); // [first]
// ── As a QUEUE (FIFO) ─────────────────────────────────────────
Queue<String> queue = new ArrayDeque<>();
queue.offer("first"); // addLast()
queue.offer("second");
queue.offer("third");
System.out.println(queue.peek()); // first — view head, no remove
System.out.println(queue.poll()); // first — remove head
System.out.println(queue.poll()); // second
System.out.println(queue); // [third]
// ── As a DEQUE (both ends) ────────────────────────────────────
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(2); // [2]
deque.offerFirst(1); // [1, 2]
deque.offerLast(3); // [1, 2, 3]
deque.offerLast(4); // [1, 2, 3, 4]
System.out.println(deque.peekFirst()); // 1
System.out.println(deque.peekLast()); // 4
System.out.println(deque.pollFirst()); // 1
System.out.println(deque.pollLast()); // 4
System.out.println(deque); // [2, 3]
// Null not allowed in ArrayDeque
try {
deque.offer(null); // throws NullPointerException
} catch (NullPointerException e) {
System.out.println("No nulls in ArrayDeque");
}
}
}10
PriorityQueue
- ✓PriorityQueue is a min-heap by default — poll() always returns the smallest element
- ✓For max-heap: new PriorityQueue<>(Comparator.reverseOrder())
- ✓offer/add: O(log n); poll/remove head: O(log n); peek: O(1); contains/remove(obj): O(n)
- ✓Iterating a PriorityQueue does NOT yield elements in sorted order — only sequential poll() does
- ✓Kth largest: maintain a min-heap of size K — peek() is always the Kth largest
- ✓PriorityQueue is not thread-safe — use PriorityBlockingQueue for concurrent use
PriorityQueueDemo.java
import java.util.PriorityQueue;
import java.util.Comparator;
public class PriorityQueueDemo {
public static void main(String[] args) {
// Min-heap (default) — smallest element polled first
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.offer(2);
minHeap.offer(4);
System.out.print("Min-heap poll order: ");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " "); // 1 2 3 4 5
}
System.out.println();
// Max-heap — largest element polled first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3);
maxHeap.offer(2); maxHeap.offer(4);
System.out.print("Max-heap poll order: ");
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " "); // 5 4 3 2 1
}
System.out.println();
// Custom object heap — sorted by priority field
record Task(String name, int priority) {}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::priority));
taskQueue.offer(new Task("Low", 3));
taskQueue.offer(new Task("High", 1));
taskQueue.offer(new Task("Medium", 2));
while (!taskQueue.isEmpty()) {
Task t = taskQueue.poll();
System.out.println("Processing: " + t.name()); // High, Medium, Low
}
}
}Learn this free with Aria, your AI tutor → AiCanCode.org/learn/java