Chapter 4. The Main Interfaces of the Java Collections Framework

A collection is an object that provides access to a group of objects, allowing them to be processed in a uniform way. A collections framework provides a uniform view of a set of collection types specifying and implementing common data structures, following consistent design rules so that they can work together. Figure 4-1 shows the main interfaces of the Java Collections Framework, together with one other—Iterable—which is outside the Framework. Iterable (see “Iterable and Iterators”) defines the contract that a class—​any class, not only one of those in the Framework—​must implement in order to be used as the target for an “enhanced for statement”, usually called a foreach statement.

jgc 1001
Figure 4-1. The main interfaces of the Java Collections Framework

The Framework interfaces in Figure 4-1 have the following purposes:

Collection

Collection exposes the core functionality required of any collection other than a Map. Its methods support managing elements by adding or removing single or multiple elements, checking membership of a single or multiple values, and inspecting and exporting elements. It has no direct concrete implementations; the concrete collection classes all implement one of its subinterfaces as well.

Set

A Set is a collection in which order is not significant and contains no duplicates. It adds no operations to Collection, but the contracts for its element-adding operations specify that they will not create duplicates.

List

A List is a collection in which order is significant and which accommodates duplicate elements. It adds operations supporting indexed access.

Queue

A Queue is a collection whose additional operations accept elements at one end, its tail, for processing, and yield them up at the other end, its head, in the order in which they are to be processed.

Map

A Map is a collection which uses key-value associations to store and retrieve elements. The keys of a Map form a Set, so they follow the rule that there is no duplication and ordering is not significant. The operations of Map allow it to be maintained by addition and removal of single or multiple key-value associations, but these are ancillary to the main use of Maps, which is to find the values that correspond to given keys.

Using the Different Collection Types

A simple example, a word cloud generator, will illustrate the purpose of some of these types. Word cloud generators normally ignore the order of the words in their input, so any of the word clouds in Figure 4-2 could be produced from the Set created by

Set.of("Larry", "Curly", "Moe")
jgc 1003
Figure 4-2. Word clouds generated from Set data

Although the position of words in a cloud is randomly determined, their size depends on the number of repetitions of each in the input to the generator. So, since Sets cannot store duplicate elements, they are not actually a suitable data structure for representing the contents of a word cloud. For a collection type that does accommodates duplicates, we must turn to List. The word cloud generated by

List.of("Larry", "Larry", Curly", "Moe")

will be like one of those in Figure 4-3, reflecting the fact that the string "Larry" occurs twice as often as the other two. (Again, the random order of the words in Figure 4-3 is not because the order has been lost from the collection but because word cloud generators ignore the order of their input.)

jgc 1005
Figure 4-3. Word clouds generated from List data

Since any Set can be represented by a List--one without duplicates and whose order is ignored—​why have a separate data type at all? The reason is that the operations of Set make it much easier to guarantee element uniqueness, when that is what we actually want, and being able to disregard order can allow operations to be much more efficient.

In our word cloud example, a better representation of the input list would be a Map associating each word with its frequency:

Map.of("Larry", 2, "Curly", 1, "Moe", 1)

You can think of a Map as a table, one of those shown in Figure 4-4:

jgc 1004
Figure 4-4. Word cloud data represented as a Map

The three tables in Figure 4-4 represent the same Map, because the table rows—​that is, the key-value pairs that make up the Map--form a set, so that their order is not significant. Further, the keys also form a set, so there couldn’t be two rows with the same key, “Larry” say.

Sequenced Collections

In the word cloud example, the order of the elements wasn’t important. Often, though, the ordering of elements is significant, and many collections, for example List, do preserve it—​and, sometimes, impose it. Such collections are said to be sequenced. A sequenced collection is one with a defined order—​unlike Collection, Set or Map--that can also be iterated in either direction, unlike Queue. Sequenced collections differ in how their ordering is derived: for some, like List, elements retain the order in which they were added, whereas for others, like NavigableSet (see below), the ordering is dictated by the values of the elements. These are sometimes called externally ordered and internally ordered types, respectively, reflecting the difference between an order which is arbitrarily imposed on the elements, for example by the order in which they are added, and an order that is an inherent property of the elements themselves, for example by alphabetic ordering on strings.

A new interface, SequencedCollection, was introduced in Java ?? to unify the sequenced collections, of both kinds. Figure 4-5 adds the sequenced interfaces of the Framework to those of Figure 4-1.

jgc 1002
Figure 4-5. The sequenced interfaces of the Java Collections Framework

SequencedCollection

SequencedCollection provides a reversed view (see §11.6), together with the operations that all sequenced collections must support on the first and last elements of the collection: access, addition, and removal.

SequencedSet and NavigableSet

A SequencedSet is an externally or internally ordered Set that also exposes the methods of SequencedCollection. A NavigableSet is an internally ordered SequencedSet that therefore also automatically sorts its elements, and also provides additional methods to find elements adjacent to a target value.

Deque

A Deque is a double-ended queue that can both accept and yield up elements at either end.

SequencedMap and NavigableMap

A SequencedMap is a Map whose keys form a SequencedSet. A NavigableMap is a SequencedMap whose keys form a NavigableSet, so that its entries are automatically sorted by the key ordering, and its methods can find keys and key-value pairs adjacent to a target key value.

Chapters Chapter 6 through Chapter 11 will concentrate on each of the Collections Framework interfaces in turn. First, though, in Chapter 5, we need to cover some preliminary ideas which run through the entire Framework design.

Get Java Generics and Collections, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.