# 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:

```plaintext
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**:

```java
// 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>`):

```java
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:

```mermaid
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**:

```java
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:

```java
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**:

```java
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**:

```java
// 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>`:

```java
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:

```java
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**:

```java
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

```mermaid
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

| Operation | `SequencedCollection` | `SequencedMap` |
| --- | --- | --- |
| **Add** | `addFirst(E)` | `putFirst(K,V)` |
| **Get** | `getFirst()` **(throws)** | `firstEntry()` **(null-safe)** |
| **Remove** | `removeFirst()` **(throws)** | `pollFirstEntry()` **(null-safe)** |
| **Views** | N/A | `sequencedKeySet()`, `sequencedEntrySet()` |

## Reverse Streams

**Pre-Java 21 hacks**:

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

**Java 21 solution** - Works everywhere:

```java
// 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:

```java
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**:
    
    ```java
    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**:

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

### Collection Hierarchy

<a href='https://postimg.cc/5XTS5V0j' target='_blank'><img src='https://i.postimg.cc/5XTS5V0j/mermaid-diagram-2026-04-02-210402.png' border='0' alt='mermaid-diagram-2026-04-02-210402'></a>