Creating Sequenced Collections, Sets, and Maps
Three interfaces introduced in JDK 21 represent collections with a defined encounter order. Each collection has a well-defined first element, second element, and so forth, up to the last element. They provide uniform APIs for accessing their first and last elements, and processing their elements in forward and reverse order.
Prior to JDK 21, the Java Collections Framework lacked a collection type that represented a sequence of elements with a defined encounter order. For example, List and Deque defined an encounter order but their common supertype, Collection, did not. Similarly, Set and subtypes such as HashSet do not define an encounter order, while subtypes such as SortedSet and LinkedHashSet do. Given the lack of a collection type with a defined encounter order, there is no uniform set of operations that respect encounter order. While there are operations that respect encounter order, they're not uniform.
An example of where a common order-significant operation is missing in the Collections
Framework is to get the first element of a Deque and of a
List. To get the first element of a Deque, you
use the getFirst()
method. However, to get the first element of a
List, you use get(0)
.
Support for encounter order was spread across the type hierarchy, making it
difficult to express certain useful concepts in APIs. Neither Collection nor List could describe a
parameter or return value that had an encounter order. Collection was too general, relegating such constraints to the
specification, and possibly leading to hard-to-debug errors. If an API wanted to receive
a collection with a defined encounter order, then using List
was too
specific, because it excluded SortedSet
and
LinkedHashSet
. A related problem was that view collections were
often forced to downgrade to weaker semantics. For example, wrapping a LinkedHashSet with
Collections::unmodifiableSet
yields a Set that discards the information about encounter order.
Without interfaces to define them, operations related to encounter order were either inconsistent or missing. Many implementations support getting the first or last element, but each collection defines its own approach, and some are not obvious or are missing entirely.
Retrofitting the Collections Framework with Sequenced Interfaces
Figure 5-1 Collections Framework with Sequenced Interfaces

