The ArrayCatalog you closed the previous lesson with works, but three lines out of four are infrastructure: a counter n running parallel to length, an Arrays.copyOf to double the capacity, a System.arraycopy to close gaps, a manual null to avoid leaking memory. None of those lines talks about libraries, loans or employees. And even with all that effort, the catalogue still cannot guarantee there are no repeated ISBNs without walking it end to end, nor find a material by its reference in less than O(n).

The Java Collections Framework is the JDK's answer to that problem, and it is one of the finest pieces of design on the platform. It is not "a few useful classes": it is an architecture of interfaces, implementations and algorithms that has been the common vocabulary of every Java programmer for twenty-five years. Learning it properly means two things. First, that you will stop writing infrastructure. Second, and more important, that you will learn to choose the right data structure, which is one of the decisions with the greatest impact on the performance and the clarity of a real program.

This lesson is the map. It does not go deep into any implementation —that is the next seven lessons— but gives you the aerial view: which interfaces exist and how they relate, which implementation to choose for each problem, how traversal works inside and which operations all collections share. The master table in section 4 is the heart of the whole module; you will come back to it again and again.

1. What the Collections Framework is
2. The interface hierarchy
3. Declare by the interface, instantiate the implementation
4. The master table of implementations
5. Generics in collections
6. Iterable, Iterator and the for-each from the inside
7. ConcurrentModificationException: fail-fast explained
8. The common methods of Collection
9. Immutable and convenience collections
10. How to choose the right collection
11. BiblioTech's first refactoring
12. Common Mistakes and Tips
13. Exercises

A collection is an object that groups several elements and knows how to manage them: add, remove, search, count, traverse. Compared with the array, a collection has three decisive virtues:

• It grows and shrinks on its own. There is no capacity to administer.
• It has semantics. A Set guarantees there are no duplicates; a Queue guarantees FIFO order. The array guarantees nothing: it only stores.
• It is interchangeable. Since they all implement the same interfaces, swapping ArrayList for LinkedList is a one-word change.

The Framework is organised into three layers that are worth distinguishing from the start:

That separation is the direct application of everything you learned in module 4. List is an interface in the exact sense of 04-01: a contract that says what can be done without saying how. ArrayList and LinkedList are two different implementations of the same contract, and the polymorphism of 03-06 lets you swap them without touching the code that uses them. The Collections Framework is probably the best example of interface-oriented design you are going to find.

Everything lives in java.util, so almost any class you write will start with one of these imports:

This is the structure you need burned into memory:

And apart from that, with no inheritance relationship to the above:

Read the two hierarchies like this, top to bottom:

• Iterable is the most general interface of all and promises only one thing: "I can give you an iterator to walk me one by one". Anything that is Iterable works with for-each. Notice that an array is not Iterable —it is not a class, it implements nothing—; the for-each over arrays works because the compiler treats it as a special case (you will see it in section 6).
• Collection adds the basic "group of elements" vocabulary: add, remove, contains, size, isEmpty, clear. It is the minimum common to lists, sets and queues.
• List: elements ordered by position, with an index and duplicates allowed. It is the natural equivalent of the array.
• Set: no duplicates, no access by index. It models the mathematical concept of a set.
• Queue: elements in a processing order, normally FIFO. You add at one end and consume at the other.
• Deque: a double-ended queue; it serves as both a queue and a stack.

It is the question everybody asks the first time, and it has a precise answer: a Collection stores loose elements; a Map stores key→value pairs. The methods of Collection would make no sense on a map:

• What would map.add(x) do? Is x a key, a value, a pair?
• What would map.iterator() return? Keys, values or pairs?
• What would map.contains(x) check? The map needs two different questions: containsKey and containsValue.

Forcing Map extends Collection would have produced an interface full of ambiguous or unsupported methods. The design solution is cleaner: Map is an independent hierarchy, and it offers three views that are collections:

And those three views are Iterable, so they can indeed be walked with for-each. It is the best of both worlds: Map keeps its own coherent API and stays connected to the rest of the Framework through its views. You will see it in detail in 05-05.

This is the golden rule of the Framework, and probably the most profitable professional habit in this lesson:

