Lists and Sets in the Java Collection Framework

The Java Collection Framework divides generic data structures into collections, represented by Collection<T>, and maps, represented by Map<T,S>.

Programming

Why Programs Need Groups of Objects

Most programs eventually have to deal with many objects at once. A program might hold a list of students in a course, the set of distinct words in a document, or a lookup table that connects a name to a phone number. Writing a separate variable for each of these items would not scale. The Java Collection Framework is the part of Java's standard library that provides ready-made, generic data structures for holding and manipulating groups of objects.

A useful way to start is to ask one question about any group you want to store: does the group behave like a sequence of positions, or like a bag of distinct things? The answer determines which part of the framework you reach for. Keep that question in mind, because the rest of this article is organized around it.

What do you think happens?

You add the same value to a set twice. How many copies of that value does the set hold?

Two copies
One copy
It depends on the value

Reveal answer

Answer:

One copy

A set is a collection in which no object can occur more than once. The second add does not create another copy, so the set still holds exactly one instance of that value. A list has no such rule, which is the central difference this article builds toward.

Collections and Maps Answer Different Questions

The generic data structures in the framework fall into two families. The first family is the collection, which is simply a group of objects. The second family is the map, which pairs objects from one set with objects from another set. A map works like a dictionary that pairs each word with its definition, or like a phone book that pairs each name with a number. Its job is to answer the question of what one thing corresponds to, rather than to hold a plain group.

In Java, these two families are described by two parameterized interfaces. Collection<T> represents collections, and Map<T,S> represents maps. The letter T stands for a type parameter that can be any non-primitive type, so Collection<String> is a collection of strings and Collection<Integer> is a collection of Integer objects. Map takes two type parameters, which is one reason it is treated separately. This article concentrates only on collections; maps are left for their own treatment.

Which types belong under Collection<T>, which belong under Map<T,S>, and why a Map is not itself a Collection?

The diagram shows why a Map is not itself a Collection. A map is organized around pairing, so its job is to answer what one thing corresponds to. A collection is organized around holding a group. The two are siblings under the broader framework, not one nested inside the other.

Lists Versus Sets

A collection is not a single kind of thing. The framework recognizes two main kinds. A list is a collection whose objects sit in a linear sequence, so it has a first item, a second item, and so on, with every item except the last having an item that directly follows it. A set is a collection built around one rule: no object can appear in it more than once. The elements of a set are not thought of as having any particular order.

These two ideas are represented by the parameterized interfaces List<T> and Set<T>. Both are subinterfaces of Collection<T>. The practical consequence is that any object that implements List<T> or Set<T> automatically implements Collection<T> as well. Collection<T> holds the operations every collection shares, while List<T> and Set<T> each add the operations that suit their own kind of group.

If the same values are added in the same order, which structure keeps every copy and its position, and which keeps only one copy with no positional meaning?

Operations Every Collection Shares

Because a collection can be a list, a set, or something else built on Collection<T>, the operations defined by the interface have to be general. They apply to a collection of any type of object. Suppose coll is an object that implements Collection<T> for some specific non-primitive type T. The interface makes the operations below available for coll. Read them as a family of questions you can ask of a group, and as a family of actions you can take on it.

Family	Operations	What it does
Inspecting	size, isEmpty, contains	Asks how many objects are held, whether there are none, and whether a given object is present
Changing	clear, add, remove	Empties the collection, adds an object, or removes an object
Combining	containsAll, addAll, removeAll, retainAll	Works with another collection as a whole
Exporting	toArray	Copies the contents into an array; toArray() returns Object[] rather than T[]

The general operations of Collection<T>, grouped into the four families named in the source

Tracing a Sequence of Calls

The clearest way to understand these operations is to follow a short sequence of calls and watch the contents change. The diagram below runs the same calls on two collections that start empty: one is a list and one is a set. Each step shows the contents after the call. Notice where the two tracks diverge.

After each call in the sequence add ant, add bee, add ant, remove bee, clear, what does each collection contain?

Worked example

Predicting the Contents After Each Call

Starting from an empty list and an empty set, the same calls are made in this order: add ant, add bee, add ant, then contains bee, remove bee, size, and clear. What does each collection hold after the sequence of changes, and what does size report at the checkpoint?

1
Add ant to both
The list becomes [ant]. The set becomes {ant}, since it had no copy of ant yet.
2
Add bee to both
The list becomes [ant, bee]. The set becomes {ant, bee}. Neither collection already contained bee.
3
Add ant a second time
The list keeps a second copy and becomes [ant, bee, ant]. The set already has ant, and no object can occur more than once, so the set stays {ant, bee}.
4
Check size and contains
size reports 3 for the list and 2 for the set. contains bee answers yes for both, since bee is present in each.
5
Remove bee
Each collection had exactly one bee, so removing it leaves the list as [ant, ant] and the set as {ant}.
6
Clear
clear empties both collections, so each one now holds nothing and isEmpty would answer yes.

Result

After the first three additions the list holds three objects and the set holds two. After the removal the list holds two copies of ant and the set holds one. After clear, both are empty. The duplicate add is the only call whose effect differs in an important way between the two structures.

Mistakes With Lists and Sets

The mistakes below come up when learners treat every group the same way. Each one comes from forgetting a property that the interfaces define.

Common mistake
Expecting a set to keep a repeated value
What it looks like
Adding ant twice to a set and expecting size to count two.
Why it fails
A set is a collection in which no object can occur more than once.
Do this instead
Use a list if repeats matter, and remember that adding a duplicate to a set leaves its contents unchanged.
Common mistake
Using position on a set
What it looks like
Trying to read the second element of a set as if it were a list item.
Why it fails
The elements of a set are not thought of as having any particular order.
Do this instead
Use a list when position is meaningful, and treat a set as a membership test.
Common mistake
Thinking a Map is a kind of Collection
What it looks like
Passing a phone book style pairing to an operation written for groups of objects.
Why it fails
Collection<T> and Map<T,S> are separate families. A map pairs objects, while a collection holds a group.
Do this instead
Decide first whether you need a group or a correspondence, then pick the matching family.
Common mistake
Assuming every Collection<T> operation exists for a specific list or set type without checking the interface

Practice: Predict the Collection

EASY

Starting from an empty list and an empty set, the calls are: add cat, add dog, add cat, size, contains dog, remove dog, size. Before reading the answer, write down the contents of the list and the set after each call, and the value that size reports at each size check.

Hints

For the list, every add appends one more object, including a second cat.
For the set, the second add of cat does not create another copy.
A remove of dog takes the single dog out of each collection.

Your attempt (not saved)

Key Takeaways

A collection holds a group of objects, while a map pairs objects from one set with objects from another; Collection<T> and Map<T,S> are separate families.
A list is an ordered linear sequence whose items can repeat, and a set is a collection in which no object occurs more than once and whose elements have no particular order.
List<T> and Set<T> are subinterfaces of Collection<T>, so every list or set also provides the general operations: inspecting, changing, combining, and exporting to an array.
When tracing calls on a list and a set, the duplicate add is the key difference: the list keeps the extra copy while the set's contents stay the same.