The SequencedCollection interface

The SequencedCollection<E> interface extends Collection<E> with the ability to treat elements as an ordered sequence with two accessible ends. Rather than focusing only on containment (as standard collections do), it introduces a consistent way to work with the front and back of the collection.

It combines the general-purpose nature of a collection with the bidirectional capabilities typically associated with a List or Deque. Through a small, consistent set of methods, it allows you to access, insert, and remove elements from either end, as well as obtain a reversed view of the same data without copying.

This abstraction enables writing algorithms that operate uniformly across different collection types while preserving their natural encounter order semantics.

The SequencedCollection interface

SequencedCollection<E> extends the standard Collection<E> interface. It is the root interface for sequenced collections and is directly extended by List and Deque.

Here is what the interface looks like:

interface SequencedCollection<E> extends Collection<E> {
    // Returns a reverse-ordered view of this collection
    SequencedCollection<E> reversed();

    // Methods promoted from Deque
    void addFirst(E e);
    void addLast(E e);
    E getFirst();
    E getLast();
    E removeFirst();
    E removeLast();
}

Notice that almost all of these methods, except reversed(), were promoted from the Deque interface. They also received default implementations. This means existing classes like ArrayList and LinkedList inherited these capabilities automatically without a complete rewrite.

Key API methods

The interface introduces several methods for double-ended access. Below is a detailed breakdown of how they work.

• addFirst(E e): This method inserts a new element at the front of the collection:

SequencedCollection<String> items = new LinkedHashSet<>();
items.add("B");
items.add("C");

items.addFirst("A");

// Output: [A, B, C]
System.out.println(items);

Implementation requirements: By default, this method throws an UnsupportedOperationException. Implementations that determine the position of elements automatically (like a TreeSet based on natural order) cannot support this. However, collections that allow positional insertion, like ArrayList, LinkedList, and LinkedHashSet, override this method to support it.

• addLast(E e): This method inserts a new element at the end of the collection:

SequencedCollection<String> items = new LinkedHashSet<>();
items.addFirst("A");
items.addLast("Z");

// Output: [A, Z]
System.out.println(items);

Implementation requirements: Just like addFirst(), the default implementation throws an UnsupportedOperationException unless the specific class explicitly supports positional insertion.

• getFirst(): This method returns the first element in the collection according to its encounter order:

SequencedCollection<String> tasks = new ArrayList<>();
tasks.add("Design");
tasks.add("Code");

// Output: First task: Design
System.out.println("First task: " + tasks.getFirst());

Implementation requirements: The default implementation retrieves an iterator from the collection and returns the first element it yields. If the collection is empty, it throws a NoSuchElementException.

Returns: The first element in the collection.

• getLast(): This method returns the last element in the collection:

SequencedCollection<String> tasks = new ArrayList<>();
tasks.add("Design");
tasks.add("Code");

// Output: Last task: Code
System.out.println("Last task: " + tasks.getLast());

Implementation requirements: The default implementation obtains an iterator from the reversed view of the collection and returns the first element it finds. If the collection is empty, it throws a NoSuchElementException.

Returns: The last element in the collection.

• removeFirst(): This method removes and returns the first element in the collection. Unlike getFirst(), which only inspects the element, this method modifies the collection:

SequencedCollection<String> queue = new LinkedList<>();
queue.add("Task 1");
queue.add("Task 2");

String removed = queue.removeFirst();

// Output: Removed: Task 1
System.out.println("Removed: " + removed);

// Output: Remaining: [Task 2]
System.out.println("Remaining: " + queue);

Implementation requirements: The default implementation retrieves an iterator, calls its next() method to get the first element, removes it using the iterator's remove() method, and returns the element. It throws a NoSuchElementException if the collection is empty.

Returns: The removed first element.

• removeLast(): This method removes and returns the last element in the collection:

SequencedCollection<String> queue = new LinkedList<>();
queue.add("Task 1");
queue.add("Task 2");

String removed = queue.removeLast();

// Output: Removed: Task 2
System.out.println("Removed: " + removed);

// Output: Remaining: [Task 1]
System.out.println("Remaining: " + queue);

Implementation requirements: The default implementation retrieves an iterator from the reversed() view, removes the first element it yields, and returns it. It throws a NoSuchElementException if the collection is empty.

Returns: The removed last element.

