Java 21 introduces Sequenced Collections - a revolutionary approach to handling ordered collections with consistent, intuitive APIs across all collection types. This feature addresses long-standing inconsistencies in Java's collection framework.
The Problem: Inconsistent Ordered Collection APIs
Before Java 21, working with ordered collections was frustratingly inconsistent:
// Different APIs for similar operations across collections
List<String> list = new ArrayList<>();
list.add("first");
String firstList = list.get(0); // get first
String lastList = list.get(list.size() - 1); // get last - verbose!
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("first");
String firstDeque = deque.getFirst(); // get first
String lastDeque = deque.getLast(); // get last
// No direct way to get first/last from SortedSet
SortedSet<String> sortedSet = new TreeSet<>();
sortedSet.add("apple");
sortedSet.add("banana");
// How to get first efficiently?
String firstSorted = sortedSet.iterator().next(); // Inefficient!
Introducing Sequenced Collections
Java 21 adds new interfaces that provide consistent ordering operations:
Collection Hierarchy with Sequenced Collections: ┌─────────────────┐ │ SequencedCollection │ ← New interface └─────────────────┘ △ │ ┌─────────────────┐ │ List │ └─────────────────┘ △ │ ┌─────────────────┐ │ SequencedSet │ ← New interface └─────────────────┘ △ │ ┌─────────────────┐ │ SortedSet │ └─────────────────┘ △ │ ┌─────────────────┐ │ NavigableSet │ └─────────────────┘ ┌─────────────────┐ │ SequencedMap │ ← New interface └─────────────────┘ △ │ ┌─────────────────┐ │ SortedMap │ └─────────────────┘ △ │ ┌─────────────────┐ │ NavigableMap │ └─────────────────┘
Core Sequenced Collection Interfaces
1. SequencedCollection Interface
public interface SequencedCollection<E> extends Collection<E> {
// New methods for ordered access
SequencedCollection<E> reversed();
void addFirst(E e);
void addLast(E e);
E getFirst();
E getLast();
E removeFirst();
E removeLast();
}
2. SequencedSet Interface
public interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
// Override return type for better type safety
SequencedSet<E> reversed();
}
3. SequencedMap Interface
public interface SequencedMap<K, V> extends Map<K, V> {
// Map-specific sequenced operations
SequencedMap<K, V> reversed();
SequencedSet<K> sequencedKeySet();
SequencedCollection<V> sequencedValues();
SequencedSet<Entry<K, V>> sequencedEntrySet();
Entry<K, V> firstEntry();
Entry<K, V> lastEntry();
Entry<K, V> pollFirstEntry();
Entry<K, V> pollLastEntry();
V putFirst(K key, V value);
V putLast(K key, V value);
}
Practical Usage Examples
1. Consistent List Operations
public class SequencedListExamples {
public static void main(String[] args) {
// Create a sequenced list
SequencedCollection<String> list = new ArrayList<>();
// Add elements to both ends
list.addFirst("first"); // ["first"]
list.addLast("last"); // ["first", "last"]
list.add("middle"); // ["first", "last", "middle"]
// Access ends consistently
System.out.println("First: " + list.getFirst()); // "first"
System.out.println("Last: " + list.getLast()); // "middle"
// Remove from ends
String removedFirst = list.removeFirst(); // "first"
String removedLast = list.removeLast(); // "middle"
System.out.println("Remaining: " + list); // ["last"]
// Reverse view
SequencedCollection<String> reversed = list.reversed();
reversed.addFirst("new-first"); // Affects original list
System.out.println("Original: " + list); // ["new-first", "last"]
}
}
2. Set Operations with Order
public class SequencedSetExamples {
public static void main(String[] args) {
// LinkedHashSet maintains insertion order
SequencedSet<String> orderedSet = new LinkedHashSet<>();
orderedSet.add("apple");
orderedSet.add("banana");
orderedSet.addFirst("apricot"); // Insert at beginning
orderedSet.addLast("cherry"); // Insert at end
System.out.println("Set: " + orderedSet); // [apricot, apple, banana, cherry]
System.out.println("First: " + orderedSet.getFirst()); // apricot
System.out.println("Last: " + orderedSet.getLast()); // cherry
// TreeSet with natural ordering
SequencedSet<String> sortedSet = new TreeSet<>();
sortedSet.addAll(List.of("zebra", "apple", "monkey"));
System.out.println("Sorted first: " + sortedSet.getFirst()); // apple
System.out.println("Sorted last: " + sortedSet.getLast()); // zebra
// Reverse view maintains performance
SequencedSet<String> reversedSorted = sortedSet.reversed();
System.out.println("Reversed first: " + reversedSorted.getFirst()); // zebra
}
}
3. Map Operations with Order
public class SequencedMapExamples {
public static void main(String[] args) {
// LinkedHashMap maintains insertion order
SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.put("one", 1);
map.put("three", 3);
map.putFirst("zero", 0); // Insert at beginning
map.putLast("four", 4); // Insert at end
System.out.println("Map: " + map); // {zero=0, one=1, three=3, four=4}
// Access first and last entries
Map.Entry<String, Integer> firstEntry = map.firstEntry();
Map.Entry<String, Integer> lastEntry = map.lastEntry();
System.out.println("First: " + firstEntry.getKey() + "=" + firstEntry.getValue());
System.out.println("Last: " + lastEntry.getKey() + "=" + lastEntry.getValue());
// Poll entries (remove and return)
Map.Entry<String, Integer> polledFirst = map.pollFirstEntry();
Map.Entry<String, Integer> polledLast = map.pollLastEntry();
System.out.println("After polling: " + map); // {one=1, three=3}
// Sequenced views
SequencedSet<String> keys = map.sequencedKeySet();
SequencedCollection<Integer> values = map.sequencedValues();
SequencedSet<Map.Entry<String, Integer>> entries = map.sequencedEntrySet();
System.out.println("Keys: " + keys.getFirst() + " to " + keys.getLast());
}
}
Real-World Use Cases
1. LRU (Least Recently Used) Cache
public class LRUCache<K, V> {
private final SequencedMap<K, V> cache;
private final int maxSize;
public LRUCache(int maxSize) {
this.maxSize = maxSize;
this.cache = new LinkedHashMap<>(maxSize, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
};
}
public V get(K key) {
return cache.get(key);
}
public void put(K key, V value) {
cache.put(key, value);
}
public V getMostRecent() {
return cache.getLast(); // Most recently accessed
}
public V getLeastRecent() {
return cache.getFirst(); // Least recently accessed
}
public void removeOldest() {
cache.pollFirstEntry(); // Remove least recently used
}
public SequencedSet<K> getKeysInAccessOrder() {
return cache.sequencedKeySet();
}
}
2. Message Queue with Priority Handling
public class MessageProcessor {
private final SequencedCollection<Message> highPriorityQueue = new ArrayDeque<>();
private final SequencedCollection<Message> normalQueue = new ArrayDeque<>();
public void addHighPriority(Message message) {
highPriorityQueue.addLast(message);
}
public void addNormalPriority(Message message) {
normalQueue.addLast(message);
}
public Message getNextMessage() {
// Process high priority first, then normal
if (!highPriorityQueue.isEmpty()) {
return highPriorityQueue.removeFirst();
} else if (!normalQueue.isEmpty()) {
return normalQueue.removeFirst();
}
return null;
}
public Message peekNextMessage() {
if (!highPriorityQueue.isEmpty()) {
return highPriorityQueue.getFirst();
} else if (!normalQueue.isEmpty()) {
return normalQueue.getFirst();
}
return null;
}
public void returnToFront(Message message) {
// Re-queue important message at front
highPriorityQueue.addFirst(message);
}
}
3. Navigation History
public class NavigationHistory {
private final SequencedCollection<String> history = new ArrayDeque<>();
private final int maxHistorySize;
private int currentIndex = -1;
public NavigationHistory(int maxHistorySize) {
this.maxHistorySize = maxHistorySize;
}
public void navigateTo(String page) {
// Remove future history if we're not at the end
if (currentIndex < history.size() - 1) {
SequencedCollection<String> future = getFutureHistory();
future.clear();
}
history.addLast(page);
currentIndex = history.size() - 1;
// Enforce size limit
if (history.size() > maxHistorySize) {
history.removeFirst();
currentIndex--;
}
}
public String goBack() {
if (currentIndex > 0) {
currentIndex--;
return history.reversed().stream()
.skip(history.size() - currentIndex - 1)
.findFirst()
.orElseThrow();
}
throw new IllegalStateException("Cannot go back");
}
public String goForward() {
if (currentIndex < history.size() - 1) {
currentIndex++;
return history.reversed().stream()
.skip(history.size() - currentIndex - 1)
.findFirst()
.orElseThrow();
}
throw new IllegalStateException("Cannot go forward");
}
public SequencedCollection<String> getFutureHistory() {
return history.reversed().stream()
.limit(history.size() - currentIndex - 1)
.collect(Collectors.toCollection(ArrayDeque::new));
}
public String getCurrentPage() {
if (currentIndex >= 0) {
return history.reversed().stream()
.skip(history.size() - currentIndex - 1)
.findFirst()
.orElseThrow();
}
return null;
}
}
Performance Characteristics
1. Collection Performance Comparison
public class SequencedCollectionPerformance {
public static void benchmarkOperations() {
int size = 100000;
// ArrayList performance
SequencedCollection<Integer> arrayList = new ArrayList<>();
benchmark("ArrayList addFirst", () -> {
for (int i = 0; i < size; i++) {
arrayList.addFirst(i); // O(n) - shifts all elements!
}
});
// ArrayDeque performance
SequencedCollection<Integer> arrayDeque = new ArrayDeque<>();
benchmark("ArrayDeque addFirst", () -> {
for (int i = 0; i < size; i++) {
arrayDeque.addFirst(i); // O(1) - circular buffer
}
});
// LinkedHashSet performance
SequencedSet<Integer> linkedHashSet = new LinkedHashSet<>();
benchmark("LinkedHashSet addFirst", () -> {
for (int i = 0; i < size; i++) {
linkedHashSet.addFirst(i); // O(1) - linked list
}
});
}
private static void benchmark(String name, Runnable operation) {
long start = System.nanoTime();
operation.run();
long duration = System.nanoTime() - start;
System.out.printf("%s: %d ms%n", name, duration / 1_000_000);
}
}
2. Choosing the Right Implementation
public class SequencedCollectionChooser {
public static <E> SequencedCollection<E> createOptimalCollection(UsagePattern pattern) {
return switch (pattern) {
case FREQUENT_RANDOM_ACCESS -> {
// ArrayList - good for get(index) but expensive addFirst/removeFirst
yield new ArrayList<>();
}
case FREQUENT_FIRST_LAST_OPS -> {
// ArrayDeque - optimized for add/remove from both ends
yield new ArrayDeque<>();
}
case UNIQUE_ELEMENTS_WITH_ORDER -> {
// LinkedHashSet - maintains insertion order, prevents duplicates
yield new LinkedHashSet<>();
}
case SORTED_ELEMENTS -> {
// TreeSet - maintains natural ordering
yield new TreeSet<>();
}
};
}
public enum UsagePattern {
FREQUENT_RANDOM_ACCESS,
FREQUENT_FIRST_LAST_OPS,
UNIQUE_ELEMENTS_WITH_ORDER,
SORTED_ELEMENTS
}
}
Migration from Legacy Code
1. Converting Legacy Collection Code
public class LegacyMigration {
// Before Java 21 - inconsistent approaches
public static <T> T getFirstElementLegacy(Collection<T> collection) {
if (collection instanceof List<T> list) {
return list.get(0);
} else if (collection instanceof Deque<T> deque) {
return deque.getFirst();
} else if (collection instanceof SortedSet<T> sortedSet) {
return sortedSet.first();
} else {
return collection.iterator().next();
}
}
// After Java 21 - unified approach
public static <T> T getFirstElementModern(Collection<T> collection) {
if (collection instanceof SequencedCollection<T> sequenced) {
return sequenced.getFirst();
} else {
return collection.iterator().next();
}
}
// Handling maps
public static <K, V> V getFirstValueLegacy(Map<K, V> map) {
if (map instanceof SortedMap<K, V> sortedMap) {
return sortedMap.get(sortedMap.firstKey());
} else if (map instanceof LinkedHashMap<K, V> linkedMap) {
return linkedMap.entrySet().iterator().next().getValue();
} else {
throw new UnsupportedOperationException("Map doesn't support ordering");
}
}
public static <K, V> V getFirstValueModern(Map<K, V> map) {
if (map instanceof SequencedMap<K, V> sequencedMap) {
return sequencedMap.firstEntry().getValue();
} else {
throw new UnsupportedOperationException("Map doesn't support ordering");
}
}
}
2. Backward Compatibility
public class CompatibilityLayer {
// For code that needs to work with pre-Java 21 and Java 21+
public static <E> void addToBeginning(Collection<E> collection, E element) {
if (collection instanceof SequencedCollection<E> sequenced) {
sequenced.addFirst(element);
} else if (collection instanceof List<E> list) {
list.add(0, element);
} else if (collection instanceof Deque<E> deque) {
deque.addFirst(element);
} else {
// Fallback - create new collection
List<E> newList = new ArrayList<>(collection);
newList.add(0, element);
collection.clear();
collection.addAll(newList);
}
}
// Safe first element access
public static <E> Optional<E> getFirstSafe(Collection<E> collection) {
if (collection instanceof SequencedCollection<E> sequenced) {
try {
return Optional.of(sequenced.getFirst());
} catch (NoSuchElementException e) {
return Optional.empty();
}
} else if (!collection.isEmpty()) {
return Optional.of(collection.iterator().next());
} else {
return Optional.empty();
}
}
}
Advanced Patterns and Recipes
1. Circular Buffer Implementation
public class CircularBuffer<E> implements SequencedCollection<E> {
private final SequencedCollection<E> delegate;
private final int capacity;
public CircularBuffer(int capacity) {
this.capacity = capacity;
this.delegate = new ArrayDeque<>(capacity);
}
@Override
public boolean add(E e) {
if (delegate.size() == capacity) {
delegate.removeFirst();
}
return delegate.add(e);
}
@Override
public void addFirst(E e) {
if (delegate.size() == capacity) {
delegate.removeLast();
}
delegate.addFirst(e);
}
@Override
public void addLast(E e) {
add(e);
}
// Delegate all other SequencedCollection methods
@Override public E getFirst() { return delegate.getFirst(); }
@Override public E getLast() { return delegate.getLast(); }
@Override public E removeFirst() { return delegate.removeFirst(); }
@Override public E removeLast() { return delegate.removeLast(); }
@Override public SequencedCollection<E> reversed() { return delegate.reversed(); }
// Implement other Collection methods...
@Override public int size() { return delegate.size(); }
@Override public boolean isEmpty() { return delegate.isEmpty(); }
@Override public Iterator<E> iterator() { return delegate.iterator(); }
// ... remaining Collection methods
}
2. Priority-Aware Collection
public class PrioritySequencedCollection<E> implements SequencedCollection<E> {
private final SequencedCollection<E> highPriority = new ArrayDeque<>();
private final SequencedCollection<E> normalPriority = new ArrayDeque<>();
@Override
public boolean add(E e) {
return addLast(e);
}
@Override
public void addFirst(E e) {
highPriority.addFirst(e);
}
@Override
public void addLast(E e) {
normalPriority.addLast(e);
}
@Override
public E getFirst() {
if (!highPriority.isEmpty()) {
return highPriority.getFirst();
} else if (!normalPriority.isEmpty()) {
return normalPriority.getFirst();
}
throw new NoSuchElementException();
}
@Override
public E getLast() {
if (!normalPriority.isEmpty()) {
return normalPriority.getLast();
} else if (!highPriority.isEmpty()) {
return highPriority.getLast();
}
throw new NoSuchElementException();
}
@Override
public E removeFirst() {
if (!highPriority.isEmpty()) {
return highPriority.removeFirst();
} else if (!normalPriority.isEmpty()) {
return normalPriority.removeFirst();
}
throw new NoSuchElementException();
}
@Override
public E removeLast() {
if (!normalPriority.isEmpty()) {
return normalPriority.removeLast();
} else if (!highPriority.isEmpty()) {
return highPriority.removeLast();
}
throw new NoSuchElementException();
}
@Override
public SequencedCollection<E> reversed() {
// Return a reversed view that maintains priority semantics
return new ReversedPriorityView();
}
private class ReversedPriorityView implements SequencedCollection<E> {
// Implementation of reversed view...
}
// Other collection methods...
}
Testing Sequenced Collections
1. Comprehensive Test Suite
class SequencedCollectionTest {
@Test
void testAddFirstAndGetFirst() {
SequencedCollection<String> collection = new ArrayList<>();
collection.addFirst("first");
collection.addLast("last");
assertEquals("first", collection.getFirst());
assertEquals("last", collection.getLast());
}
@Test
void testRemoveFirstAndLast() {
SequencedCollection<Integer> collection = new ArrayDeque<>();
collection.addAll(List.of(1, 2, 3, 4));
assertEquals(1, collection.removeFirst());
assertEquals(4, collection.removeLast());
assertEquals(List.of(2, 3), new ArrayList<>(collection));
}
@Test
void testReversedView() {
SequencedCollection<String> original = new LinkedHashSet<>();
original.addAll(List.of("a", "b", "c"));
SequencedCollection<String> reversed = original.reversed();
assertEquals("c", reversed.getFirst());
assertEquals("a", reversed.getLast());
// Modifications through reversed view affect original
reversed.addFirst("d");
assertEquals("d", original.getLast());
}
@ParameterizedTest
@MethodSource("collectionImplementations")
void testSequencedContract(SequencedCollection<Integer> collection) {
collection.addFirst(1);
collection.addLast(2);
assertEquals(1, collection.getFirst());
assertEquals(2, collection.getLast());
assertEquals(1, collection.removeFirst());
assertEquals(2, collection.removeLast());
assertTrue(collection.isEmpty());
}
static Stream<SequencedCollection<Integer>> collectionImplementations() {
return Stream.of(
new ArrayList<>(),
new LinkedList<>(),
new ArrayDeque<>(),
new LinkedHashSet<>()
);
}
}
Best Practices
1. Choose the Right Implementation
public class SequencedCollectionBestPractices {
public void implementationGuidelines() {
// Use cases and recommended implementations:
// Frequent random access + sequenced operations
SequencedCollection<String> forRandomAccess = new ArrayList<>();
// Pros: Fast get(index), good iteration
// Cons: Expensive addFirst/removeFirst (O(n))
// Frequent add/remove from both ends
SequencedCollection<String> forEndOperations = new ArrayDeque<>();
// Pros: O(1) addFirst/removeFirst, good memory locality
// Cons: No random access
// Unique elements with insertion order
SequencedSet<String> forUniqueOrdered = new LinkedHashSet<>();
// Pros: Prevents duplicates, maintains order
// Cons: No random access, memory overhead
// Sorted elements
SequencedSet<String> forSorted = new TreeSet<>();
// Pros: Automatic sorting, efficient range operations
// Cons: Slower insertion (O(log n))
}
public void performanceConsiderations() {
// ArrayList - be careful with addFirst/removeFirst
SequencedCollection<Integer> arrayList = new ArrayList<>();
// This is O(n) per operation!
for (int i = 0; i < 100000; i++) {
arrayList.addFirst(i); // Each call shifts all elements!
}
// Use ArrayDeque instead for this pattern
SequencedCollection<Integer> arrayDeque = new ArrayDeque<>();
for (int i = 0; i < 100000; i++) {
arrayDeque.addFirst(i); // O(1) per operation
}
}
}
Conclusion
Java 21 Sequenced Collections provide a much-needed unification of ordered collection APIs:
Key Benefits:
- Consistent API across all ordered collections
- Intuitive operations for first/last element access
- Performance clarity with appropriate implementation choices
- Backward compatibility through new interfaces
- Enhanced readability with fluent method names
Migration Strategy:
- Update type declarations to use sequenced interfaces where appropriate
- Replace custom first/last logic with standardized methods
- Choose optimal implementations based on usage patterns
- Leverage reversed views instead of manual reversal
- Update tests to verify sequenced behavior
Example of Modern Code:
public class ModernSequencedUsage {
public void processTasks(SequencedCollection<Task> tasks) {
// Process highest priority task first
Task highestPriority = tasks.getFirst();
process(highestPriority);
// Add new urgent task to front
tasks.addFirst(createUrgentTask());
// Remove completed task from end
Task completed = tasks.removeLast();
archive(completed);
// Process in reverse order when needed
for (Task task : tasks.reversed()) {
if (needsRecheck(task)) {
recheck(task);
}
}
}
}
Sequenced Collections make Java's collection framework more consistent, expressive, and powerful, finally providing a unified way to work with ordered data structures across the entire ecosystem.