Sequenced Collections in Java

1. Overview

Java 21 introduced an update of Java’s collections framework called Sequenced Collections.

The Sequenced Collections proposal stands out as a game-changing enhancement that promises to redefine how developers interact with collections. This feature injects new interfaces into the existing hierarchy, offering a seamless mechanism to access the first and last elements of a collection using built-in default methods. Moreover, it provides support to obtain a reversed view of the collection.

In this article, we will explore this new enhancement, its potential risks, and the advantages it brings.

2. Motivation

The absence of a universal supertype for collections with a defined encounter order has been a repeated source of problems and complaints. Additionally, the lack of uniform methods for accessing first and last elements and iterating in reverse order has been a persistent limitation of Java’s collections framework.

We can take as an example List and Deque: both define an encounter order, but their common supertype, Collection, does not. Similarly, Set does not define an encounter order, but some subtypes, such as SortedSet and LinkedHashSet, do. Support for encounter order is thus spread across the type hierarchy, and operations related to encounter order are either inconsistent or missing.

In order to demonstrate the inconsistency, let’s make a comparison of accessing the first and last elements of different collection types:

The same thing happens when trying to get a reversed view of a collection. While iterating the elements of a collection from the first to the last element follows a clear and consistent pattern, doing so in the opposite direction presents challenges.

To illustrate, when dealing with a NavigableSet, we can use the descendingSet() method. For a Deque, the descendingIterator() method proves useful. Similarly, when dealing with a List, the listIterator() method works well. However, this is not the case for LinkedHashSet, as it doesn’t provide any support for reverse iteration.

All these differences led to fragmented codebases and complexity, making it challenging to express certain useful concepts in APIs.

3. The New Java Collection Hierarchy

This new feature introduces three new interfaces for sequenced collections, sequenced sets, and sequenced maps, which are added to the existing hierarchy of collections:

This image is part of the official documentation for JEP 431: Sequenced Collections (source).

3.1. SequencedCollection

A sequenced collection is a Collection whose elements have a defined encounter order. The new SequencedCollection interface provides methods to add, retrieve, or remove elements at both ends of the collection, along with a method to get a reverse-ordered view of the collection.

interface SequencedCollection<E> extends Collection<E> {

    // new method
    SequencedCollection<E> reversed();

    // methods promoted from Deque
    void addFirst(E);
    void addLast(E);

    E getFirst();
    E getLast();

    E removeFirst();
    E removeLast();
}

All methods, except reversed(), are default methods, provide a default implementation, and are promoted from Deque. The reversed() method provides a reversed-order view of the original collection. Also, any modifications to the original collection are visible in the reversed view.

The add*() and remove*() methods are optional and throw an UnsupportedOperationException in their default implementation, primarily to support the case of unmodifiable collections and collections with an already defined sorting order. The get*() and remove*() methods throw NoSuchElementException if the collection is empty.

3.2. SequencedSet

A sequenced set can be defined as a specialized Set which functions as a SequencedCollection, ensuring the absence of duplicate elements. The SequencedSet interface extends SequencedCollection and overrides its reversed() method. The only difference is that the return type of SequencedSet.reversed() is SequencedSet.

interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {

    // covariant override
    SequencedSet<E> reversed();
}

3.3. SequencedMap

A sequenced map is a Map whose entries have a defined encounter order. The SequencedMap does not extend SequencedCollection and provides its own methods to manipulate elements at either end of the collection.

interface SequencedMap<K, V> extends Map<K, V> {
    
    // new methods
    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();
}

Similar to SequencedCollection, put*() methods throw UnsupportedOperationException for unmodifiable maps or maps with an already defined sorting order. Also, calling one of the methods promoted from NavigableMap on an empty map leads to throwing a NoSuchElementException.

4. Risks

The introduction of the new interfaces is supposed not to affect code that simply uses collections implementations. However, there are several kinds of conflicts that may appear if custom collection types would be defined in our codebases:

• method naming: new methods introduced might clash with methods on existing classes. For example, if we have a custom implementation of the List interface that already defines a getFirst() method but with a different return type than getFirst() defined in SequencedCollection, it will create a source incompatibility when upgrading to Java 21.
• covariant overrides: both List and Deque provide covariant overrides of the reversed() method, one returning List and the other one returning Deque. Therefore, any custom collection that implements both interfaces will lead to a compile-time error when upgrading to Java 21 because the compiler can’t choose one over the other.

The report JDK-8266572 contains a full analysis of the incompatibility risk.

5. Conclusion

In conclusion, Sequenced Collections marks a significant leap forward for the Java Collections. By addressing the long-standing need for a unified way to handle collections with a defined encounter order, Java empowers developers to work more efficiently and intuitively. The new interfaces establish a clearer structure and consistent behavior, resulting in more robust and readable code.