To the left of the =, the most general type that covers what you need (the interface). To the right, the concrete implementation. The reasons:

1. You can change implementation by touching one word. If tomorrow you find you need queue behaviour, you change new ArrayList<>() for new LinkedList<>() and nothing else in the program notices. If you had declared ArrayList<Book>, you have to revise every declaration, every parameter and every return type.

2. Your method signatures become flexible. Compare:

The practical rule for signatures: ask for the most general type that serves you. If you only traverse, Iterable or Collection. If you need indices, List. When returning, on the other hand, it pays to be a little more specific so as not to hide useful guarantees (if you return something without duplicates, declare it as a Set).

3. You communicate the intent, not the mechanism. List<Book> says "an ordered sequence with possible repetition". ArrayList<Book> also says "implemented on top of an array", an internal detail the caller does not care about.

The exceptions are few and explicit: when you need a method that exists only in the implementation. ArrayList has trimToSize(), LinkedList has addFirst() inherited from Deque. In those cases, declare by the type that offers the method you actually use:

And a note on the diamond operator <>: since Java 7, the type on the right-hand side is inferred from the left, so new ArrayList<Book>() is written new ArrayList<>(). Always write it that way.

This table is the heart of the module. Each row is a lesson or a section of the next seven, but having them together gives you something no isolated lesson does: a criterion for choosing.

* Amortised: almost always O(1), but when the internal array fills up there is an O(n) copy. You will see why the average is still O(1) in 05-03.

Read the table by columns and the patterns that really matter will come out:

• The "Order" column has three values. None means the traversal order is unpredictable and can change between runs or when elements are added: never depend on it. Insertion means it is walked in the order you put the elements in. Sorted means by Comparable or Comparator (05-09).
• The "O(1) versus O(log n)" column sums up the difference between hash structures (HashXxx) and tree ones (TreeXxx): the hash is faster, the tree keeps the order. Choosing means deciding whether you need that order.
• The "null" column is a huge source of unexpected NullPointerExceptions. The "modern" structures (ArrayDeque, PriorityQueue) reject them on purpose, because they use null as an internal "empty" signal. The tree ones reject them because null cannot be compared with compareTo.
• The bold rows in "when to choose it" are the four default answers: ArrayList, HashSet, HashMap, ArrayDeque. Always start with one of them and change only if you have a concrete reason.

All collections are generic: they carry between angle brackets the type of element they hold.

For now, read it like this: <...> is the type of what is inside. List<Book> is "a list of books". Map<String, Material> is "a map whose keys are strings and whose values are materials". Nothing more.

What you gain is compile-time safety:

Before Java 5 collections stored Object, and every read required a cast that could fail at run time:

Generics move that error from run time to compile time, which is exactly where you want your errors. Never use raw types (without <>); the compiler will warn you with an unchecked warning and it will be right.

Generics only accept reference types, not primitives. List<int> does not compile; you have to write List<Integer>. The autoboxing of 01-04 does the conversion automatically and the code looks natural:

But the cost is real and worth knowing:

For a million integers, the difference is about 4 MB versus more than 20 MB, and several times slower to walk. In a business application it makes no difference; in intensive numerical computation, it does. The rule: use collections unless you work with lots of primitives and performance is critical, in which case the array wins.

There is also an Integer comparison trap you already saw in 01-05 and that reappears here:

The full theory of generics —your own type parameters (class Box<T>), wildcards (? extends, ? super), bounds (<T extends Comparable<T>>) and the type erasure that explains why List<int> is impossible— is lesson 10-01. In this module it is enough for you to use the existing generics.

The for-each you learned in 05-01 is not magic: it is syntactic sugar. The compiler translates it into something else, and knowing what will explain several behaviours at once that otherwise look arbitrary.

Over an array, the compiler generates a classic for:

Over an Iterable (any collection), it generates a loop with an iterator:

An Iterator is an object that represents a position within a traversal and offers three methods:

The design is a beautiful application of the principle from 04-01: Iterator is a contract that decouples the traversal from the structure. An ArrayList implements it by moving an index; a LinkedList, by jumping from node to node; a HashSet, by walking buckets. Your loop is unaware of any of those differences.