• Collections.unmodifiableSequencedCollection(SequencedCollection<E> c): This utility method returns an unmodifiable view of a specific SequencedCollection:

SequencedCollection<String> items = new ArrayList<>();
items.addLast("A");
items.addLast("B");

SequencedCollection<String> readOnlyItems = Collections.unmodifiableSequencedCollection(items);

// Reading works perfectly
// Output: A
System.out.println(readOnlyItems.getFirst());

// This will throw an UnsupportedOperationException
readOnlyItems.addFirst("C");

Implementation requirements: It wraps the provided collection in a view that blocks any structural modifications. If you call mutating methods like addFirst(), removeLast(), or clear(), the program will throw an UnsupportedOperationException.

Returns: A read-only sequenced collection view.

The reversed() view

One of the most useful features of the interface is the reversed() method. Before this method appeared, iterating backward through a collection was inconvenient. It often required traditional for loops with decrementing indexes or special iterators.

The reversed() method solves this by returning a reverse-ordered view of the original collection.

Note that it does not create a new collection or copy the data. It simply provides a window that looks at the existing elements from back to front. Since it is a view, any modifications made to the original collection immediately reflect in the reversed view, and vice versa.

import java.util.ArrayList;
import java.util.SequencedCollection;

public class ReversedViewDemo {
    public static void main(String[] args) {
        SequencedCollection<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);

        SequencedCollection<Integer> reversedNumbers = numbers.reversed();

        System.out.println("Original: " + numbers);         // Output: [1, 2, 3]
        System.out.println("Reversed: " + reversedNumbers); // Output: [3, 2, 1]

        // Modifying the original collection
        numbers.add(4);
        
        System.out.println("Original after adding 4: " + numbers);         // Output: [1, 2, 3, 4]
        System.out.println("Reversed after adding 4: " + reversedNumbers); // Output: [4, 3, 2, 1]

        // Modifying the reversed view
        reversedNumbers.removeFirst(); // Removes "4" (the first element in the reversed view)
        
        System.out.println("Original after removing from view: " + numbers); // Output: [1, 2, 3]
    }
}

As you can see, reversedNumbers.removeFirst() effectively performs an operation similar to removeLast() on the underlying original collection.

Performance characteristics

While SequencedCollection makes your code cleaner and more uniform, the interface does not change the performance characteristics of the underlying data structure. You still need to choose your implementations carefully.

In practice, most standard JDK implementations provide $O(1)$ constant-time access to the first and last elements, but this is not guaranteed by the interface itself. Performance ultimately depends on the concrete implementation:

• ArrayList: An ArrayList is backed by a contiguous array in memory. Adding or removing elements at the end with addLast() or removeLast() is generally very fast. These are $O(1)$ operations. However, calling addFirst() or removeFirst() forces the JVM to shift every subsequent element in the array one position over. This makes front-end operations slow, resulting in $O(n)$ time complexity. Use front operations on an ArrayList with caution.

• LinkedHashSet: This structure uses a hash table alongside a doubly-linked list running through its entries. Because of this linked list, accessing, adding, or removing elements at either the front or the back is a fast $O(1)$ operation.

• LinkedList or ArrayDeque: These structures are specifically designed for efficient modifications at both ends. Calling addFirst() or removeFirst() on a Deque or LinkedList remains a fast $O(1)$ operation.

In practice, ArrayDeque delivers better performance in most scenarios due to the memory usage specifics of LinkedList. It should be the default choice, with LinkedList considered only when you specifically need to work with the List interface in addition to deque operations.

Conclusion

The SequencedCollection<E> interface, introduced in JDK 21, brings clarity and consistency to ordered collections in Java.

Below is an overview of its key characteristics:

• Uniform end-access: It provides standard methods to add, retrieve, and remove elements at both the beginning and the end of the collection.

• Backward iteration: The reversed() method provides a live, reverse-ordered view of the collection. This makes backward iteration as simple as a standard for-each loop.

• Seamless integration: It fits naturally into the existing Java hierarchy, meaning List and Deque implement it automatically.

• Performance depends on implementation: The interface provides the methods, but the underlying class dictates whether those operations are fast or slow.

• Exception handling: It throws NoSuchElementException when retrieving from an empty collection and UnsupportedOperationException when modifying an unmodifiable collection.

By programming to the SequencedCollection interface, you can write expressive, order-aware code that easily adapts to different collection implementations.