Collections I: List, Set, Map — The Essential Tour
The big picture: two families
Almost every program you've written so far stores a few things in variables. Real programs store thousands — users, orders, log lines, request headers — and Java's collections framework is the standard toolkit for holding them. The whole framework is built on one design choice: there are two families, not one. The Collection family holds elements (a list of names, a set of tags). The Map family holds key → value pairs (a username → profile lookup). Map is deliberately not a Collection: it answers a different question ("given this key, what's the value?") than a collection does ("hold these things in some order").
The takeaway from that diagram: you never choose "a Collection." You choose a List (ordered, duplicates allowed, indexed), a Set (no duplicates), or a Map (key lookup) — and then you pick the implementation whose performance and ordering guarantees match your need. Every choice below is a decision rule, and every decision rule comes with its failure mode.
List: ordered, indexed, duplicates welcome
A List is the closest thing to a resizable array: elements keep insertion order, you can fetch element get(2), and duplicates are fine. Two implementations dominate.
ArrayList — the default
An ArrayList wraps a plain array that grows as needed. Random access is effectively constant time — get(i) is just an array read. The price: inserting or removing in the middle shifts every element after it, which gets expensive for very large lists. Appending at the end is cheap (amortized).
LinkedList — almost never
A LinkedList chains nodes together, so inserting in the middle is cheap once you're there — but reaching position i walks node by node, so get(i) crawls on large lists. It also implements Deque (double-ended queue), which is why it survives in old code. Here's the modern decision rule:
- Random access or iteration →
ArrayList. This is the overwhelmingly common case; make it your default. - Frequent add/remove at both ends (queue or stack behavior) →
ArrayDeque, notLinkedList.ArrayDequeis a resizable circular array: no per-element node objects, better memory locality, and faster in practice for both-end access. - Failure mode: reaching for
LinkedList"because insertion is O(1)" and then indexing into it in a loop — you get O(n) per access and a program that mysteriously slows to a crawl at scale. And iterating aLinkedListwithget(i)in aforloop is the classic version of this bug; use a for-each or iterator instead.
var names = new ArrayList<String>();
names.add("Ava"); names.add("Ben"); names.add("Ava"); // duplicates are fine
System.out.println(names.get(1)); // Ben
System.out.println(names); // [Ava, Ben, Ava]
var queue = new ArrayDeque<String>(); // modern two-ended queue
queue.addLast("first"); queue.addLast("second");
queue.addFirst("urgent");
System.out.println(queue.removeFirst()); // urgentOutput:
Ben
[Ava, Ben, Ava]
urgent(A note on syntax: ArrayList<String> uses generics — the <String> says "this list holds strings." You'll use this syntax everywhere in this post; the full generics story, including wildcards, gets its own post next.)
Set: uniqueness, with three flavors of order
A Set answers one question: "is it in there?" Duplicates are silently rejected — add returns false when the element already exists. The three implementations differ in ordering guarantees and cost:
HashSet— unordered, backed by a hash table. Add/contains/remove are effectively constant time. Decision rule: membership testing or deduplication where order doesn't matter. Failure mode: depending on its iteration order — it's arbitrary and can change as the set grows. (This is also why your earlier equality lesson matters:HashSetrelies onhashCode()being consistent withequals(). Break that contract and duplicates sneak in.)LinkedHashSet— insertion order preserved, still effectively constant-time operations. Decision rule: you want dedup plus a predictable, stable order — e.g., collecting unique tags in the order the user typed them.TreeSet— elements kept sorted, operations in logarithmic time. Decision rule: you need sorted output or range queries ("everything between A and M"). Failure mode: elements must be mutually comparable — strings and numbers work out of the box, but your own classes needComparableor aComparator, or you get aClassCastExceptionat runtime. (Post 14 covers ordering in depth; this is just the teaser.)
var tags = new HashSet<String>();
tags.add("java"); tags.add("spring"); tags.add("docker");
System.out.println(tags.size()); // 2 — duplicate silently rejected
var ordered = new LinkedHashSet<String>();
ordered.add("java"); ordered.add("spring"); ordered.add("docker");
System.out.println(ordered); // [java, spring, docker] — insertion order
var sorted = new TreeSet<String>();
sorted.add("java"); sorted.add("spring"); sorted.add("docker");
System.out.println(sorted); // [docker, java, spring] — sortedOutput (the HashSet line is intentionally not shown — its order is arbitrary, and that's the point):
2
[java, spring, docker]
[docker, java, spring]Map: keys that find values
A Map stores key → value pairs: look up the value for a key, typically in constant time. Keys are unique (putting the same key twice replaces the value); values may repeat. The same three ordering flavors apply:
HashMap— unordered, effectively constant-time get/put. Decision rule: your default for lookups: caches, indexes, frequency counts, grouping.LinkedHashMap— insertion order preserved. Decision rule: when you iterate the map later and want "the order I put them in" — configuration entries, ordered results.TreeMap— keys kept sorted. Decision rule: sorted keys or range lookups ("all orders from January"). SameComparable/Comparatorrequirement on keys asTreeSet.
Failure mode: using a HashMap and then being surprised that "the output order changed between runs." It didn't change maliciously — you just never had an ordering guarantee. If order matters to your program's correctness or your test assertions, pick the ordered variant up front.
var scores = new HashMap<String, Integer>();
scores.put("Ava", 95);
scores.put("Ben", 82);
scores.put("Ava", 97); // same key: value REPLACED
System.out.println(scores.get("Ava")); // 97
System.out.println(scores.containsKey("Zoe")); // false
// the classic frequency-count idiom:
var wordCounts = new HashMap<String, Integer>();
for (var word : List.of("the", "cat", "sat", "the", "mat", "the")) {
wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
}
System.out.println(wordCounts.get("the")); // 3Output:
97
false
3Next post goes deep on HashMap internals — hashing, collisions, capacity, and the equals/hashCode contract in action. For now, the decision rules above are all you need to choose correctly.
Iteration: three idioms, and why for-each removal explodes
You'll iterate collections constantly. There are three idioms, in order of preference:
- For-each — the default for read-only traversal:
for (var name : names) { System.out.println(name); } Iterator— when you need to remove elements while traversing:var it = names.iterator(); while (it.hasNext()) { if (it.next().startsWith("X")) { it.remove(); // safe: the iterator's own removal } }removeIf— the modern one-liner for conditional removal, usually the best choice:names.removeIf(name -> name.startsWith("X"));
Now the famous trap. This looks reasonable and compiles fine:
for (var name : names) {
if (name.startsWith("X")) {
names.remove(name); // DON'T — throws ConcurrentModificationException
}
}It throws ConcurrentModificationException because Java's collection iterators are fail-fast: each iterator snapshots the collection's modification count when it's created, and on every step it checks whether the collection was structurally modified outside the iterator. If it was, the iterator fails immediately rather than silently producing garbage — skipping elements, revisiting elements, or corrupting internal state depending on the implementation. That's the design philosophy: a loud, obvious exception at the exact point of the bug beats a subtly wrong result that surfaces three methods later. The exception name is a historical quirk — nothing is actually concurrent here; "concurrent" just means "modified while iteration was in progress." The fixes are the idioms above: Iterator.remove() (which updates the count itself) or removeIf (which does the whole pass internally).
Unmodifiable collections: say what you mean
Modern Java (9+) gives you factory methods that create compact, unmodifiable collections in one expression:
var roles = List.of("admin", "editor", "viewer");
var flags = Set.of("dark-mode", "beta");
var config = Map.of("host", "localhost", "port", "8080");These are genuinely unmodifiable — any add, put, or remove throws UnsupportedOperationException. They also reject null elements/keys/values outright (a NullPointerException at creation, which is a feature: it surfaces bad data immediately). Decision rule: when a collection is built once and only read afterward — constants, configuration, fixed lookup tables — use List.of / Set.of / Map.of. It documents intent and the runtime enforces it.
Failure mode: handing someone a mutable list "for reading" and discovering they sorted it, mutating your state. If you must wrap an existing mutable collection, Collections.unmodifiableList(existing) returns a read-only view — but note the caveat: it's a view, not a copy, so changes to the original list still show through. For a true snapshot, copy first (List.copyOf(existing)), then it's unmodifiable.
When iteration order matters
This post keeps coming back to order, so here's the consolidated rule of thumb:
- Order never matters (pure membership/lookup):
HashSet,HashMap. Cheapest, and the lack of order is a feature — it keeps you honest. - Insertion order matters (stable, predictable output; "in the order added"):
LinkedHashSet,LinkedHashMap, or justArrayList. - Sorted order matters (rankings, ranges, alphabetical output):
TreeSet,TreeMap— with the comparability requirement in mind.
A practical test: if your unit test asserts on the string form of a collection (e.g., "[java, spring]"), you need a deterministic order, which means you need one of the ordered variants. Tests written against HashMap ordering are flaky by construction — they may pass a hundred times and then fail on a different JVM or after adding an eleventh entry.
Quick recap of the decision rules: List when order and indexing matter (ArrayList by default, ArrayDeque for both-end access); Set when uniqueness matters (HashSet unordered, LinkedHashSet insertion-ordered, TreeSet sorted); Map when key lookup matters (HashMap default, ordered/sorted variants when iteration order matters). Remove during iteration with Iterator.remove() or removeIf, never inside a for-each. Reach for List.of/Set.of/Map.of for read-only data. Next up: inside HashMap — how hashing actually works and what happens when it goes wrong.
Continue: Java Learning Roadmap 2026
Comments
Post a Comment