Sequenced Collections in Java: getFirst(), getLast(), and reversed()

Sequenced collections are collections whose elements have a defined order – lists, deques, LinkedHashSet, TreeSet, and the corresponding maps. Since Java 21, they share methods that let you access the first and the last element and iterate over the elements in reverse order.

Since Java 21, you can read the last element of a list with getLast(). Up to Java 20, you had to calculate the index of the last element:

List<String> pioneers = List.of("Ada", "Grace", "Alan");

// up to Java 20
System.out.println(pioneers.get(pioneers.size() - 1));

// since Java 21
System.out.println(pioneers.getLast());

Alan
Alan

With a LinkedHashSet, the difference is greater. Up to Java 20, you had to use an iterator for the first element and a loop over the entire set for the last element:

LinkedHashSet<String> tags =
    new LinkedHashSet<>(List.of("java", "collections", "api"));

// up to Java 20
String first = tags.iterator().next();
String last = null;
for (String tag : tags) {
  last = tag;
}
System.out.println(first + ", " + last);

// since Java 21
System.out.println(tags.getFirst() + ", " + tags.getLast());

java, api
java, api

The new methods come from three interfaces that were introduced in Java 21 by JEP 431: SequencedCollection, SequencedSet, and SequencedMap.

In this article, you will learn

• which collections have a defined order and which do not,
• where the three new interfaces sit in the hierarchy of the Collections Framework,
• how getFirst(), addFirst(), and removeFirst() behave with empty and unmodifiable collections,
• why reversed() returns a view and not a copy,
• what addFirst() does with a LinkedHashSet and why a TreeSet rejects the method,
• which methods SequencedMap defines and why there is a sequencedKeySet() next to keySet(),
• which pitfalls you should know about.

What Is a Sequenced Collection?

A sequenced collection has a defined order of its elements, the so-called encounter order – the order in which an iterator returns the elements. In this order, there is a first and a last element.

The order comes about in one of two ways. With a list, a deque, a LinkedHashSet, and a LinkedHashMap, your code determines the position of an element – by its index or by when and at which end it is inserted. With a TreeSet and a TreeMap, on the other hand, the sorting determines the position, i.e., the natural order of the elements or a Comparator.

The following table shows which JDK classes have an encounter order, where it comes from, and through which interface the class has been a sequenced collection since Java 21:

Class	Order of the elements	Sequenced via
ArrayList, LinkedList	index	List
ArrayDeque	insertion at the front or at the back	Deque
LinkedHashSet	insertion order	SequencedSet
TreeSet	sorting	SortedSet
LinkedHashMap	insertion order of the keys	SequencedMap
TreeMap	sorting of the keys	SortedMap
HashSet, HashMap	none defined	✗
PriorityQueue	only the element at the head is defined	✗

With a HashSet and a HashMap, the order of the elements is not defined; it can change when you insert more elements. A PriorityQueue only defines which element is removed next – there is no last element. You can read more about this in the article Queue vs. Deque.

The Three Interfaces in the Hierarchy

The following two class diagrams show the new interfaces in the hierarchy of the collections and in that of the maps. They also show the concrete classes from java.util and java.util.concurrent that implement one of the three new interfaces and whose name occurs at least 50 times in the JDK source code. Solid lines stand for extends, dashed lines for implements. The diagrams leave out superclasses such as HashSet or AbstractList.

The three interfaces that were introduced with Java 21 have a dark blue border. The older interfaces and classes that have an encounter order and that, since Java 21, directly or indirectly extend or implement one of the new interfaces have a light blue border. The interfaces without an encounter order have a gray border. Queue is gray, too: Deque extends Queue, but Queue itself has no encounter order.

For the maps, SequencedMap sits between Map and SortedMap:

Deque has had the methods getFirst(), addFirst(), and their counterparts for the end, getLast() and addLast(), since Java 6. JEP 431 moved them from there into the new interface, hence their names. They are not in Collection itself, because Collection also covers collections without an encounter order – a getFirst() on a HashSet, for example, would have no unambiguous answer.

