Collections Framework Refresher¶

Eighty percent of the Java code you write in studies and in production is manipulating collections. The framework is small, mostly stable since Java 8, with a few Java 21 additions (sequenced collections). This file re-anchors the hierarchy, the performance characteristics, and the choices that separate someone who “knows Java” from someone who is fluent.

Every time you reach for a collection, ask three questions: ordered or not? unique or not? indexed or keyed? The answers pick the interface. Then pick the implementation by asking: random-access reads, insert-at-end, insert-in-middle, or key lookups?

The hierarchy (mental model)¶

Iterable
 └── Collection
      ├── List           (ordered, index-addressed, duplicates OK)
      │     ├── ArrayList
      │     ├── LinkedList        (also implements Deque)
      │     └── CopyOnWriteArrayList
      ├── Set            (no duplicates)
      │     ├── HashSet
      │     ├── LinkedHashSet     (insertion order)
      │     └── TreeSet           (sorted, NavigableSet)
      └── Queue / Deque
            ├── ArrayDeque
            ├── PriorityQueue
            └── LinkedList (again)

Map                       (key → value, NOT a Collection)
 ├── HashMap
 ├── LinkedHashMap        (insertion or access order)
 ├── TreeMap              (sorted, NavigableMap)
 ├── ConcurrentHashMap    (thread-safe, lock-striping)
 └── EnumMap              (keys are enum constants; array-backed, blazing fast)

Map is deliberately not a Collection — it has entries, not elements. Its values() and entrySet() return collections that view into the map.

1. `List` — `ArrayList` is the default¶

Op	ArrayList	LinkedList
`get(i)`	O(1)	O(n)
`add(e)` (end)	Amortized O(1)	O(1)
`add(0, e)` (head)	O(n)	O(1)
`remove(i)`	O(n)	O(n) traversal + O(1) unlink
`contains(e)`	O(n)	O(n)
Memory per element	1 slot (bare)	3 refs (node + prev + next)

LinkedList is almost always the wrong choice. Even inserting at the head, an ArrayDeque beats it. The only time LinkedList wins is when you have a live ListIterator at the insertion point — rare. Cache locality (contiguous array vs pointer-chase) usually dominates the theoretical big-O.

When you actually want LinkedList: almost never. Ignore it in modern code.

`ArrayList` growth¶

Initial capacity 10. On overflow, capacity grows to oldCap + oldCap >> 1 = 1.5×. If you know the final size, pre-size it: new ArrayList<>(expectedSize). This avoids intermediate copies and is a free performance win in hot code.

`List.of(...)` — immutable¶

List<Integer> xs = List.of(1, 2, 3);   // immutable, add() throws
List<Integer> ys = new ArrayList<>(xs); // mutable copy

List.of also rejects null elements. Arrays.asList accepts nulls, is fixed-size (backed by the array), and mutates the backing array.

2. `Set` — `HashSet` for speed, `LinkedHashSet` for order, `TreeSet` for sorted¶

Op	HashSet	LinkedHashSet	TreeSet
`add` / `remove` / `contains`	O(1) avg	O(1) avg	O(log n)
Iteration order	none (hash order)	insertion	sorted
Null element	one allowed	one allowed	NOT allowed

HashSet is backed by a HashMap<E, PRESENT>. Everything about HashMap (below) applies.

TreeSet sorts by natural ordering or a Comparator. Elements must be Comparable or you must supply the comparator. It’s a NavigableSet — you get first, last, higher(e), lower(e), ceiling(e), floor(e), headSet, tailSet, subSet.

When TreeSet beats HashSet: you need range queries (“all users with score between 50 and 100”) or you need the elements in sorted order regardless. Otherwise HashSet is 3–10× faster.

3. `Map` — the workhorse¶

`HashMap` internals¶

Backing: array of Node<K,V> buckets (“table”). Default capacity 16, load factor 0.75. Rehash doubles capacity when size > capacity * loadFactor.
Bucket index = (n-1) & hash(key) where n is the table length (power of 2) and hash(key) = key.hashCode() ^ (key.hashCode() >>> 16). The XOR with the high bits spreads entropy.
Collisions: linked-list chain per bucket. At 8 entries in one bucket, the chain is treeified into a red-black tree (as long as the table is at least 64; otherwise it just resizes). Falls back to a list at 6.
Iteration order: undefined. Don’t rely on it.

`LinkedHashMap`¶

Same as HashMap plus a doubly-linked list threading all entries. Iteration is in insertion order by default. Pass accessOrder=true to the constructor and it becomes access order — the basis for an LRU cache in 20 lines:

class LRU<K,V> extends LinkedHashMap<K,V> {
    private final int cap;
    LRU(int cap) { super(cap, 0.75f, true); this.cap = cap; }
    @Override protected boolean removeEldestEntry(Map.Entry<K,V> e) { return size() > cap; }
}

`TreeMap`¶

Red-black tree keyed by natural order or Comparator. O(log n) everything. NavigableMap methods: firstKey, lastKey, higherKey, floorKey, subMap, etc.

`ConcurrentHashMap`¶

Thread-safe. Uses bucket-level locking (“lock striping”). Read operations are lock-free. Rich atomic API: putIfAbsent, computeIfAbsent, compute, merge, forEach, reduce. Never wrap a HashMap in Collections.synchronizedMap if a ConcurrentHashMap will do — the wrapper serializes every operation.

`EnumMap`¶

Keys are enum constants. Backed by an array indexed by ordinal. Faster than HashMap for enum keys, iteration in enum-declaration order. Use it whenever your keys are an enum.

The four verbs you should reach for reflexively¶

map.getOrDefault(key, defaultVal);
map.putIfAbsent(key, val);                       // returns existing if present
map.computeIfAbsent(key, k -> new ArrayList<>()); // lazy init pattern
map.merge(key, 1, Integer::sum);                 // counter pattern

