The Collections Framework

You have kept groups of values in an ArrayList for a while now. A list suits a playlist or a row of scores, but other jobs come with other rules. A guest list should never name the same person twice. A phone book finds a number by a name. At a shop counter, whoever arrived first is served first. Java's library has a ready-made container for each of these jobs, and together they are called the Collections Framework. This lesson shows you the family: what each kind promises, which class to pick, and how to walk through any of them without tripping over your own changes.

A family of containers#

Picture the software behind a small café. It has to remember four different things:

• The orders taken today, in the order they came in. Two customers can both ask for a latte, so a drink may appear twice.
• The different drinks sold today, each one named once.
• Each regular customer's usual drink, found by the customer's name.
• The customers waiting at the counter, served in the order they arrived.

You could keep all four in ArrayLists, but then you would enforce every rule by hand: check for a repeat before each add, search the list for a name, remember to always take from the front. Java has a container type for each rule, with the rule built in.

A collection is an object that holds a group of other objects, called its elements. The Collections Framework is the set of interfaces and classes in java.util for working with them. Each interface is a promise about how the elements behave, and one or more classes keep each promise. It is the split you know from interfaces: List is the promise, and ArrayList is one class that keeps it. This is the family:

Read it from the top. Iterableis the smallest promise: “you can walk through me, one element at a time”. Collection extends it with the methods every group of elements has, such as add, remove, contains and size. List, Set and Queue each extend Collection with one more rule, and Deque extends Queue. When one interface builds on another, Java writes extends and the diagram draws a solid line. The dashed lines go from a class to the interface it implements.

Map stands apart. A map holds pairs, a key and a value, so its basic operation takes two things, put(key, value), where Collection's add takes one. Map is still part of the framework, but it does not extend Collection.

Key idea

Each collection interface is a promise about its elements: a List keeps positions, a Set refuses repeats, a Queue hands out from the front, and a Map finds a value by its key.

Four kinds, side by side#

Each kind is easiest to understand by watching it work. Here are the café's four jobs as four short programs. Step through them and keep an eye on the memory view under the code, which draws each kind of collection in its own way.

A List keeps order and repeats#

It prints [latte, tea, latte, mocha], then Second order: tea and Orders taken: 4. Both lattes stay, in the order they were added, and get(1) reaches the second order by its position. This is the ArrayList you already know. The only new thing is the type on the left, List, which the next section explains.

A Set drops repeats#

It prints [tea, mocha, latte], Second latte added? false, Different drinks: 3 and Sold any tea? true. The second add("latte") changed nothing and returned false, because a set holds each element at most once. A set has no positions either, so there is no get(1). You ask a set whether it contains something.

Look at the order. The set printed tea, mocha, latte, which is neither the order the drinks were added nor alphabetical. A HashSet files each element into one of a row of numbered buckets, picked by a number worked out from the element itself, and it prints and walks them bucket by bucket. The narration and the memory view show the buckets as you step; HashMap and HashSet explains how a bucket is picked. For now, keep the rule: a HashSet makes no promise about order. When you need one, LinkedHashSet keeps the order in which elements were first added, and TreeSet keeps them sorted.

A Map pairs keys with values#

A map stores entries: pairs of a key and a value. The two types in the angle brackets are the key type and then the value type, so Map<String, String> maps a customer's name to a drink. put(key, value) stores an entry and get(key) finds the value again.

It prints {Asha=mocha, Ben=tea, Chen=tea}, then Ben usually has tea, Dev usually has null and Regulars: 3. Ben and Chen both drink tea, so values may repeat. Keys may not: the second put for Asha replaced latte with mocha, and the map still holds three entries. Asking for a key that is not there, such as Dev, gives null.

It prints 2 2. The third put found the key latte already in the map and replaced its value, 5, with 2. A map never holds two entries with the same key, so the size stays at 2.

A Queue serves the oldest first#

It prints Waiting: [Asha, Ben, Chen], Next up: Asha, Serving Asha, Serving Ben and Waiting: [Chen, Dev]. offer adds an element at the back of the queue, peek looks at the front one without taking it, and poll takes the front one out and returns it. Asha arrived first, so she was served first. That rule is called first in, first out, or FIFO. On an empty queue, peek and poll return null instead of stopping the program.

