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.