Improved Collections in Java 21

Introduction

In Java, there are three fundamental abstractions for grouping data:

1. List<E>: Index-ordered collection that allows duplicates. Elements maintain their insertion position (ArrayList, LinkedList).

2. Set<E>: Collection of unique elements. Can be unordered (HashSet) or ordered by insertion (LinkedHashSet) or natural ordering (TreeSet).

3. Map<K,V>: It is not a Collection, but a number of key-value pairs with unique keys. Similarly: unordered (HashMap), insertion-ordered (LinkedHashMap), or natural (TreeMap).

These interfaces have been widely used since JDK 1.2 (1998), with few structural changes since JDK 5 (2004, generics). However, they had a critical gap: there was no common abstraction for collections with defined "encounter order" (clear first/last element) that unified:

List/Deque     vs     LinkedHashSet/SortedSet  (¡no common supertype!)
(duplicates OK)          (unique)

Java 21 (JEP 431) introduces SequencedCollection, SequencedSet, and SequencedMap, the first fundamental interfaces in many years, resolving this historic inconsistency.

Ordered Sets

The Need for SequencedSet<E>

Before Java 21, developers faced a structural inconsistency: collections with defined encounter order + unique elements existed (LinkedHashSet, NavigableSet), but shared no common interface. Set<E> is unordered by definition, forcing API designers to return concrete LinkedHashSet types, violating interface segregation.

Pre-Java 21:

// PROBLEM 1: No abstraction for ordered+unique
public LinkedHashSet<String> getOrderedUniqueItems() {  // Concrete type! Bad API design, an interface should be used
    return new LinkedHashSet<>(items);
}

// PROBLEM 2: Accessing first/last requires hacks
LinkedHashSet<String> set = new LinkedHashSet<>(List.of("C", "A", "B"));
String first = set.iterator().next();        
String last  = null;
Iterator<String> it = set.iterator();
while (it.hasNext()) last = it.next();       // Manual scan!
set.remove(last);                           // Order may shift

// PROBLEM 3: Reverse iteration? Copy to List first
List<String> reversed = new ArrayList<>(set);
Collections.reverse(reversed);              // O(n) copy + reverse

Java 21 solution - SequencedSet<E> (extends SequencedCollection<E>):

SequencedSet<String> set = new LinkedHashSet<>();
set.addLast("C"); set.addLast("A"); set.addLast("B");  // [C, A, B]

String first = set.getFirst();    // "C" - O(1)
String last  = set.getLast();     // "B"  - O(1)
set.removeFirst();                // [A, B]

// Reordering existing elements (NEW!)
set.addFirst("A");                // Moves A to front: [A, B]
set.addLast("B");                 // Moves B to end:   [A, B]

// Reverse stream - uniform across all sequenced types
set.reversed().stream()
   .forEach(System.out::println);  // B, A

Why No SequencedList<E> equivalent?

List<E> and Deque<E> already share the exact operations SequencedCollection provides (getFirst(), removeLast(), etc.). SequencedCollection<E> sits between Collection<E> and both:

graph TB
    Collection --> SC[SequencedCollection]
    SC --> List["List<E>"]
    SC --> Deque["Deque<E>"]
    
    classDef sequenced fill:#bbdefb,stroke:#01579b,stroke-width:2px
    classDef standard fill:#f5f5f5
    class SC sequenced
    class List,Deque standard

List gained SequencedCollection methods for free. No need for a SequencedList wrapper—List<E> is already sequenced.

Why Tail Elements Matter

Accessing first/last elements (tail elements) is a fundamental operation in ordered collections, yet in pre-Java 21 it could be error-prone. Developers constantly needed temporary variables just to compute indices, leading to off-by-one errors.

Pre-Java 21:

List<String> items = fetchItemsFromDatabase();  // Simulate expensive fetch
int lastIndex = items.size() - 1;              // Temp var #1: index calculation
String lastItem = items.get(lastIndex);        // Temp var #2: store result
processLastItem(lastItem);                     // Finally use it

// Or inline 
String firstItem = items.isEmpty() ? null : items.get(0);  // Null check + index

// Example - Processing latest log entry:

List<LogEntry> logs = readLogFile();  // 10k+ entries
if (!logs.isEmpty()) {
    int lastIdx = logs.size() - 1;               // Temporary variable for index
    LogEntry latest = logs.get(lastIdx);         // Another temporary variable
    sendAlert(latest.getLevel(), latest.getTime()); 
}

Post-JDK 21:

List<LogEntry> logs = readLogFile();
if (!logs.isEmpty()) {
    LogEntry latest = logs.getLast();         // Direct! No temporary variables
    sendAlert(latest.getLevel(), latest.getTime());
}

