Java Programming
The Java Collections Framework: Lists, Sets, Maps and Queues
Beginner8 min readUpdated
The collections framework is the part of the JDK you use in every program, and choosing the wrong implementation is a quiet source of bugs and slow code. This guide explains the interface hierarchy, the performance characteristics of each main implementation, how hashing and ordering actually work, and the immutable and concurrent variants. You will finish able to pick the right collection for a job and justify it.
What you will learn
- Navigate the Collection, List, Set, Queue and Map hierarchy and know what each interface promises
- Choose an implementation by access pattern and explain its time complexity
- Explain why hashCode and Comparable matter to HashSet, HashMap and TreeMap
- Iterate and modify collections safely, including removal during iteration
- Use immutable factories, views and the Collections utility methods correctly
Every Java program that handles more than one thing at a time uses java.util. The framework is small enough to learn fully — a handful of interfaces and a dozen implementations you will actually use — yet detailed enough that picking LinkedList where ArrayList belonged, or HashMap where TreeMap was needed, quietly costs performance or correctness. This guide gives you the hierarchy, the cost model, the rules about hashing and ordering, and the operations that experienced developers reach for. Code targets Java 21.
The interface hierarchy
The framework separates what a collection promises (interfaces) from how it stores data (implementations). Program against the interface and choose the implementation at the point of construction.
Iterable
└── Collection
├── List ordered, indexed, duplicates allowed
├── Set no duplicates
│ └── SortedSet → NavigableSet sorted by natural order or Comparator
└── Queue head-first access
└── Deque both ends
Map (not a Collection) key → value, unique keys
└── SortedMap → NavigableMap
Map is deliberately outside Collection: a map is a set of associations, not a bag of elements, and its keySet(), values() and entrySet() are the views through which you treat it as one.
Java 21 added sequenced collections (JEP 431): SequencedCollection, SequencedSet and SequencedMap give List, Deque, LinkedHashSet, LinkedHashMap and the sorted types uniform getFirst(), getLast(), addFirst(), removeLast() and reversed() methods. Before 21 you needed list.get(list.size() - 1) or a ListIterator walked backwards.
Lists
A List is an ordered sequence with positional access. Two implementations matter.
ArrayList stores elements in an array that grows (by roughly half) when full. Index access is constant time, appending is amortised constant time, and inserting or removing in the middle costs a memory shift of the tail — fast in practice because System.arraycopy is a tight native loop. Iteration is cache-friendly. This is the default list.
LinkedList is a doubly linked chain of nodes. Positional access walks from an end, so get(i) is linear; every node is a separate object with two pointers, so memory is three to four times an ArrayList for small elements and iteration jumps around the heap. It only wins for removal at a cursor already positioned by a ListIterator. It also implements Deque, but ArrayDeque does that job better.
List<String> hosts = new ArrayList<>(List.of("db1", "db2", "cache"));
hosts.add("queue");
hosts.set(0, "db-primary");
hosts.remove("cache"); // remove by value (first match)
hosts.remove(0); // remove by index — beware with List<Integer>
String last = hosts.getLast(); // Java 21
hosts.sort(Comparator.naturalOrder());
The remove overload trap is real: List<Integer> has both remove(int index) and remove(Object o), and list.remove(3) picks the index version. Write list.remove(Integer.valueOf(3)) to remove by value.
Sets and the hashing contract
A Set rejects duplicates, where "duplicate" means equals returns true. How it detects them depends on the implementation.
HashSet stores elements in a hash table. add, contains and remove are constant time on average, iteration order is unspecified and may change when the set resizes. It relies on the contract from Object: elements that are equals must have the same hashCode. Break that (by overriding one without the other) and the set stores "duplicates" or fails to find elements it contains. Since Java 8, a bucket with many colliding keys degrades to a balanced tree rather than a linked list, so pathological hash functions hurt less, but a good hashCode still matters.
LinkedHashSet is a HashSet that also keeps a linked list of insertion order. Same cost, predictable iteration, slightly more memory. Use it when tests, logs or users will see the order.
TreeSet keeps elements sorted in a red-black tree by their natural order (Comparable) or a Comparator you supply. Operations are logarithmic and you gain range queries: headSet, tailSet, subSet, ceiling, floor. A TreeSet decides equality with compareTo or compare, not equals, so a comparator that returns 0 for distinct elements will drop one of them.
EnumSet is a bit-vector specialised for enum elements: tiny, extremely fast and the correct choice whenever the element type is an enum.
record Tag(String name) implements Comparable<Tag> {
@Override public int compareTo(Tag o) { return name.compareToIgnoreCase(o.name); }
}
Set<Tag> tags = new TreeSet<>();
tags.add(new Tag("Java"));
tags.add(new Tag("java")); // compareTo says equal → not added
System.out.println(tags.size()); // 1, even though the records are not equals()
Maps
A Map associates unique keys with values. The same three storage strategies apply.
| Implementation | Lookup | Ordering | Nulls | Use when |
|---|---|---|---|---|
HashMap | O(1) average | None | One null key, null values | Default choice |
LinkedHashMap | O(1) average | Insertion (or access) order | Same as HashMap | Predictable iteration, LRU caches |
TreeMap | O(log n) | Sorted by key | No null keys | Range queries, sorted output |
EnumMap | O(1) | Enum declaration order | No null keys | Enum keys |
ConcurrentHashMap | O(1) average | None | No null keys or values | Shared between threads |
The Map interface gained a set of methods in Java 8 that replace the classic "check, then put" dance:
Map<String, List<String>> byDept = new HashMap<>();
// Before Java 8
List<String> names = byDept.get("eng");
if (names == null) { names = new ArrayList<>(); byDept.put("eng", names); }
names.add("Ada");
// Now
byDept.computeIfAbsent("eng", k -> new ArrayList<>()).add("Ada");
Map<String, Integer> counts = new HashMap<>();
counts.merge("java", 1, Integer::sum); // increment or initialise
int hits = counts.getOrDefault("kotlin", 0);
counts.putIfAbsent("scala", 0);
counts.replaceAll((k, v) -> v * 2);
computeIfAbsent, merge and getOrDefault are the three to memorise. Iterate a map through entrySet() when you need both halves; iterating keySet() and calling get for each key does two lookups per entry.
LinkedHashMap has a constructor flag for access order and a removeEldestEntry hook, which together make a bounded LRU cache in about ten lines — a common interview question and an occasionally useful production tool.
Keys must be stable. A key whose hashCode changes after insertion (a mutable object with a hash based on its fields) is lost: the map looks in the bucket for the new hash and never finds it. Use immutable keys — strings, numbers, enums, records.
Queues, deques and stacks
Queue offers head-first access with two method families: add/remove/element throw when they cannot proceed, while offer/poll/peek return false or null instead. Deque extends this to both ends.
ArrayDeque is a resizable circular array and the right implementation for both a FIFO queue and a LIFO stack. It is faster than LinkedList for both and faster than the legacy Stack class, which is synchronised and extends Vector — do not use Stack in new code.
PriorityQueue is a binary heap that always returns the smallest element by natural order or comparator. Insertion and removal are logarithmic; iteration order is not sorted, only poll() is.
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second
Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.addAll(List.of(3, 9, 1));
System.out.println(pq.poll()); // 9
Blocking variants — ArrayBlockingQueue, LinkedBlockingQueue — add put and take that wait, and belong to the concurrency toolbox.
Iteration, ordering and modification
The for-each loop compiles to an Iterator: hasNext(), next(), repeat. Most non-concurrent collections are fail-fast: if the collection is structurally modified during iteration by anything other than the iterator's own remove, the next next() throws ConcurrentModificationException. This is a best-effort detection of a bug, not a thread-safety guarantee.
List<Order> orders = ...;
// Wrong: throws ConcurrentModificationException
for (Order o : orders) if (o.isCancelled()) orders.remove(o);
// Right, and shortest
orders.removeIf(Order::isCancelled);
// Also right, when you need the iterator anyway
for (Iterator<Order> it = orders.iterator(); it.hasNext(); ) {
if (it.next().isCancelled()) it.remove();
}
Sorting is either in place — list.sort(comparator) or Collections.sort(list) — or into a new collection with a stream. Comparator composes well: Comparator.comparing(Person::lastName).thenComparing(Person::firstName).reversed(), with nullsFirst/nullsLast for optional fields. The sort is a stable merge sort (TimSort), so equal elements keep their relative order, which matters when you sort by one key after another.
Immutable collections and views
Java 9 introduced convenience factories: List.of(...), Set.of(...), Map.of(k1, v1, ...), Map.ofEntries(...), and Java 10 added List.copyOf, Set.copyOf, Map.copyOf. They return unmodifiable collections: any mutator throws UnsupportedOperationException, null elements are rejected, and Set.of/Map.of throw on duplicate keys. Their iteration order is intentionally randomised per JVM run so that no one accidentally depends on it.
Distinguish three things that look alike:
- Immutable collection (
List.of): cannot change, ever. - Unmodifiable view (
Collections.unmodifiableList(inner)): you cannot change it through the view, but if the original changes, the view reflects it. Good for exposing internal state without copying. - Defensive copy (
new ArrayList<>(inner)orList.copyOf(inner)): a snapshot that neither side can affect.
Views are everywhere in the framework: map.keySet(), list.subList(a, b), Arrays.asList(array) are all live windows onto other data. Removing from keySet() removes from the map; clearing a subList removes that range from the list. Powerful when intended, surprising when not.
Collections also offers synchronizedList and friends, which wrap every method in a lock. They make individual calls safe but not sequences of calls (check-then-act) or iteration, and are mostly superseded by the java.util.concurrent collections.
Choosing an implementation
Give an initial capacity when you know the size: new ArrayList<>(10_000) or HashMap.newHashMap(expected) (Java 19) avoid a series of resizes. And size the collection you return: returning List.of() or Collections.emptyList() costs nothing, whereas allocating an empty ArrayList for every call adds up.
Common mistakes
Mutable hash keys. A Set<Point> where Point has setters, or a map keyed by a list you then append to, silently loses elements. Keys must be immutable.
Relying on HashMap order. It is unspecified and changes with resizing and JDK version. Tests that pass by luck fail after a refactor.
Arrays.asList on a primitive array. Arrays.asList(new int[]{1, 2}) gives a List<int[]> with one element. Use IntStream.of(...).boxed().toList() or an Integer[].
Treating subList as a copy. It is a view; structural changes to the parent invalidate it, and changes through it alter the parent.
Using LinkedList as a queue or Stack as a stack. ArrayDeque is faster and lighter for both.
Null in modern collections. List.of, Map.of and ConcurrentHashMap reject null. Decide up front whether null is meaningful in your data; usually it is not, and Optional or an explicit sentinel is clearer.
Iterating keySet() then calling get. Two lookups per entry; iterate entrySet().
Sorting a TreeSet comparator inconsistently with equals. Elements the comparator sees as equal are deduplicated even if equals disagrees. Either make them consistent or document the difference.
Key takeaways
- Declare variables by interface (
List,Set,Map,Deque) and choose the implementation at construction. ArrayList,HashSet,HashMapandArrayDequeare the defaults; reach forLinked*when iteration order matters andTree*when you need sorting or range queries.- Hash-based collections depend on a consistent
equals/hashCodepair and on keys that never change; tree-based ones depend on the comparator alone. - Modify during iteration only through
removeIfor the iterator; anything else throwsConcurrentModificationException. List.ofand friends are immutable and null-hostile;Collections.unmodifiable*andsubListare live views;copyOfand copy constructors are snapshots.- Use
computeIfAbsent,mergeandgetOrDefaultinstead of check-then-put, andentrySet()for iteration.
Sources and further reading
Frequently asked questions
- When should I use LinkedList instead of ArrayList?
- Almost never. ArrayList wins on iteration, random access and memory, and even insertions in the middle are usually faster because the memory copy is cheap compared with LinkedList's pointer chasing. Use ArrayDeque for a queue or stack, and reserve LinkedList for the rare case of frequent insertion and removal through a ListIterator at a known position.
- Why does HashMap iteration order change?
- HashMap stores entries in buckets chosen by hash code, and the bucket count changes as the map grows, so order depends on both the keys and the history of insertions. If you need insertion order use LinkedHashMap; if you need sorted keys use TreeMap. Never rely on HashMap order, even if it looks stable in a test.
- What is the difference between List.of and Arrays.asList?
- List.of (Java 9) returns a fully immutable list that rejects nulls and throws on any modification. Arrays.asList returns a fixed-size list backed by the array: you can call set, which writes through to the array, but add and remove throw. For a genuinely mutable copy, use new ArrayList<>(source).
- How do I remove elements from a list while iterating?
- Use removeIf with a predicate for the common case, or use an explicit Iterator and call iterator.remove(). Calling list.remove inside a for-each loop throws ConcurrentModificationException on the next iteration because the iterator detects the structural change.