The following method shows what the shared interfaces give you. It prints the first and the last element of any sequenced collection:

static void printEnds(SequencedCollection<?> collection) {
  System.out.println(collection.getFirst() + " to " + collection.getLast());
}

The same method works for a list, a deque, a LinkedHashSet, and a TreeSet:

printEnds(List.of("Ada", "Grace", "Alan"));
printEnds(new ArrayDeque<>(List.of("Ada", "Grace", "Alan")));
printEnds(new LinkedHashSet<>(List.of("java", "collections", "api")));
printEnds(new TreeSet<>(List.of(21, 17, 25)));

Ada to Alan
Ada to Alan
java to api
17 to 25

Up to Java 20, these four classes had no common type with such a method. You would have had to write printEnds() separately for each of them – with get(0) for the list, getFirst() for the deque, an iterator for the LinkedHashSet, and first() for the TreeSet.

Reading, Adding, and Removing the First and Last Element

SequencedCollection defines six methods for the two ends of a collection:

• getFirst() and getLast() return the first and the last element, respectively.
• addFirst(E) and addLast(E) insert an element at the front and at the back, respectively.
• removeFirst() and removeLast() remove the first and the last element, respectively, and return it.

The following example reads both ends of an ArrayList, inserts an element at each end, and removes both again:

List<String> pioneers = new ArrayList<>(List.of("Ada", "Grace", "Alan"));

System.out.println(pioneers.getFirst());
System.out.println(pioneers.getLast());

pioneers.addFirst("Charles");
pioneers.addLast("Linus");
System.out.println(pioneers);

System.out.println(pioneers.removeFirst());
System.out.println(pioneers.removeLast());
System.out.println(pioneers);

Ada
Alan
[Charles, Ada, Grace, Alan, Linus]
Charles
Linus
[Ada, Grace, Alan]

For a list, addLast() does the same as add(). addFirst() corresponds to add(0, …).

With an ArrayList, this comes at a price: addFirst() and removeFirst() shift all remaining elements in the internal array by one position – with a million elements, that is almost a million references per call. If you often insert or remove at the front, use an ArrayDeque instead of the ArrayList. It stores its elements in a ring buffer and shifts no elements when inserting or removing at the front.

Empty Collections

With an empty collection, getFirst(), getLast(), removeFirst(), and removeLast() throw a NoSuchElementException. This also applies to lists, where get(0) throws a different exception:

List<String> empty = new ArrayList<>();

try {
  empty.get(0);
} catch (RuntimeException e) {
  System.out.println(e);
}

try {
  empty.getFirst();
} catch (RuntimeException e) {
  System.out.println(e);
}

java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
java.util.NoSuchElementException

SequencedCollection has no method that returns null for an empty collection. Deque has peekFirst() and peekLast() for that. With a list, you should check beforehand whether it is empty:

List<String> empty = new ArrayList<>();
String first = empty.isEmpty() ? null : empty.getFirst();
System.out.println(first);

null

Unmodifiable Collections

addFirst(), addLast(), removeFirst(), and removeLast() are optional operations. An unmodifiable collection – such as a list from List.of() – rejects them with an UnsupportedOperationException:

List<String> pioneers = List.of("Ada", "Grace", "Alan");
pioneers.addFirst("Charles");

Exception in thread "main" java.lang.UnsupportedOperationException
    at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:156)
    at java.base/java.util.ImmutableCollections$AbstractImmutableList.add(ImmutableCollections.java:272)
    at java.base/java.util.List.addFirst(List.java:799)

The stack trace shows how addFirst() works for a list: the default method in List calls add() with index 0, and the unmodifiable list rejects this call. getFirst(), getLast(), and reversed(), on the other hand, also work with unmodifiable collections.

reversed(): The Reverse Order as a View