// Even inlines perfectly:
processLastItem(fetchItemsFromDatabase().getLast());  // Zero boilerplate

Why this matters technically:

• Eliminates size()-1 bug (most common List off-by-one error)

• Uniform API across List, Deque, LinkedHashSet via SequencedCollection

Ordered Maps

The Need for SequencedMap<K,V>

As it has been explained with Set, Pre-Java 21, Map<K,V> implementations with defined encounter order (LinkedHashMap, NavigableMap) lacked a common interface, forcing concrete types in APIs and inconsistent endpoint operations. Map naming conventions were also fragmented (firstEntry() vs pollFirstEntry() vs no operations at all).

Pre-Java 21:

// PROBLEM 1: Concrete types in APIs
public LinkedHashMap<String, Integer> getOrderedScores() {  // Bad API design, an interface should be used
    return new LinkedHashMap<>();
}

// PROBLEM 2: No consistent first/last access
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3); 
map.put("A", 1); 
map.put("B", 2);  // Order: C,A,B

// First entry? Iterator hack
Map.Entry<String, Integer> first = map.entrySet().iterator().next();  // O(n)

// Last entry? Manual scan
Map.Entry<String, Integer> last = null;
for (Map.Entry<String, Integer> e : map.entrySet()) {
    last = e;
}

Java 21 solution - SequencedMap<K,V>:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("C", 3); 
map.putLast("A", 1); 
map.putLast("B", 2);  // [C,A,B]

Map.Entry<String, Integer> first = map.firstEntry();   // O(1) - "C"=3
Map.Entry<String, Integer> last  = map.lastEntry();    // O(1) - "B"=2

// Remove + return (poll semantics from NavigableMap)
Map.Entry<String, Integer> removed = map.pollLastEntry();  // "B"=2, map=[C,A]

// Reordering existing keys (NEW!)
map.putFirst("A", 99);  // Updates A, moves to front: [A, C]

Sequenced Map Views

Unique to maps: Three sequenced projections that preserve order:

SequencedMap<String, Integer> scores = new LinkedHashMap<>();
scores.put("Z", 26); 
scores.put("A", 1); 
scores.put("M", 13);

// Traditional views (unordered!)
Set<String> keys = scores.keySet();           // HashSet - order lost!

// NEW: Sequenced views preserve encounter order
SequencedSet<String> seqKeys = scores.sequencedKeySet();    // [Z, A, M]
seqKeys.removeFirst();  // Removes "Z" from original map!

Real-world example - LRU Cache simulation:

SequencedMap<String, Integer> cache = new LinkedHashMap<>();
cache.putLast("key1", 100);
cache.putLast("key2", 200);

// "Touch" key1 (move to end)
cache.putLast("key1", 150);  // Now: [key2, key1]

// Evict oldest
cache.pollFirstEntry();      // Removes key2

Map Hierarchy

graph TB
    Map --> SM["SequencedMap<K,V>"]
    SM --> SortedMap
    SortedMap --> NavigableMap
    LHM["LinkedHashMap"]
    SM -.-> LHM
    
    classDef new fill:#bbdefb,stroke:#01579b
    classDef impl fill:#f3e5f5
    class SM new
    class LHM impl

Key Technical Differences

Reverse Streams

Pre-Java 21 hacks:

Stream<String> reversed = IntStream.range(0, list.size())
    .mapToObj(i -> list.get(list.size()-1-i));

Java 21 solution - Works everywhere:

// List, Set, Map views - uniform!
list.reversed().stream()
linkedHashSet.reversed().stream()
map.sequencedKeySet().reversed().stream()
    .filter(s -> s.startsWith("A"))
    .forEach(System.out::println);

Example: Log processing:

logEntries.reversed().stream()    // Newest first
    .filter(LogEntry::isError)
    .limit(5)
    .forEach(LogAnalyzer::process);

Why "Sequenced" Instead of "Ordered"?

Not "OrderedSet" because:

1. SortedSet already exists (natural/comparator order, like TreeSet)

2. "Encounter order" ≠ sorted order:

   NavigableSet<Integer> sorted = new TreeSet<>(List.of(3, 1, 2));  // [1,2,3]
   LinkedHashSet<Integer> seqd  = new LinkedHashSet<>(List.of(3,1,2)); // [3,1,2]
   

3. SequencedSet preserves insertion order (or stable order), not sorted order

4. Terminology consistency: Matches Stream API's "encounter order" concept [JEP 431]

Key distinction:

SequencedSet<Integer> seq = new LinkedHashSet<>(List.of(3, 1, 2));  // [3,1,2]
SortedSet<Integer> sorted = new TreeSet<>(seq);                    // [1,2,3]

Collection Hierarchy