Description of "Figure 5-1 Collections Framework with Sequenced Interfaces"
- List has SequencedCollection as its immediate superinterface.
- Deque has SequencedCollection as its immediate superinterface.
- LinkedHashSet implements SequencedSet.
- SortedSet has SequencedSet as its immediate superinterface.
- LinkedHashMap implements SequencedMap.
- SortedMap has SequencedMap as its immediate superinterface.
- Covariant overrides for the
reversed()
method are defined in the appropriate places. For example,List::reversed
is overridden to return a value of typeList
rather than a value of type SequencedCollection. - Methods added to the Collections utility class create unmodifiable wrappers for
three new types:
Collections.unmodifiableSequencedCollection(sequencedCollection)
Collections.unmodifiableSequencedSet(sequencedSet)
Collections.unmodifiableSequencedMap(sequencedMap)
See JEP 431 for background information about the interfaces for sequenced collections, sequenced sets, and sequenced maps.
SequencedCollection
A SequencedCollection is a collection type added in JDK 21 that represents a sequence of elements with a defined encounter order.
A SequencedCollection has first and last elements with the elements between them having successors and predecessors. A SequencedCollection supports common operations at either end, and it supports processing the elements from first to last and from last to first (such as, forward and reverse).
interface SequencedCollection<E> extends Collection<E> {
SequencedCollection<E> reversed();
// methods promoted from Deque
void addFirst(E);
void addLast(E);
E getFirst();
E getLast();
E removeFirst();
E removeLast();
}
The reversed()
method provides a reverse-ordered view of the
original collection. Any modifications to the original collection are visible in the
view.
The encounter order of elements in the returned view is the inverse of the encounter order of elements in this collection. The reverse ordering affects all order-sensitive operations, including those on the view collections of the returned view.
- Enhanced
for
loops - Explicit
iterator()
loops forEach()
stream()
parallelStream()
toArray()
LinkedHashSet
was previously
quite difficult; now it is
simply:linkedHashSet.reversed().stream()
Note:
Thereversed()
method is essentially a renamed NavigableSet::descendingSet
,
promoted to SequencedCollection.
void addFirst(E)
void addLast(E)
E getFirst()
E getLast()
E removeFirst()
E removeLast()
Theadd*(E)
andremove*()
methods are optional, primarily to support the case of unmodifiable collections. Theget*()
andremove*()
methods throw aNoSuchElementException
if the collection is empty. There are no definitions ofequals()
andhashCode()
in SequencedCollection because its subinterfaces have conflicting definitions.
SequencedSet
A SequencedSet is both a SequencedCollection and a Set.
A SequencedSet can be thought of either as a Set that also has a well-defined encounter order, or as a SequencedCollection that also has unique elements.
interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
SequencedSet<E> reversed(); // covariant override
}
This interface has the same requirements on the equals
and
hashCode
methods as defined by Set.equals
and
Set.hashCode
. A Set and a SequencedSet compare equals
if and only if
they have equal elements, irrespective of ordering.
SequencedSet
defines the reversed()
method, which
provides a reverse-ordered view of this set. The only difference from the
SequencedCollection.reversed
method is that the return type of
SequencedSet.reversed
is SequencedSet
.
add*(E)
methods of the
SequencedCollection perform the following:
addFirst(E)
- Adds an element as the first element of the collection.addLast(E)
- Adds an element as the last element of the collection.
The add*(E)
methods of the SequencedCollection also
have the following special-case behaviors for LinkedHashSet and
SortedSet.
Special-case behaviors for LinkedHashSet:
- The
addFirst(E)
andaddLast(E)
methods have special-case semantics for collections such as LinkedHashSet. LinkedHashSet repositions the entry if it is already present in the set. If the element is already present in the set then it is moved to the appropriate position. This remedies a long-standing deficiency in LinkedHashSet, namely the inability to reposition elements.
Special-case behaviors for SortedSet:
- Collections such as SortedSet, which
position elements by relative comparison, cannot support explicit-positioning
operations such as the
addFirst(E)
andaddLast(E)
methods declared in the SequencedCollection superinterface. These methods throw anUnsupportedOperationException
.
SequencedMap
A SequencedMap provides methods to add mappings, to
retrieve mappings, and to remove mappings at either end of the map's encounter order. This
interface also defines the reversed() method
, which provides a
reverse-ordered view of this map.
A SequencedMap has a well-defined encounter order that supports
operations at both ends and is reversible. A map's reverse-ordered view is generally not
serializable, even if the original map is serializable. The encounter order of a
SequencedMap is similar to that of the elements of a
SequencedCollection
, but the ordering applies to mappings instead
of individual elements:
interface SequencedMap<K,V> extends Map<K,V> {
SequencedMap<K,V> reversed();
SequencedSet<K> sequencedKeySet();
SequencedCollection<V> sequencedValues();
SequencedSet<Entry<K,V>> sequencedEntrySet();
V putFirst(K, V);
V putLast(K, V);
// methods promoted from NavigableMap
Entry<K, V> firstEntry();
Entry<K, V> lastEntry();
Entry<K, V> pollFirstEntry();
Entry<K, V> pollLastEntry();
}
The sequencedKeySet(), sequencedValues(), and sequencedEntrySet()methods are exactly analogous to the keySet(), values(), and entrySet() methods of Map interface. All of these methods return views of the underlying collection; where modifications to the view are visible in the underlying collection and vice versa. The encounter order of these views exactly corresponds to the encounter order of the underlying map.
- In
SequencedSet<K> sequencedKeySet()
, the implemention returns aSequencedSet
view of the map'skeySet
and behaves as follows:- add and addAll methods throw
UnsupportedOperationException
. reversed
method returns thesequencedKeySet
view of the reversed view of the map.- Its other methods call the corresponding methods of the
keySet
view of the map.
- add and addAll methods throw
- In
SequencedCollection<V> sequencedValues()
, the implemention returns aSequencedCollection
view of the map'svalues
collection and behaves as follows:add
andaddAll
methods throwUnsupportedOperationException
.reversed
method returns thesequencedValues
view of the reversed view of the map.equals
andhashCode
methods are inherited from Object.- Its other methods call the corresponding methods of the
values
view of the map.
- In
SequencedSet<Entry<K,V>> sequencedEntrySet()
, the implemention returns aSequencedSet
view of the map's entrySetand behaves as follows:add
andaddAll
methods throwUnsupportedOperationException
.reversed
method returns thesequencedEntrySet
view of the reversed view of the map.- Its other methods call the corresponding methods of the
entrySet
view of the map.
put*(K, V)
methods have special-case semantics, similar
to the corresponding add*(E)
methods of SequencedSet:
- For maps such as LinkedHashMap, they have the additional effect of repositioning the entry if it is already present in the map.
- For maps such as SortedMap, these
methods throw
UnsupportedOperationException
.
Entry<K, V> firstEntry()
Entry<K, V> lastEntry()
Entry<K, V> pollFirstEntry()
Entry<K, V> pollLastEntry()
The methods firstEntry()
, lastEntry()
, pollFirstEntry()
, and pollLastEntry()
return Map.Entry
instances that
represent snapshots of mappings as of the time of the call. They do not support
mutation of the underlying map via the optional setValue
method.
Demonstrating ArrayList and LinkedHashMap Reversed Views
Several scenarios are provided of using the sequenced interfaces in the Collections Framework.
Topics
Demonstrating a Reverse-Ordered View of a Collection
The following example demonstrates how the reversed()
method of the sequenced interfaces produces a reverse-ordered view of a collection, how
modifications to a reversed view affect the original collection, and how modifications to
the original collection are visible in the reversed view.
The reversed view is "live" and not a snapshot of a collection. This
characteristic is illustrated in the following examples by using an
ArrayList
and its reversed view.
Note:
Unessentialjshell
output is not included in the following example
code.
Start a jshell
session and use the ArrayList
class to
create a list of String
objects.
jshell> var list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"))
list ==> [a, b, c, d, e]
Next, use the reversed()
method to produce a reverse-ordered view of the
collection.
jshell> var rev = list.reversed()
rev ==> [e, d, c, b, a]
When you modify the reversed view, it affects the original collection. Add
f
as an entry to the reverse-ordered view and then verify that it
is added to the original collection.
jshell> rev.add(1, "f")
jshell> rev
rev ==> [e, f, d, c, b, a]
jshell> list
list ==> [a, b, c, d, f, e]
When you modify the original collection, your modifications are visible in
the reversed view. Set the element at index 2 to X
, verify it is added
to the collection, and then produce a reverse-ordered view of the modified
collection.
jshell> list.set(2, "X")
jshell> list
list ==> [a, b, X, d, f, e]
jshell> rev
rev ==> [e, f, d, X, b, a]
Demonstrating Composition of LinkedHashMap Views
In addition to using ArrayList
, a
reversed()
view can also be composed of other views such as
List.subList().reversed()
or
SequencedMap.sequencedKeySet().reversed()
and
SequencedMap.reversed().sequencedKeySet()
.
The SequencedMap.sequencedKeySet().reversed()
and
SequencedMap.reversed().sequencedKeySet()
views are functionally
equivalent and are illustrated by using the LinkedHashMap
class in the
following example code.
Start a jshell
session and use the LinkedHashMap
class
to create a map
of String
objects.
jshell> var map = new LinkedHashMap<String, Integer>()
jshell> map.put("a", 1)
jshell> map.put("b", 2)
jshell> map.put("c", 3)
jshell> map.put("d", 4)
jshell> map.put("e", 5)
map ==> {a=1, b=2, c=3, d=4, e=5}
Next, use the reversed()
method to produce a
reverse-ordered view of the keySet
view of the original collection.
jshell> map.sequencedKeySet().reversed()
$17 ==> [e, d, c, b, a]
Demonstrating SequencedMap Does Not Support Mutation of the Underlying Map
This demonstration illustrates the final statement in the
SequencedMap
section that firstEntry()
,
lastEntry()
, pollFirstEntry()
, and
pollLastEntry()
methods do not support mutation of the underlying map
through use of the optional setValue
method.
Attempting to change an entry in the underlying map by using
setValue()
with these methods will throw an
UnsupportedOperationException
. This is in contrast to changing a
map entry obtained by iterating the entrySet
. If you call
seqmap.entrySet().iterator().next()
to return a map entry and then
call setValue()
on the entry, it will modify the original map.
Open a jshell
session and use the map produced in Demonstrating Composition of LinkedHashMap Views.
Call map.entrySet().iterator().next()
to return the first
map entry.
jshell> var entry = map.entrySet().iterator().next()
entry ==> a=1
Use setValue()
to change the value of the map entry to
77
. The entry was obtained by iterating the
entrySet
so it can be modified in the original
map
. Verify that the value in map
changed to
77
.
jshell> entry.setValue(77)
$19 ==> 1
jshell> map
map ==> {a=77, b=2, c=3, d=4, e=5}
Note:
The ability to callsetValue()
on the entry returned by the iterator is not a new
behavior introduced in JDK 21.
Use setValue()
to try and change the map entry to
999
. Because the map entry was not obtained by iterating with
entrySet
, it throws an
UnsupportedOperationException
.
jshell> entry = map.firstEntry()
entry ==> a=77
jshell> entry.setValue(999)
| Exception java.lang.UnsupportedOperationException: not supported
| at NullableKeyValueHolder.setValue (NullableKeyValueHolder.java:126)
| at (#22:1)