Topic 9.12
Sequenced Collections
In one line
Java 21 added SequencedCollection, SequencedSet and SequencedMap: one standard way to get the first and last element, add at either end, and walk in reverse with reversed(), for every collection that has a defined order.
Think of it like this
A queue at a ticket counter has a clear front and back. Whether it's a line of people, a stack of plates or a row of seats, you can always ask "who's first?", "who's last?" and "read the line backwards". Before Java 21 every ordered collection asked these questions differently; now they all use the same words.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Encounter order
- The defined order in which a collection hands out its elements: insertion order, sorted order, or position in a list.
- SequencedCollection
- A Java 21 interface for collections with a first and a last element and a reversed view.
- View
- An object that shows another collection's data in a different way without copying it.
- JEP
- JDK Enhancement Proposal: the document that describes a new Java feature, like JEP 431 for sequenced collections.
- Live
- Always up to date: it reflects later changes to the original.
Step by step
01The problem Java 21 solved
Four ordered collections, four different ways to read the last element. And for LinkedHashSet, which keeps insertion order, there was no getLast at all.
Generic code couldn't say "any collection with an order" either: List and Deque share no common supertype for ordered operations, and Collection makes no promise about order.
list.get(list.size() - 1); // List
deque.getLast(); // Deque
sortedSet.last(); // SortedSet
// LinkedHashSet: no direct way. Loop to the end:
String last = null;
for (String s : linkedSet) last = s;02The new interfaces
SequencedCollection sits between Collection and List/Deque. SequencedSet extends it and Set. SequencedMap extends Map. Existing classes were retrofitted, so your ArrayList already has getFirst() on Java 21.
03First, last and both ends
getFirst() and getLast() throw NoSuchElementException on an empty collection (like Deque, unlike list.get(0)'s IndexOutOfBoundsException). removeFirst()/removeLast() remove and return.
On ArrayList, addFirst is O(n) because every element shifts right (Topic 9.2), while ArrayDeque.addFirst is O(1). Same method name, different cost: pick the right class.
04reversed() is a view
list.reversed() doesn't copy. Iterating it walks the original backwards. Add to the original and the view sees it; set through the view changes the original at the mirrored position.
For a reversed copy you can keep, use new ArrayList<>(list.reversed()) or List.copyOf(list.reversed()).
05Maps: firstEntry, pollLastEntry, putFirst
LinkedHashMap keeps insertion order, so firstEntry() is the oldest entry and lastEntry() the newest. pollFirstEntry() removes and returns it, handy for simple caches and queues of keyed work.
putFirst(k, v) inserts at (or moves to) the front. The entries returned by firstEntry() and friends are immutable snapshots: calling setValue on them throws.
06What isn't sequenced
HashSet and HashMap have no defined order (Topic 9.4), so they don't implement the new interfaces. A method that needs an order should take SequencedCollection<E> or SequencedMap<K,V> as its parameter type; then the compiler stops callers from passing a HashSet.
Try it yourself
- 1
Move to the front
In "One API for both ends", change
set.addFirst(3)toset.addLast(1). Predict the set before running. ([2, 3, 1], because 1 moves to the end.) - 2
Reverse a TreeSet in place?
Add
sorted.addFirst(0);to the second example. Run it and read the exception: a sorted set decides positions itself, so it can't add at the front.
Code & diagrams
Expected output
[a, b, c, d] first=a last=d
reversed view: [d, c, b, a]
set: [3, 1, 2] last=2
map: {w=0, x=1, y=2} first=w=0 last=y=2
pollLastEntry: y=2 -> {w=0, x=1}Expected output
back sees the change: [4, 3, 2, 1]
nums: [1, 2, 3, 40]
TreeSet reversed: [5, 3, 1], first=1static <E> E newest(SequencedCollection<E> items) {
return items.getLast();
}
newest(new ArrayList<>(List.of(1, 2))); // fine
newest(new ArrayDeque<>(List.of(1, 2))); // fine
newest(new LinkedHashSet<>(List.of(1, 2))); // fine
// newest(new HashSet<>(List.of(1, 2))); // compile error: HashSet has no orderBreak it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
getFirst on an empty list
Call new ArrayList<String>().getFirst().
Myth vs fact
Myth
reversed() returns a reversed copy.
Fact
It returns a live view backed by the original. Copy it if you need an independent list.
Myth
Every collection got getFirst and getLast in Java 21.
Fact
Only collections with a defined order. HashSet and HashMap are not sequenced.
Myth
addFirst is cheap everywhere.
Fact
It's O(1) on ArrayDeque and LinkedList but O(n) on ArrayList, because every element shifts.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Adding
getFirst()toListbroke a few third-party libraries that already declared agetFirst()with a different return type (Kotlin'sList.getFirstextension is a well-known example), so check dependencies when upgrading to 21. - ▸
Collections.unmodifiableSequencedCollection,unmodifiableSequencedSetandunmodifiableSequencedMapwere added alongside, so read-only views keep the sequenced API. - ▸
LinkedHashMap.reversed().entrySet()iterates newest-first in O(n) with no copying, which is a clean way to show "recent items first" from an insertion-ordered cache.
Remember this
- 1
Before Java 21, getting the last element meant
list.get(list.size() - 1)for a list,deque.getLast()for a deque,sortedSet.last()for aTreeSet, and for aLinkedHashSetthere was no direct way at all: you had to iterate to the end. Java 21 (JEP 431) unified this. - 2
**
SequencedCollection<E>** (extendsCollection) addsaddFirst,addLast,getFirst,getLast,removeFirst,removeLastandreversed().List,DequeandLinkedHashSet(throughSequencedSet) all implement it, so the same method names work everywhere. - 3
**
SequencedSet<E>** is a sequenced collection with no duplicates;SortedSet/NavigableSet(TreeSet) andLinkedHashSetare sequenced sets. **SequencedMap<K,V>** addsfirstEntry,lastEntry,pollFirstEntry,pollLastEntry,putFirst,putLast,reversed(), plussequencedKeySet(),sequencedValues()andsequencedEntrySet().LinkedHashMapandTreeMapimplement it. - 4
**
reversed()returns a live view**, not a copy: changes to the original show up in the reversed view, and writes through a modifiable reversed view change the original. It's O(1) to create. - 5
Not every collection can do every operation. A sorted collection decides positions itself, so
TreeSet.addFirstthrowsUnsupportedOperationException. An immutable list throws onaddFirstlike onadd.HashSetandHashMaphave no defined order, so they are not sequenced at all. - 6
On
LinkedHashSet,addFirst(x)andaddLast(x)movexif it's already present. OnLinkedHashMap,putFirst/putLastmove the entry too. That makes some LRU-style code shorter.
Explain it without notes
What problem do sequenced collections solve, and which Java version added them?
Why does TreeSet.addFirst throw, while LinkedHashSet.addFirst works?
Is list.reversed() a copy or a view? What are the consequences?
Practice
Using sequenced methods, write code that rotates a list one step to the left (first element moves to the end).
Print the three most recently inserted keys of a LinkedHashMap, newest first.
Trade-offs
- ↔
Sequenced methods make code clearer, but the cost of the same method differs by class (addFirst on ArrayList vs ArrayDeque).
- ↔
Taking SequencedCollection as a parameter type documents and enforces ordering, but ties the code to Java 21 or later.
Done when you can
Done when you can name the three sequenced interfaces and which classes implement them.
Done when you can use getFirst/getLast, addFirst/addLast and reversed() and say what each costs.
Done when you know reversed() is a live view and that HashSet/HashMap are not sequenced.