merge is the cleanest way to write a word-frequency counter:

for (var word : words) counts.merge(word, 1, Integer::sum);

4. `Queue` / `Deque` — `ArrayDeque` is the default¶

Interface	Best implementation	Why
`Queue` (FIFO)	`ArrayDeque`	Circular array, no locks, fast
`Deque` (double-ended)	`ArrayDeque`	Same
`Stack` (LIFO)	`ArrayDeque`	Use `push`, `pop`, `peek`
Priority queue	`PriorityQueue`	Min-heap by default
Blocking queue (concurrent)	`LinkedBlockingQueue` / `ArrayBlockingQueue`	Thread-safe with blocking `take`/`put`

⚠️ What most people get wrong¶

They use java.util.Stack. Stack extends Vector, which is legacy and synchronized on every method. Use ArrayDeque as a stack:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
int top = stack.pop();  // 2

Same goes for Vector and Hashtable — both legacy, synchronized, and slower than ArrayList / HashMap even in single-threaded code. Never new them up.

`PriorityQueue`¶

Binary heap. offer/peek/poll are O(log n) / O(1) / O(log n). Ordering by natural order or Comparator. Iterating a PriorityQueue does NOT give you sorted order — only poll in a loop does. This is a classic bug.

Max-heap: new PriorityQueue<>(Comparator.reverseOrder()) or Comparator.comparingInt(x -> -x).

5. Sequenced collections (Java 21)¶

Three new interfaces plug a decade-old hole: uniform first/last access on ordered collections.

SequencedCollection<E>: adds addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed()
SequencedSet<E>: same for sets
SequencedMap<K,V>: firstEntry, lastEntry, putFirst, putLast, sequencedKeySet, etc.

Implementations updated:

List extends SequencedCollection
Deque extends SequencedCollection
LinkedHashSet extends SequencedSet
LinkedHashMap, TreeMap implement SequencedMap

Before Java 21, getting the first element of a LinkedHashSet was a 3-line iterator hack. Now it’s set.getFirst().

6. Iteration and the fail-fast contract¶

Most non-concurrent collections are fail-fast: modifying them during iteration (except via the iterator’s own remove) throws ConcurrentModificationException. This detection is best-effort — don’t rely on it, but expect it.

Safe modification patterns:

// Remove during iteration — use Iterator.remove()
var it = list.iterator();
while (it.hasNext()) {
    if (predicate.test(it.next())) it.remove();
}

// Or use removeIf (Java 8+, cleaner)
list.removeIf(predicate);

// Copy-on-write if reads dominate writes
List<X> concurrent = new CopyOnWriteArrayList<>();

CopyOnWriteArrayList: every mutation copies the whole array. Reads are lock-free. Good only when reads massively outnumber writes (e.g. listener lists).

7. Complexity cheat table¶

Structure	get/contains	add	remove
`ArrayList`	O(1) get / O(n) contains	amortized O(1) end / O(n) mid	O(n)
`LinkedList`	O(n)	O(1) at ends / O(n) mid	O(n)
`ArrayDeque`	O(1) peek	O(1) amortized	O(1) at ends
`HashMap`/`HashSet`	O(1) avg / O(log n) worst (treeified)	O(1) avg	O(1) avg
`LinkedHashMap`/`LinkedHashSet`	O(1) avg	O(1) avg	O(1) avg
`TreeMap`/`TreeSet`	O(log n)	O(log n)	O(log n)
`PriorityQueue`	O(1) peek / O(n) contains	O(log n)	O(log n) poll / O(n) arbitrary
`ConcurrentHashMap`	O(1) avg	O(1) avg	O(1) avg

Memorize this table. study partners ask by this table.

8. Immutable / unmodifiable factories¶

List.of(1, 2, 3);           // immutable list
Set.of("a", "b");            // immutable set (unordered)
Map.of("k", 1, "m", 2);     // immutable map, max 10 entries
Map.ofEntries(Map.entry("k", 1), Map.entry("m", 2), ...);   // unlimited
Collections.unmodifiableList(mutableList);  // view, not a copy
List.copyOf(mutableList);   // immutable snapshot

Collections.unmodifiableList returns a view. If the underlying list changes, the view reflects it. List.copyOf is a copy. In doubt, copy.

9. Streams (quick pointer)¶

Streams get a full treatment in Phase 04. For now, just remember the shape:

List<String> upper = names.stream()
    .filter(n -> n.length() > 3)
    .map(String::toUpperCase)
    .toList();               // Java 16+ shortcut for collect(toList())

Map<String, Long> byLen = words.stream()
    .collect(Collectors.groupingBy(w -> w, Collectors.counting()));

Don’t reach for streams for two-line loops. They’re a tool for pipelines, not a religion.

Practice: 20-minute drill¶

Word count from a List<String> using merge. 3 lines.
LRU cache in LinkedHashMap, capacity 100. 6 lines.
Given List<Person>, group by city into Map<String, List<Person>>. Two ways: for-loop with computeIfAbsent, and stream with groupingBy.
Get the top-3 largest ints from a List<Integer> using PriorityQueue. O(n log 3).
Merge two sorted List<Integer>s into a new sorted list. Iterator-based, no Collections.sort.

Each under 5 minutes.

Return to README.md · Next: 04_io_and_exception_handling.md

Collections Framework Refresher¶

The hierarchy (mental model)¶

1. List — ArrayList is the default¶

ArrayList growth¶

List.of(...) — immutable¶

2. Set — HashSet for speed, LinkedHashSet for order, TreeSet for sorted¶

3. Map — the workhorse¶

HashMap internals¶

LinkedHashMap¶

TreeMap¶

ConcurrentHashMap¶

EnumMap¶