You will not normally write iterators by hand. There is one important exception, and it is the reason they exist: removing elements while you traverse.

And, since Iterable is the most general interface of all, a method that only traverses can accept it and work with any data source:

Iterable also offers forEach, which takes one of the Consumers you mastered in 04-06:

It is equivalent to a for-each and sometimes more readable, especially when you already have the method reference written. And in module 10 you will see that stream() opens a third, far more expressive way to filter, transform and group in a single expression; in this module we will always traverse with for-each, Iterator and the collections' own methods.

Now, the error that generates more internet searches than anything else in the Framework:

The name is misleading: no concurrent thread is needed. "Concurrent" here means "during the traversal". What happens is this.

Every collection carries an internal counter called modCount (modification count) that is incremented every time its structure changes: every add, every remove, every clear. When you ask for an iterator, it saves a copy of the current modCount. And on every next(), the iterator compares:

If the collection changed behind the iterator's back, the two counters differ and the iterator refuses to continue.

This policy is called fail-fast: fail early and loudly. And it is a virtue, not a whim. If the iterator carried on, the traversal would fall out of sync and the result would be worse than an exception: elements silently skipped. Check it with this example, which does not throw an exception and is still wrong:

When you remove element 0 from a list of 3, the size drops to 2 and the iterator's internal index moves to 1, so hasNext() (which compares 1 != 2) gives true, "Nuria Vidal" is returned, the index moves to 2 and hasNext() gives false: the loop ends early and "Diego Alonso" is never visited. If the element to remove is the second to last, the traversal ends without an exception and without having looked at the last one. That is the scenario fail-fast tries to prevent; the fact that it sometimes does not fire is an accident of the counting, not a guarantee.

1. Iterator.remove() — the classic solution, valid in any version of Java:

2. removeIf(Predicate) — since Java 8, the solution preferred for readability:

One line, no visible iterator, and with the Predicate from 04-06. It is what you should write by default.

3. Traverse a copy — when you need to modify the original while reading it whole:

It costs memory (it duplicates the list) but it is indispensable when the operation inside the loop can add and remove elements.

4. Traverse backwards with indices — useful if you need the position:

Backwards, because when you remove element i the following ones shift; going in reverse, the ones already visited do not move.

That last row matters: for (Material m : catalog) { m.lend(); } is perfectly legal. modCount counts structural changes in the collection, not changes in the objects it holds.

Anything that is a Collection —any List, Set or Queue— understands this vocabulary:

Two observations about the returned value that solve real problems:

add returns a boolean, and in a Set that boolean is worth gold. false means "it was already there", so detecting duplicates is one line:

remove and contains use equals, not ==. That is why 03-09 insisted so much on implementing it properly: if your class does not override equals, contains will compare references and an "equal" but distinct object will never be found.

And toArray closes the circle with the previous lesson:

The new Material[0] is not a waste: it tells the method what type of array to create. Passing new Material[list.size()] is also valid and tends to be slightly slower on modern JVMs, odd as that sounds. Always use new Material[0].

Since Java 9 there are factory methods that create immutable collections in a single expression:

Their properties, which have to be known in detail because they are surprising:

• Completely immutable: any add, remove, set or clear throws UnsupportedOperationException.
• They do not accept null, neither as an element, nor as a key, nor as a value: they throw NullPointerException on creation.
• Set.of and Map.of reject duplicates on construction, with IllegalArgumentException. It is deliberate: if you write Set.of("a", "a") it is almost certainly a mistake of yours.
• Map.of accepts up to 10 pairs. For more, Map.ofEntries(Map.entry(k, v), ...).
• Their traversal order is not guaranteed and can change between runs (in Set.of and Map.of it is deliberately randomised so that nobody depends on it). List.of does preserve the order, because a list is ordered by definition.

They are perfect for constants, fixed tables and configuration values:

Collections.unmodifiableList does something similar but not the same: it creates a read-only view over an existing list.

For a genuine defensive copy in a getter (the pattern from 03-07), unmodifiableList is not enough if the caller can reach the original list. The correct thing is List.copyOf(list) or Collections.unmodifiableList(new ArrayList<>(list)).