The seventh SequencedCollection method, reversed(), returns the elements in reverse order – not as a copy but as a so-called view: an object without elements of its own that forwards every access to the original collection.

The following example creates such a view, then changes the original list, and then removes an element through the view:

List<String> pioneers = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
List<String> reversed = pioneers.reversed();
System.out.println(reversed);

pioneers.add("Linus");
System.out.println(reversed);

reversed.removeFirst();
System.out.println(pioneers);

[Alan, Grace, Ada]
[Linus, Alan, Grace, Ada]
[Ada, Grace, Alan]

The element “Linus”, which the program appended to the back of the original list, is at the front of the view. Conversely, removeFirst() on the view removes the last element of the original list.

Since reversed() copies no elements, creating the view costs the same regardless of the size of the list.

Iterating Backwards

Most often, you need reversed() to iterate over a collection backwards. With a list, up to Java 20, you did this with a ListIterator that you had to start at the end of the list:

List<String> pioneers = List.of("Ada", "Grace", "Alan");

ListIterator<String> iterator = pioneers.listIterator(pioneers.size());
while (iterator.hasPrevious()) {
  System.out.println(iterator.previous());
}

Since Java 21, a for-each loop over reversed() is enough:

List<String> pioneers = List.of("Ada", "Grace", "Alan");

for (String pioneer : pioneers.reversed()) {
  System.out.println(pioneer);
}

Both listings print the same:

Alan
Grace
Ada

You can also create a stream in reverse order this way:

List<String> pioneers = List.of("Ada", "Grace", "Alan");

List<String> upperCase = pioneers.reversed()
    .stream()
    .map(String::toUpperCase)
    .toList();
System.out.println(upperCase);

[ALAN, GRACE, ADA]

reversed() vs. Collections.reverse() and descendingSet()

Even before Java 21, there were some methods for the reverse order. The following table shows what they return and whether they change the original collection:

Call	Returns	Changes the original	Since
Collections.reverse(list)	nothing	yes	Java 1.2
navigableSet.descendingSet()	view	no	Java 6
navigableMap.descendingMap()	view	no	Java 6
deque.descendingIterator()	iterator	no	Java 6

Collections.reverse() reverses the list itself. For a TreeSet and a TreeMap, reversed() internally calls descendingSet() and descendingMap(), respectively.

The Special Case LinkedList

List.reversed() returns a List, Deque.reversed() a Deque – each interface overrides the method with its own return type. A class that implements both interfaces – List and Deque – must therefore choose a return type that is both a List and a Deque.

The following class implements both interfaces, but not the reversed() method. Up to Java 20, it compiled:

public abstract class ListDeque<E> extends AbstractList<E> implements Deque<E> {
}

Since Java 21, the compiler rejects it:

error: types Deque<E> and List<E> are incompatible;
  both define reversed(), but with unrelated return types

In the JDK, this affects the LinkedList class: it implements List and Deque and therefore overrides reversed() with the return type LinkedList:

LinkedList<String> pioneers = new LinkedList<>(List.of("Ada", "Grace", "Alan"));
LinkedList<String> reversed = pioneers.reversed();
System.out.println(reversed);

[Alan, Grace, Ada]

If you have a class of your own that implements List and Deque, you must also override reversed() when you migrate to Java 21 – like LinkedList, with your own class as the return type. You can find out more about the interfaces of LinkedList in the article about the Java LinkedList.

SequencedSet: LinkedHashSet and TreeSet

SequencedSet extends Set and SequencedCollection. It defines no further methods. It only overrides reversed() so that the returned view is a SequencedSet and not a general SequencedCollection.

LinkedHashSet: addFirst() and addLast() Move Elements

A set contains each element only once. So what happens if you use addFirst() or addLast() to insert an element that is already in the set? The answer: the LinkedHashSet moves it to the front or to the back, respectively. add(), on the other hand, leaves the order unchanged, as it did up to Java 20:

SequencedSet<String> tags =
    new LinkedHashSet<>(List.of("java", "collections", "api"));

tags.add("java");
System.out.println(tags);

tags.addLast("java");
System.out.println(tags);

tags.addFirst("api");
System.out.println(tags);

[java, collections, api]
[collections, api, java]
[api, collections, java]

add("java") changes nothing, because “java” is already in the set. addLast("java") moves “java” to the back, addFirst("api") moves “api” to the front.

TreeSet: No addFirst() and No addLast()

In a TreeSet, the sorting determines the position of each element. Reading, removing, and reversed() therefore work, but inserting at a specific position does not:

SortedSet<Integer> versions = new TreeSet<>(List.of(21, 17, 25));

System.out.println(versions.getFirst());
System.out.println(versions.getLast());
System.out.println(versions.reversed());

System.out.println(versions.removeFirst());
System.out.println(versions);

versions.addFirst(11);

17
25
[25, 21, 17]
17
[21, 25]
Exception in thread "main" java.lang.UnsupportedOperationException
    at java.base/java.util.TreeSet.addFirst(TreeSet.java:478)

getFirst() and getLast() return the same as the methods first() and last(), which SortedSet has had since Java 1.2. addFirst() and addLast() throw an UnsupportedOperationException for every SortedSet. According to JEP 431, SortedSet still belongs to the family of sequenced collections so that you can use a TreeSet wherever a SequencedCollection is expected – as with the printEnds() method above.

SequencedMap: LinkedHashMap and TreeMap

In the Collections Framework, maps have a hierarchy of their own. For maps with an encounter order, Java 21 introduces the SequencedMap interface. LinkedHashMap implements it directly, TreeMap via SortedMap.

SequencedMap defines the following methods:

• firstEntry() and lastEntry() return the first and the last entry of the map, respectively, and null for an empty map.
• pollFirstEntry() and pollLastEntry() remove the first and the last entry, respectively, and return it.
• putFirst(K, V) and putLast(K, V) insert an entry at the front and at the back, respectively. If the key already exists, they overwrite its value and move the entry to the front or to the back.
• reversed() returns a view of the map in reverse order.
• sequencedKeySet(), sequencedValues(), and sequencedEntrySet() return the keys, the values, and the entries, respectively, as a sequenced collection.

For TreeMap, firstEntry(), lastEntry(), pollFirstEntry(), and pollLastEntry() are not new – they have been in the NavigableMap interface since Java 6. They are new for LinkedHashMap.

Example: Recently Opened Files

A typical use case for putLast() in a map is a list of recently opened files like the one many editors display. The following method open() stores how often each file was opened. With putLast(), it moves the file to the end of the map, and if the map has more than three entries, it removes the oldest one with pollFirstEntry():

static void open(SequencedMap<String, Integer> recentFiles, String file) {
  int count = recentFiles.getOrDefault(file, 0);
  recentFiles.putLast(file, count + 1);
  if (recentFiles.size() > 3) {
    recentFiles.pollFirstEntry();
  }
}

The following program opens four files one after the other, pom.xml twice, and prints the map after opening each file:

SequencedMap<String, Integer> recentFiles = new LinkedHashMap<>();
List<String> files =
    List.of("pom.xml", "Main.java", "README.md", "pom.xml", "Test.java");
for (String file : files) {
  open(recentFiles, file);
  System.out.println(file + " opened --> " + recentFiles);
}

System.out.println("lastEntry() = " + recentFiles.lastEntry());
System.out.println("sequencedKeySet().reversed() = "
    + recentFiles.sequencedKeySet().reversed());

pom.xml opened --> {pom.xml=1}
Main.java opened --> {pom.xml=1, Main.java=1}
README.md opened --> {pom.xml=1, Main.java=1, README.md=1}
pom.xml opened --> {Main.java=1, README.md=1, pom.xml=2}
Test.java opened --> {README.md=1, pom.xml=2, Test.java=1}
lastEntry() = Test.java=1
sequencedKeySet().reversed() = [Test.java, pom.xml, README.md]