ArrayDeque is the everyday class for a queue. A Deque(said “deck”, short for double-ended queue) lets you add and take at both ends, which also makes it a good stack, where the newest element comes out first. A PriorityQueue is a queue that always hands out its smallest element first. Both get a full lesson in stacks, queues and deques.

Declare the interface, create the class#

All four programs gave the variable an interface type and created the object from a class: List<String> orders = new ArrayList<>();. You met this habit in designing classes well, where it was called programming to an interface, and it is the usual way to declare a collection in Java. Read the line in two halves. The left side is the promise the rest of the program relies on: orders is some kind of list. The right side picks the class that keeps the promise.

The split pays off in two ways. Switching to another class touches one word: change new ArrayList to new LinkedList and every other line still compiles, because the rest of the program only ever asked for a List. And a method can accept any collection that keeps the promise it needs. This method asks only for a Collection, so it takes a list, a set and a queue:

It prints orders: 3 items [latte, tea, latte], drinks: 2 items [tea, latte] and line: 2 items [Asha, Ben]. One method served three kinds of collection. The set came from new HashSet<>(orders), which copies every element of the list and drops the repeat. The general-purpose collection classes all have a constructor like this, which copies the elements of any other collection.

The price is the rule you learned in polymorphism: the declared type decides which methods you may call. A Collection has no positions, so it has no get, even when the object behind it is an ArrayList:

So pick the most general interface that still has every method your code calls. A variable you read by position needs List. A method that only counts, checks, adds or loops can take a Collection, and then it works for every kind.

Key idea

Give a collection variable or parameter an interface type, and create the object from a class. Choose the most general interface that still has every method you call.

What every collection can do#

List, Set and Queue all extend Collection, so they share its methods. Learn these once and they work on all three.

• The first line prints true false. orders.add("tea") returns true, because a list always takes another element. drinks.add("tea") returns false, because the set already had tea.
• addAll adds a whole collection. The list grows to six orders, [latte, tea, latte, tea, mocha, cocoa], while the set takes in only the two drinks it did not have and prints [tea, mocha, cocoa, latte].
• removeIf drops both lattes from the list in one call, leaving [tea, tea, mocha, cocoa], and remove takes cocoa out of the set, leaving three drinks.
• The last two lines count the teas with a stream and print 2 teas. Counting leaves the list as it was.

1import java.util.HashSet;
2import java.util.List;
3import java.util.Set;
4 
5public class Main {
6    public static void main(String[] args) {
7        List<String> orders = List.of("tea", "mocha", "latte", "cocoa", "mocha", "tea");
8        Set<String> seen = new HashSet<>();
9        String firstRepeat = "none";
10 
11        // TODO: find the first order that repeats an earlier one
12 
13        System.out.println("First repeat: " + firstRepeat);
14    }
15}

Walking through any collection#

The for-each loop you used on arrays and lists works on every collection. That is the promise Iterable makes at the top of the family tree: a for-each loop can walk any object that is Iterable. Here it walks a set and a queue:

The set is walked in its own order, tea, mocha, latte, the same order it prints in. The queue is walked from front to back, and walking takes nothing out: the last line prints 2 still waiting. Only poll takes elements out of a queue.

The iterator behind the loop#

A for-each loop runs on an iterator, an object whose only job is to walk a collection one element at a time. Every collection hands one out from its iterator() method, and an iterator has three methods:

• hasNext() answers whether there is another element to visit.
• next() hands out the next element and moves past it.
• remove() removes the element that next() handed out last.

The Java Language Specification defines the for-each loop by turning it into iterator code. The first loop below runs exactly as if you had written the second:

You write the iterator out yourself when the loop needs it, usually to remove elements as it goes. The milk has run out, so every latte order must be cancelled:

It prints [tea, mocha]. Each pass asks hasNext(), takes the next order with next(), and calls it.remove() on each latte. Step through it and watch the list in the memory view: each latte disappears, the later orders shift left, and the loop still visits every order. Iterator lives in java.util, so it needs an import, and its type parameter matches the collection's: an iterator over strings is an Iterator<String>.