And there are three more utilities for frequent cases:

Their value lies in a design tip worth adopting right now: never return null where a collection is expected. Return an empty collection. The caller will be able to write for (Material m : catalog.find(...)) without checking anything, and a whole family of NullPointerExceptions disappears.

This tree resolves the vast majority of real decisions:

And in five questions, in case you prefer the list format:

1. Do I search by key? → Map. (HashMap unless you need order.)
2. Are duplicates an error? → Set. (HashSet unless you need order.)
3. Do I need positions and indices? → List. (ArrayList almost always.)
4. Do I only add at one end and take from the other? → Deque / Queue. (ArrayDeque.)
5. Do I always want to deal with the most urgent one first? → PriorityQueue.

A warning about premature optimisation: for collections of tens or hundreds of elements, the performance difference between implementations is irrelevant. Choose by semantics: Set when duplicates are a conceptual error, Map when a key genuinely exists. A Set<String> of ISBNs documents that ISBNs are unique better than any comment. Performance matters from tens of thousands of elements upwards, and there the table in section 4 will give you the right answer.

Let us apply what we have learned to the ArrayCatalog of the previous lesson. Remember what it looked like:

And this is how it looks with collections:

Usage:

Count what has disappeared: the field n, the capacity check, the Arrays.copyOf to grow, the System.arraycopy to remove, the manual null, the final trimming of the result array. And count what has appeared: a Set<String> that guarantees in O(1) that there are no repeated ISBNs, something the array version did not have and that would have cost an O(n) loop on every registration.

There is still a weakness, and it is deliberate: remove and any search by reference walk the whole list, O(n). With a Map<String, Material> it would be O(1). That is 05-05.

Declaring by the implementation. ArrayList<Book> list = new ArrayList<>() works, but it ties you down. Write List<Book> list = new ArrayList<>(). In your method parameters, ask for the most general type that serves you: Collection or Iterable if you only traverse.

Using raw types. List list = new ArrayList(); compiles with a warning and returns Object, forcing casts that fail at run time. Always put the <Type> in.

Modifying the collection inside a for-each. It is the number one cause of ConcurrentModificationException. Use removeIf for simple criteria, Iterator.remove() for complex logic, or traverse a copy if you also add.

Trusting the order of a HashSet or HashMap. There is no guaranteed order and it can change when elements are added or between Java versions. If you need reproducible order, use the Linked or Tree variants. A test that depends on the order of a HashSet is a test that will fail one day.

Putting objects without correct equals/hashCode into a Set or using them as Map keys. The object will be stored but never found. In 05-05 you will see the exact demonstration and the reason why; for now, if an object is going into a Set or a Map key, revisit 03-09.

Expecting List.of to be modifiable. It returns an immutable list. If you need to modify it: new ArrayList<>(List.of(...)).

Confusing unmodifiableList with a copy. It is a view: if somebody modifies the original list, the view changes. For a real defensive copy, List.copyOf(list).

Returning null instead of an empty collection. It forces the caller to check for null on every use and guarantees a NullPointerException the day somebody forgets. Return List.of() or Collections.emptyList().

Comparing Integers with == inside collections. It works up to 127 because of the integer cache and fails from 128 upwards. Always use equals, or compare with intValue().

Performance tip: do not optimise without measuring. For 200 elements, ArrayList and LinkedList are indistinguishable. Choose by semantics; performance shows up from tens of thousands upwards, and by then you will have the table from section 4.

For each BiblioTech requirement, state which interface and which implementation you would use and why. Write the variable declaration too.

1. The full catalogue, walked often and displayed in the order in which items were registered.
2. The ISBNs already catalogued, to reject duplicate registrations instantly.
3. Finding a material by its reference without walking the catalogue.
4. The loans pending processing, dealt with in order of arrival.
5. The due-date notices, always dealing first with the one with the most days late.
6. The material types that exist, always listed alphabetically.
7. The last 10 operations, so that the most recent one can be undone.
8. The loan days by type, as a program constant.

Write a class CatalogPurge with three static methods that take a List<Material> and remove the materials whose title is empty or whose reference is null:

• purgeWithIterator(List<Material>), using an explicit Iterator.
• purgeWithRemoveIf(List<Material>), in one line.
• purgeOverCopy(List<Material>), traversing a copy.

Add a method demonstrateError(List<Material>) that deliberately triggers the ConcurrentModificationException, with a comment explaining at exactly what moment it will fire.

Write a utility class Traversals with methods that accept the most general type possible:

• int count(Iterable<?> source): counts the elements of anything traversable.
• String join(Iterable<Material> materials, String separator): concatenates the titles.
• double sumRates(Collection<Material> materials).
• List<Material> available(Collection<Material> materials): those that are available, always returning a list (empty if there are none, never null).

Show that they all work the same with an ArrayList, a HashSet, a List.of(...) and a map's keySet() where appropriate.

Solution 1

The cross-cutting lesson of the exercise: the right collection follows from the wording. "No repeats" says Set. "Search by" says Map. "In order of arrival" says Queue. "Undo" says stack. If you have to think about it a lot, the requirement is probably not well formulated.

Solution 2

The three valid versions do the same thing at different costs: removeIf and Iterator.remove operate on the original list with no extra memory; purgeOverCopy duplicates the list, and only pays off when the loop also adds elements. The removeIf version is also the only one that reads at a glance.

Solution 3

A demonstration that the general type is what gives you the flexibility:

A single method, count, works over five different sources —including a map's views— because it asks for Iterable, the minimum contract they all fulfil. It is the golden rule of section 3 taken to method signatures, and it is what separates a rigid API from a reusable one. When you meet Streams in module 10, this same flexibility will be expressed even more compactly, but the principle will be the same.

You now have the full map. You know that the Collections Framework is organised into three layers —interfaces that define contracts, implementations that pick the data structure and algorithms that operate over any of them— and that this separation is the JDK's best example of interface-oriented design. You know the hierarchy: Iterable → Collection → List/Set/Queue, with Deque extending Queue and the Sorted/Navigable variants; and you know why Map stands apart: it stores pairs, not loose elements, and add, contains and iterator would be ambiguous on it. You also know that it reconnects to the rest of the Framework through its three views: keySet, values and entrySet.

You have adopted the golden rule: List<Book> catalog = new ArrayList<>(). Declare by the interface, instantiate the implementation, and ask in your signatures for the most general type that serves you. With that, changing implementation costs one word and your methods accept sources you had not even foreseen.

You have the master table of the ten implementations you will use for the rest of your career, with their order, their duplicates, their nulls and their complexities, and the four default answers memorised: ArrayList, HashSet, HashMap, ArrayDeque. And you have the decision tree for reaching the right choice in five questions.

You understand generics as a user: <...> is the type of what is inside, it gives compile-time safety, removes casts and forces Integer instead of int at a memory cost worth knowing —the theory arrives in 10-01—. You know that the for-each is syntactic sugar: over arrays it translates into a for with an index, and over collections into an Iterator with hasNext/next. And you understand ConcurrentModificationException thoroughly: the modCount, the fail-fast policy, why it is a virtue, why sometimes it does not fire and fails worse, and the four solutions with the criterion for choosing between them, starting with removeIf.

You have mastered Collection's common vocabulary —add with its revealing boolean, remove and contains leaning on equals, addAll, retainAll, forEach, removeIf, toArray(new T[0])— and the immutable collections, with the precise difference between List.of, Collections.unmodifiableList (a view) and List.copyOf (a copy), plus the tip that eliminates a whole family of failures: never return null where a collection is expected.

And BiblioTech can already feel it. The Catalog has lost the counter, the capacity, the copyOf, the arraycopy and the manual nulls, and it has gained something it did not have before: a Set<String> that guarantees in constant time that there are no repeated ISBNs. One obvious weakness remains: searching by reference still walks the whole list.

In the next lesson, ArrayList, you will go into the implementation you will use more than any other. You will see how it works inside —the internal array, the difference between capacity and size, resizing and why adding is still "amortised" O(1) even though it sometimes copies a million elements—, its complete API with the classic trap of remove(int) versus remove(Object) on a List<Integer>, the conversions between array and list with the traps of each, and the definitive refactoring of BiblioTech's catalogue, with the before and after of a real method.