The fourth line shows the second opening of pom.xml: putLast() increments the counter to 2 and moves the entry behind README.md. After that, Main.java is at the front. When Test.java is opened, the map has four entries, and pollFirstEntry() removes Main.java – this is what the fifth line shows. lastEntry() returns the most recently opened file, and sequencedKeySet().reversed() returns the file names from the most recent to the oldest.

With put() instead of putLast(), pom.xml would stay in its position when opened the second time. The following example shows this:

SequencedMap<String, Integer> recentFiles = new LinkedHashMap<>();
recentFiles.put("pom.xml", 1);
recentFiles.put("Main.java", 1);

recentFiles.put("pom.xml", 2);
System.out.println(recentFiles);

recentFiles.putLast("pom.xml", 3);
System.out.println(recentFiles);

{pom.xml=2, Main.java=1}
{Main.java=1, pom.xml=3}

A TreeMap rejects putFirst() and putLast(), because, as with the TreeSet, the sorting determines the position – here, that of the keys:

SequencedMap<Integer, String> releases =
    new TreeMap<>(Map.of(21, "2023", 17, "2021"));
System.out.println(releases.firstEntry());
releases.putFirst(11, "2018");

17=2021
Exception in thread "main" java.lang.UnsupportedOperationException
    at java.base/java.util.TreeMap.putFirst(TreeMap.java:322)

Why sequencedKeySet() and Not keySet()?

You might expect keySet() of a LinkedHashMap to return a SequencedSet since Java 21. However, the return type of keySet() is still Set, and Set has no getLast():

LinkedHashMap<String, Integer> recentFiles = new LinkedHashMap<>();
recentFiles.put("pom.xml", 1);
System.out.println(recentFiles.keySet().getLast());

error: cannot find symbol
  symbol:   method getLast()
  location: interface Set<String>

In an earlier version of JEP 431, SequencedMap overrode keySet(), values(), and entrySet() with the sequenced types as return types. According to the JEP, however, this would have invalidated every existing subclass of, e.g., LinkedHashMap: a subclass that overrides keySet() with the return type Set would no longer have compiled.

That is why there are the three new methods with the prefix sequenced: sequencedKeySet(), sequencedValues(), and sequencedEntrySet(). The authors of JEP 431 suspect that NavigableMap got the navigableKeySet() method in Java 6 for the same reason, instead of overriding keySet().

Unmodifiable Views from the Collections Class

For the three new interfaces, the Collections class got four new methods:

• unmodifiableSequencedCollection(), unmodifiableSequencedSet(), and unmodifiableSequencedMap() return an unmodifiable view of a SequencedCollection, a SequencedSet, and a SequencedMap, respectively – analogous to unmodifiableList() and the other unmodifiable methods that have existed since Java 1.2.
• newSequencedSetFromMap() returns a SequencedSet that stores its elements as keys of the given SequencedMap – analogous to newSetFromMap().

Reading methods such as getLast() and reversed() work on an unmodifiable view; modifying methods throw an UnsupportedOperationException:

List<String> pioneers = new ArrayList<>(List.of("Ada", "Grace"));
SequencedCollection<String> view =
    Collections.unmodifiableSequencedCollection(pioneers);

System.out.println(view.getLast());
System.out.println(view.reversed());
view.removeLast();

Grace
[Grace, Ada]
Exception in thread "main" java.lang.UnsupportedOperationException

Before and After

The following table compares the code up to Java 20 with the code since Java 21 for the most common tasks:

Task	Up to Java 20	Since Java 21
first element of a list	list.get(0)	list.getFirst()
last element of a list	list.get(list.size() - 1)	list.getLast()
first element of a LinkedHashSet	set.iterator().next()	set.getFirst()
last element of a LinkedHashSet	loop over all elements	set.getLast()
iterate over a list backwards	ListIterator from the end	list.reversed()
oldest entry of a LinkedHashMap	map.entrySet().iterator().next()	map.firstEntry()
most recent entry of a LinkedHashMap	loop over all entries	map.lastEntry()
move an entry to the end	map.remove(k), map.put(k, v)	map.putLast(k, v)

Pitfalls

reversed() Is Not a Copy

Because reversed() returns a view, it changes along with the original collection. If you store it as a snapshot and then clear the collection, the view is empty, too:

List<String> pioneers = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
List<String> backwards = pioneers.reversed();
pioneers.clear();
System.out.println(backwards);

[]

If you need a copy in reverse order, copy the view:

List<String> pioneers = new ArrayList<>(List.of("Ada", "Grace", "Alan"));
List<String> backwards = new ArrayList<>(pioneers.reversed());
pioneers.clear();
System.out.println(backwards);

[Alan, Grace, Ada]

The connection between the view and the original collection also works in the other direction: if you change the view, you also change the original collection. In the example further above, removeFirst() on the view removed the last element of the original list.

firstEntry() Returns an Unmodifiable Entry

firstEntry() and lastEntry() return an unmodifiable copy of the entry. You cannot change its value through this copy:

SequencedMap<String, Integer> recentFiles = new LinkedHashMap<>();
recentFiles.put("pom.xml", 1);
recentFiles.firstEntry().setValue(2);

Exception in thread "main" java.lang.UnsupportedOperationException: not supported

The entries of sequencedEntrySet(), on the other hand, are backed by the map, just like those of entrySet(). You can change the value through them:

SequencedMap<String, Integer> recentFiles = new LinkedHashMap<>();
recentFiles.put("pom.xml", 1);
recentFiles.sequencedEntrySet().getFirst().setValue(2);
System.out.println(recentFiles);

{pom.xml=2}

Empty Map: null Instead of an Exception

With an empty collection, getFirst() and getLast() throw a NoSuchElementException. With an empty map, on the other hand, firstEntry(), lastEntry(), pollFirstEntry(), and pollLastEntry() return null, like the methods of the same name that NavigableMap has had since Java 6. The three views of the map – sequencedKeySet(), sequencedValues(), and sequencedEntrySet() – are, in turn, sequenced collections and throw a NoSuchElementException for an empty map:

SequencedMap<String, Integer> recentFiles = new LinkedHashMap<>();

System.out.println(recentFiles.firstEntry());

try {
  recentFiles.sequencedKeySet().getFirst();
} catch (RuntimeException e) {
  System.out.println(e);
}

null
java.util.NoSuchElementException

Therefore, check the result of firstEntry() and lastEntry() for null before you call getKey() or getValue().

Summary

Since Java 21, all collections with a defined order – lists, deques, LinkedHashSet, TreeSet, and their counterparts among the maps – have shared methods for the first and the last element and for the reverse order. They come from the interfaces SequencedCollection, SequencedSet, and SequencedMap, which were introduced by JEP 431.

getFirst() and getLast() throw a NoSuchElementException for an empty collection; firstEntry() and lastEntry() return null for an empty map. reversed() returns a view, not a copy. A LinkedHashSet and a LinkedHashMap move an existing element on addFirst() and addLast() or putFirst() and putLast(), respectively. TreeSet and TreeMap reject these methods because the sorting determines the position.

Four recommendations for your code:

• Replace list.get(0) and list.get(list.size() - 1) with getFirst() and getLast() – and iterate over collections backwards with reversed() instead of a ListIterator.
• Declare a parameter as SequencedCollection if your method needs an order but does not depend on a specific collection type.
• Copy the result of reversed() if you need a snapshot.
• Use an ArrayDeque instead of an ArrayList if you often insert or remove at the front.

You can find out which other new features Java 21 brought in the article about the Java 21 features. How Deque and Queue are related is explained in the article Queue vs. Deque.