Walking a map#

A Map is not Iterable, so for (String name : usual) does not compile: javac stops with for-each not applicable to expression type. Instead, a map offers three views of itself, and each view is a collection you can walk: keySet() holds the keys, values() the values, and entrySet() the entries. Walking the entries gives you both halves of each pair:

It prints Asha has latte, Ben has tea and Chen has tea. Each entry is a Map.Entry<String, String>, and getKey() and getValue() read its two halves. The regulars come out as Asha, Ben, Chen here, but a HashMap promises no order, the same as a HashSet. The views read the map itself, so removing something from a view removes it from the map. HashMap and HashSet walks all three views and puts that to use.

Changing a collection while you walk it#

In the ArrayList lesson you saw this crash: removing from a list inside a for-each loop stopped the program with a ConcurrentModificationException. Now that you know a for-each loop runs on an iterator, you can see exactly where the exception comes from, and why it sometimes does not come at all. Here the café cancels the tea order while it checks the orders:

It prints Checking latte and Checking tea, removes tea, and then stops with the exception on the for line, at the moment the loop asks for the next order.

Two numbers inside the iterator#

An ArrayList counts the changes made to it. Every add or removeadds one to a counter that the JDK's source code calls modCount, and so do a few other changes, such as clear and sort. When the list hands out an iterator, the iterator keeps two numbers of its own:

• a cursor, the position of the next element it will hand out, starting at 0;
• a copy of the list's change count, taken when the iterator was made.

Its two methods use them like this:

• hasNext() compares the cursor with the size. If they differ, it answers true. It never looks at the change count.
• next() first compares the list's change count with its copy. If they differ, the list was changed behind the iterator's back, and it throws ConcurrentModificationException. If they match, it hands out the element at the cursor and moves the cursor on by one.

Here is the café program again, number by number:

The name sounds like threads, but nothing here runs at the same time. “Concurrent modification” means the list was modified while a walk over it was in progress, and the documentation of the exception says that a single thread can cause it in exactly this way.

When the alarm stays quiet#

hasNext() never checks the count, and that gap explains the odd case from the ArrayList lesson. Predict this one, where the loop removes mocha, the second-to-last order.

It prints three Checking lines and [latte, tea, cocoa], with no exception. After mocha is removed, the size is 3 and the cursor is 3. hasNext() sees two equal numbers and answers false, so the loop ends before next() can notice the changed count. Cocoa is never checked. Had cocoa needed cancelling too, it would still be on the list, and nothing would tell you.

Try all of these in the lab below. Each press of Next pass runs hasNext() and next() once, and the two remove buttons are the two ways the loop body could remove the current order. Start from Reset each time, remove tea, then mocha, then cocoa, and watch the cursor and the two counts.

The exception works like a smoke alarm for a bug. It goes off in most cases, but the documentation promises only a best effort, which is why the quiet case exists. So never let a program depend on the exception. Write the loop so the problem cannot happen.

Removing safely#

There are three safe ways to change a collection that you are walking:

• Remove through the iterator, as in SoldOut.java. it.remove() moves the cursor back one place and copies the new count, so the iterator and the list stay in step. In the lab, it.remove() never leads to an exception.
• Call removeIf. It walks and removes in one call, and every collection has it: lists, sets, queues and the views of a map.
• Collect first, change afterwards. Walk the collection, put what you want to remove or add in a second list, and call removeAll or addAll once the loop has finished. This is the way to add, because adding inside a for-each loop trips the same check as removing.

Two customers got tired of waiting and left the line. removeIf takes them out of the queue without a loop of your own:

It prints [Asha, Chen] and Next up: Asha. Ben and Dev are gone, and everyone else keeps their place in the line. The set gaveUp is only asked contains, which is why it can come from Set.of.

Key idea

Never change the size of a collection inside a for-each loop over it. Remove through the iterator, call removeIf, or collect the changes and make them after the loop.

1import java.util.ArrayList;
2import java.util.Iterator;
3import java.util.List;
4import java.util.Set;
5 
6public class Main {
7    public static void main(String[] args) {
8        List<String> orders = new ArrayList<>(List.of("latte", "tea", "cocoa", "mocha", "latte", "tea"));
9        Set<String> soldOut = Set.of("latte", "cocoa");
10 
11        // TODO: remove every order for a sold-out drink
12 
13        System.out.println(orders);
14    }
15}

Collections that cannot change#

List.of from the ArrayList lesson builds a list that nobody can change. Set and Map have the same kind of method: Set.of and Map.of arrived together with List.of in Java 9. Map.of takes keys and values in turns: key, value, key, value.

It prints [small, medium, large], true 3 and 350, then stops on the last line with an UnsupportedOperationException. All three collections are unmodifiable: every method that would change them, such as add, put, remove or clear, throws that exception, while reading works as usual. They also refuse null as an element, a key or a value, with a NullPointerException the moment you create them.

A copy or a view?#

Sometimes you want to let other code read a list that you are still changing. Java has two ways to hand it over, and they behave differently. Think of the café's specials. The chalkboard by the door shows the specials as they are right now. A printed flyer shows them as they were when it was printed.

It prints board: [soup, pie, cake] and flyer: [soup, pie]. Notice the s in Collections: it is a class full of static helper methods, not the Collection interface.

Set.copyOf and Map.copyOf copy sets and maps in the same way, and Collections.unmodifiableSet and Collections.unmodifiableMap make views of them.

Key idea

List.of, Set.of, Map.of and copyOf build collections that nobody can change. Collections.unmodifiableList builds a read-only window onto a list that its owner can still change.

First, last and reversed#

Some collections keep their elements in a definite order: a list, a deque, a LinkedHashSet (the order of adding) and a TreeSet (sorted order). Until Java 21, each of them reached its ends in its own way. The last element of a list was orders.get(orders.size() - 1), a deque had getLast(), a TreeSet had last(), and a LinkedHashSet had no direct way at all: you walked the whole set to reach its last element.

Java 21 gave all of them one set of names through a new interface, SequencedCollection, which sits between Collection and List or Deque. Its methods are getFirst, getLast, addFirst, addLast, removeFirst, removeLast and reversed.

It prints First: latte and Last: mocha. addFirst puts espresso at the front and removeLast takes mocha off the end, leaving [espresso, latte, tea], and reversed() gives the list back to front: [tea, latte, espresso]. The deque answers to the same names with blue green and [green, red, blue]. On an empty list, getFirst() throws a NoSuchElementException, where get(0) would throw an IndexOutOfBoundsException.

A LinkedHashSet implements SequencedSet, the set version. On a set, addFirst and addLast never create a repeat: they move an element that is already there to that end. The variable has to be declared as a SequencedSet (or a LinkedHashSet), since a plain Set has no getFirst.

addLast("latte") moved latte from the front to the end instead of adding a second one. reversed() does not copy anything, either. It returns a view of the same collection in the opposite order, so a change to the original shows up in it:

Step through it. In the step where mocha joins orders, the memory view shows it at the front of newestFirst as well, because there is only one list underneath.

A HashSet has no order to speak of, so it is not a sequenced collection, and getFirst() on one stops javac with cannot find symbol. Maps with an order, LinkedHashMap and TreeMap, got the same treatment through SequencedMap, with methods such as firstEntry(), lastEntry() and reversed().

Choosing a collection#

Choosing comes down to a few questions about the job. Do you find things by a key? May an item appear twice? Which item do you want back next, and does the order matter when you walk them? Answer those, pick the interface, then pick the class.

When you are not sure, start with ArrayList, HashSet or HashMap, declared as List, Set or Map. Because the rest of your code uses only the interface, switching to a LinkedHashSet or a TreeMap later changes a single word.

The picker asks the same questions one at a time. Try it with the jobs in the table, or with something from a program you use every day.

Further reading#

• The Collection interface in the Java SE 25 API documentation
• ConcurrentModificationException in the Java SE 25 API documentation
• JEP 431: Sequenced Collections, the proposal behind getFirst, getLast and reversed
• Getting to know the collection hierarchy, on dev.java