Sequenced collections

suggest change

Many Java collections keep their elements in a defined order: a List, a Deque, a LinkedHashSet, a TreeSet, a LinkedHashMap. Before Java 21 there was no common type for "a collection with an order", and each class had its own way of getting the first or last element or of walking it backwards. Getting the last element of a LinkedHashSet meant iterating over all of it.

Java 21 added three interfaces (JEP 431) that fix this:

The existing interfaces were retrofitted into this hierarchy: List and Deque extend SequencedCollection, SortedSet and LinkedHashSet are SequencedSets, and SortedMap and LinkedHashMap are SequencedMaps. All new methods are default methods, so your own List or Deque implementations get them for free.

The examples are single files you run with java Example.java. Output is from JDK 25. Each section shows the old idiom next to the new method that replaces it.

Which collections are sequenced

import java.util.*;
import java.util.concurrent.*;

public class WhichAreSequenced {
    static void check(Object o) {
        String kind = o instanceof SequencedMap<?, ?> ? "SequencedMap"
                : o instanceof SequencedSet<?> ? "SequencedSet"
                : o instanceof SequencedCollection<?> ? "SequencedCollection"
                : "-";
        System.out.printf("%-22s %s%n", o.getClass().getSimpleName(), kind);
    }

    public static void main(String[] args) {
        check(new ArrayList<>());
        check(new LinkedList<>());
        check(new ArrayDeque<>());
        check(List.of(1, 2));
        check(new LinkedHashSet<>());
        check(new TreeSet<>());
        check(new HashSet<>());
        check(new PriorityQueue<>());
        check(new LinkedHashMap<>());
        check(new TreeMap<>());
        check(new ConcurrentSkipListMap<>());
        check(new HashMap<>());
        check(Map.of(1, 2));
    }
}
ArrayList              SequencedCollection
LinkedList             SequencedCollection
ArrayDeque             SequencedCollection
List12                 SequencedCollection
LinkedHashSet          SequencedSet
TreeSet                SequencedSet
HashSet                -
PriorityQueue          -
LinkedHashMap          SequencedMap
TreeMap                SequencedMap
ConcurrentSkipListMap  SequencedMap
HashMap                -
Map1                   -

HashSet, HashMap and Map.of(...) have no defined order, so they are not sequenced. PriorityQueue hands out elements in priority order, but its iteration order is unspecified, so it isn't sequenced either. List.of(...) returns an immutable list, which is still a List and therefore a SequencedCollection.

getFirst and getLast

Here's how you got the first and last element of four ordered collections before Java 21, and how you do it now:

import java.util.*;

public class FirstAndLast {
    public static void main(String[] args) {
        List<String> list = List.of("a", "b", "c");
        Deque<String> deque = new ArrayDeque<>(list);
        LinkedHashSet<String> linkedSet = new LinkedHashSet<>(list);
        SortedSet<String> sortedSet = new TreeSet<>(list);

        // Before Java 21: a different idiom for each type
        String first1 = list.get(0);
        String last1 = list.get(list.size() - 1);
        String first2 = deque.getFirst();
        String last2 = deque.getLast();
        String first3 = linkedSet.iterator().next();
        String last3 = null;
        for (String s : linkedSet) last3 = s;   // walk the whole set
        String first4 = sortedSet.first();
        String last4 = sortedSet.last();
        System.out.println(first1 + last1 + " " + first2 + last2 + " "
                + first3 + last3 + " " + first4 + last4);

        // Java 21: the same two methods everywhere
        System.out.println(list.getFirst() + list.getLast() + " "
                + deque.getFirst() + deque.getLast() + " "
                + linkedSet.getFirst() + linkedSet.getLast() + " "
                + sortedSet.getFirst() + sortedSet.getLast());
    }
}
ac ac ac ac
ac ac ac ac

list.get(list.size() - 1) is easy to get wrong, and LinkedHashSet had no way to reach its last element other than iterating through the whole set. Now it's getFirst() and getLast() on all of them. Deque already had these two methods, and SortedSet has first() and last(), which still work.

On an empty collection both methods throw NoSuchElementException, even on a List, where get(0) throws IndexOutOfBoundsException:

import java.util.*;

public class EmptyFirst {
    public static void main(String[] args) {
        List<String> empty = new ArrayList<>();
        try {
            empty.get(0);
        } catch (RuntimeException e) {
            System.out.println("get(0):     " + e);
        }
        try {
            empty.getFirst();
        } catch (RuntimeException e) {
            System.out.println("getFirst(): " + e);
        }
        String first = empty.isEmpty() ? "(none)" : empty.getFirst();
        System.out.println(first);
        System.out.println(empty.stream().findFirst().orElse("(none)"));
    }
}
get(0):     java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
getFirst(): java.util.NoSuchElementException
(none)
(none)

There's no Optional-returning variant. Check isEmpty() first, or use stream().findFirst() when an Optional fits better.

addFirst, addLast, removeFirst, removeLast

The same naming is used for adding and removing at both ends:

import java.util.*;

public class AddRemove {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("b", "c"));
        list.addFirst("a");            // was: list.add(0, "a")
        list.addLast("d");             // same as list.add("d")
        System.out.println(list);
        String removed = list.removeLast();   // was: list.remove(list.size() - 1)
        System.out.println(removed + " " + list);
        list.removeFirst();            // was: list.remove(0)
        System.out.println(list);

        LinkedHashSet<String> set = new LinkedHashSet<>(List.of("x", "y", "z"));
        set.addFirst("w");
        set.removeLast();
        System.out.println(set);
    }
}
[a, b, c, d]
d [a, b, c]
[b, c]
[w, x, y]

removeFirst() and removeLast() return the removed element. On an ArrayList, addFirst and removeFirst shift all the other elements, so they are O(n) just like add(0, x) and remove(0). If you add and remove at the front a lot, use an ArrayDeque (see Deque).

Repositioning in a LinkedHashSet

A set can't hold duplicates, so for a LinkedHashSet addFirst and addLast have a useful extra behavior: if the element is already present, it's moved to the front or to the end. Plain add leaves an existing element where it is:

import java.util.*;

public class Reposition {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>(List.of("a", "b", "c"));
        set.add("a");          // already present: nothing changes
        System.out.println(set);
        set.addFirst("c");     // already present: moved to the front
        System.out.println(set);
        set.addLast("c");      // and back to the end
        System.out.println(set);
    }
}
[a, b, c]
[c, a, b]
[a, b, c]

Before Java 21 you had to remove the element and add it again, and there was no way at all to put an element at the front of a LinkedHashSet without rebuilding it.

Operations that throw UnsupportedOperationException

The new methods are part of interfaces that every ordered collection implements, but not every collection can support all of them:

import java.util.*;

public class Unsupported {
    static void attempt(String what, Runnable r) {
        try {
            r.run();
            System.out.println(what + ": ok");
        } catch (RuntimeException e) {
            System.out.println(what + ": " + e.getClass().getSimpleName());
        }
    }

    public static void main(String[] args) {
        TreeSet<Integer> sorted = new TreeSet<>(List.of(10, 20, 30));
        attempt("TreeSet.addFirst", () -> sorted.addFirst(5));
        attempt("TreeSet.removeFirst", () -> sorted.removeFirst());
        System.out.println(sorted);

        List<Integer> immutable = List.of(1, 2, 3);
        attempt("List.of(...).getLast", () -> immutable.getLast());
        attempt("List.of(...).addFirst", () -> immutable.addFirst(0));

        List<Integer> fixed = Arrays.asList(1, 2, 3);
        attempt("Arrays.asList(...).removeLast", () -> fixed.removeLast());
    }
}
TreeSet.addFirst: UnsupportedOperationException
TreeSet.removeFirst: ok
[20, 30]
List.of(...).getLast: ok
List.of(...).addFirst: UnsupportedOperationException
Arrays.asList(...).removeLast: UnsupportedOperationException

reversed()

reversed() returns a view of the collection in reverse order. It doesn't copy anything, so it's O(1) no matter how large the collection is:

import java.util.*;
import java.util.stream.*;

public class Reversed {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));

        // Before Java 21: copy and reverse, or a ListIterator walking backwards
        List<Integer> copy = new ArrayList<>(nums);
        Collections.reverse(copy);
        System.out.println(copy);
        for (ListIterator<Integer> it = nums.listIterator(nums.size()); it.hasPrevious(); ) {
            System.out.print(it.previous() + " ");
        }
        System.out.println();

        // Java 21: a reversed view, no copying
        for (int n : nums.reversed()) {
            System.out.print(n + " ");
        }
        System.out.println();
        System.out.println(nums.reversed().stream()
                .map(String::valueOf)
                .collect(Collectors.joining(",")));

        LinkedHashSet<String> set = new LinkedHashSet<>(List.of("a", "b", "c"));
        System.out.println(set.reversed());
        Deque<String> deque = new ArrayDeque<>(List.of("x", "y", "z"));
        System.out.println(deque.reversed().peek());
    }
}
[4, 3, 2, 1]
4 3 2 1
4 3 2 1
4,3,2,1
[c, b, a]
z

Collections.reverse(list) reverses a list in place, so to iterate backwards without changing the original you had to copy it first, or use a ListIterator starting from the end. LinkedHashSet had no way to iterate in reverse at all. With reversed() you can use a for-each loop, a stream, or peek() on a reversed deque.

The view is live and writable. Changes to the original show up in the view, and writes to the view (if the original supports them) go to the original:

import java.util.*;

public class ReversedView {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("a", "b", "c"));
        List<String> rev = list.reversed();
        System.out.println(rev);

        list.add("d");                 // changes show up in the view
        System.out.println(rev);

        rev.addFirst("z");             // first of the view is last of the list
        rev.set(1, "D");               // index 1 of the view
        System.out.println(list);

        List<String> snapshot = List.copyOf(list.reversed());
        list.clear();
        System.out.println(snapshot + " " + rev);
    }
}
[c, b, a]
[d, c, b, a]
[a, b, c, D, z]
[z, D, c, b, a] []

Calling addFirst on the reversed view adds to the end of the original. If you need an independent reversed copy, copy the view with List.copyOf or new ArrayList<>(...).

reversed() returns the most specific type it can: a List for a List, a Deque for a Deque, and a NavigableSet or NavigableMap for TreeSet and TreeMap, where it's equivalent to descendingSet() and descendingMap():

import java.util.*;

public class ReversedTypes {
    public static void main(String[] args) {
        List<Integer> list = List.of(1, 2, 3, 4, 5);
        List<Integer> revList = list.reversed();             // still a List
        System.out.println(revList.subList(0, 2) + " " + revList.indexOf(5));

        TreeSet<Integer> tree = new TreeSet<>(list);
        NavigableSet<Integer> revTree = tree.reversed();     // same as descendingSet()
        System.out.println(revTree.headSet(3) + " " + revTree.ceiling(3) + " " + tree.descendingSet().equals(revTree));

        TreeMap<String, Integer> map = new TreeMap<>(Map.of("a", 1, "b", 2, "c", 3));
        NavigableMap<String, Integer> revMap = map.reversed(); // same as descendingMap()
        System.out.println(revMap.firstKey() + " " + revMap.headMap("b"));
    }
}
[5, 4] 0
[5, 4] 3 true
c {c=3}

Everything in a reversed view is reversed: indexes, subList, headSet, ceiling. revTree.headSet(3) returns the elements that come before 3 in descending order, which are 5 and 4.

SequencedMap

LinkedHashMap, TreeMap and the other SortedMaps (like ConcurrentSkipListMap) are SequencedMaps. TreeMap already had firstEntry, pollFirstEntry and friends through NavigableMap; Java 21 moved them up to SequencedMap so that LinkedHashMap has them too.

firstEntry, lastEntry, pollFirstEntry, pollLastEntry

import java.util.*;

public class MapEnds {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> scores = new LinkedHashMap<>();
        scores.put("ann", 90);
        scores.put("bob", 72);
        scores.put("cid", 85);

        // Before Java 21
        Map.Entry<String, Integer> oldFirst = scores.entrySet().iterator().next();
        Map.Entry<String, Integer> oldLast = null;
        for (var e : scores.entrySet()) oldLast = e;
        System.out.println(oldFirst + " " + oldLast);

        // Java 21
        System.out.println(scores.firstEntry() + " " + scores.lastEntry());

        Map.Entry<String, Integer> polled = scores.pollFirstEntry();
        System.out.println(polled + " " + scores);

        try {
            scores.firstEntry().setValue(0);
        } catch (UnsupportedOperationException e) {
            System.out.println("firstEntry() is a snapshot: " + e.getClass().getSimpleName());
        }
        scores.sequencedEntrySet().getFirst().setValue(0);
        System.out.println(scores);
    }
}
ann=90 cid=85
ann=90 cid=85
ann=90 {bob=72, cid=85}
firstEntry() is a snapshot: UnsupportedOperationException
{bob=0, cid=85}

putFirst and putLast

LinkedHashMap keeps keys in insertion order, and put on an existing key doesn't change its position. putFirst and putLast insert at, or move to, either end:

import java.util.*;

public class PutFirst {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        map.put("b", 2);
        map.put("c", 3);
        map.putFirst("a", 1);
        System.out.println(map);

        map.put("a", 10);        // existing key: value replaced, position kept
        System.out.println(map);
        map.putLast("a", 100);   // existing key: value replaced and moved to the end
        System.out.println(map);

        TreeMap<String, Integer> tree = new TreeMap<>(map);
        try {
            tree.putFirst("zzz", 0);
        } catch (UnsupportedOperationException e) {
            System.out.println("TreeMap.putFirst: " + e.getClass().getSimpleName());
        }
    }
}
{a=1, b=2, c=3}
{a=10, b=2, c=3}
{b=2, c=3, a=100}
TreeMap.putFirst: UnsupportedOperationException

As with SortedSet.addFirst, a sorted map can't put a key at an arbitrary position, so TreeMap.putFirst and putLast throw UnsupportedOperationException.

Sequenced views and reversed maps

keySet(), values() and entrySet() return plain Set and Collection types even on a LinkedHashMap. The sequenced versions return SequencedSet and SequencedCollection, so you get getFirst, reversed() and the rest:

import java.util.*;

public class MapViews {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);

        SequencedSet<String> keys = map.sequencedKeySet();
        SequencedCollection<Integer> values = map.sequencedValues();
        SequencedSet<Map.Entry<String, Integer>> entries = map.sequencedEntrySet();
        System.out.println(keys.getLast() + " " + values.getFirst() + " " + entries.getLast());

        // Views write through to the map
        keys.removeFirst();
        System.out.println(map);

        // A reversed map, also a view
        SequencedMap<String, Integer> rev = map.reversed();
        System.out.println(rev);
        rev.forEach((k, v) -> System.out.print(k + "=" + v + " "));
        System.out.println();
        rev.putFirst("four", 4);    // first of the reversed map = last of the map
        System.out.println(map);
        System.out.println(map.sequencedKeySet().reversed());
    }
}
three 1 three=3
{two=2, three=3}
{three=3, two=2}
three=3 two=2
{two=2, three=3, four=4}
[four, three, two]

Like the collection views, reversed() on a map is a live view that writes through: putFirst on the reversed map puts the key at the end of the original.

An LRU cache

A LinkedHashMap created with accessOrder = true moves an entry to the end every time it's read, so the first entry is always the least recently used one. firstEntry() and pollFirstEntry() make it easy to inspect and evict it:

import java.util.*;

public class LruCache {
    public static void main(String[] args) {
        // accessOrder = true: get() moves an entry to the end
        LinkedHashMap<String, String> cache = new LinkedHashMap<>(16, 0.75f, true);
        cache.put("a", "A");
        cache.put("b", "B");
        cache.put("c", "C");
        cache.get("a");
        System.out.println(cache);
        System.out.println("eldest: " + cache.firstEntry().getKey()
                + ", newest: " + cache.lastEntry().getKey());

        Map.Entry<String, String> evicted = cache.pollFirstEntry();
        System.out.println("evicted " + evicted + " -> " + cache);
    }
}
{b=B, c=C, a=A}
eldest: b, newest: a
evicted b=B -> {c=C, a=A}

For a cache that evicts automatically, override removeEldestEntry, as shown in Java LinkedHashMap class and Caching.

Example: a list of recently opened files

addFirst moving an existing element to the front, together with removeLast, makes a "recent files" list a few lines of code:

import java.util.*;

public class RecentFiles {
    private final SequencedSet<String> files = new LinkedHashSet<>();
    private final int max;

    RecentFiles(int max) {
        this.max = max;
    }

    void opened(String file) {
        files.addFirst(file);          // new or not, it becomes the most recent
        if (files.size() > max) {
            files.removeLast();        // drop the least recent
        }
    }

    SequencedSet<String> view() {
        return Collections.unmodifiableSequencedSet(files);
    }

    public static void main(String[] args) {
        RecentFiles recent = new RecentFiles(3);
        for (String f : List.of("a.txt", "b.txt", "c.txt", "a.txt", "d.txt")) {
            recent.opened(f);
            System.out.println(f + " -> " + recent.view());
        }
        SequencedSet<String> view = recent.view();
        System.out.println("most recent: " + view.getFirst()
                + ", oldest first: " + view.reversed());
        try {
            view.removeFirst();
        } catch (UnsupportedOperationException e) {
            System.out.println("view is read-only");
        }
    }
}
a.txt -> [a.txt]
b.txt -> [b.txt, a.txt]
c.txt -> [c.txt, b.txt, a.txt]
a.txt -> [a.txt, c.txt, b.txt]
d.txt -> [d.txt, a.txt, c.txt]
most recent: d.txt, oldest first: [c.txt, a.txt, d.txt]
view is read-only

Opening a.txt a second time moves it to the front instead of adding a duplicate. view() returns a read-only view, so callers can read the list but can't change it.

Unmodifiable sequenced views

Collections.unmodifiableCollection, unmodifiableSet and unmodifiableMap return types that are not sequenced, so wrapping a LinkedHashMap used to hide its order from the type system. Java 21 added Collections.unmodifiableSequencedCollection, unmodifiableSequencedSet and unmodifiableSequencedMap:

import java.util.*;

public class Unmodifiable {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> stock = new LinkedHashMap<>();
        stock.put("apples", 5);
        stock.put("pears", 2);

        // Collections.unmodifiableMap returns a plain Map: no firstEntry(), no reversed()
        Map<String, Integer> plain = Collections.unmodifiableMap(stock);
        System.out.println(plain instanceof SequencedMap);

        SequencedMap<String, Integer> view = Collections.unmodifiableSequencedMap(stock);
        System.out.println(view.firstEntry() + " " + view.reversed());
        try {
            view.pollFirstEntry();
        } catch (UnsupportedOperationException e) {
            System.out.println("pollFirstEntry: " + e.getClass().getSimpleName());
        }
        stock.put("plums", 7);           // the view follows the backing map
        System.out.println(view.lastEntry());
    }
}
false
apples=5 {pears=2, apples=5}
pollFirstEntry: UnsupportedOperationException
plums=7

These are views, not copies: they reflect later changes to the backing map. Reading methods work; every method that modifies the collection, including pollFirstEntry, throws.

Collections.newSequencedSetFromMap turns any SequencedMap into a SequencedSet. Combined with removeEldestEntry, it gives you a set that keeps only the most recent elements, for example to remember the last few message IDs you've processed:

import java.util.*;

public class BoundedSet {
    public static void main(String[] args) {
        // A LinkedHashMap that drops its eldest entry once it has more than 3
        SequencedMap<String, Boolean> map = new LinkedHashMap<>() {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Boolean> eldest) {
                return size() > 3;
            }
        };
        SequencedSet<String> seen = Collections.newSequencedSetFromMap(map);
        for (String id : List.of("m1", "m2", "m3", "m4", "m5")) {
            seen.add(id);
        }
        System.out.println(seen + " oldest=" + seen.getFirst());
    }
}
[m3, m4, m5] oldest=m3

Writing methods that accept any ordered collection

The main benefit for your own code is that you can now write one method that accepts any ordered collection. Before Java 21 you had to pick List (which excludes Deque and LinkedHashSet), or accept Collection and lose the ordering guarantee:

import java.util.*;

public class GenericApi {
    // Before Java 21 you needed List<T>, Deque<T> or a hand-written overload per type.
    static <T> String ends(SequencedCollection<T> items) {
        if (items.isEmpty()) {
            return "(empty)";
        }
        return items.getFirst() + ".." + items.getLast();
    }

    static <K, V> V newest(SequencedMap<K, V> map) {
        var last = map.lastEntry();
        return last == null ? null : last.getValue();
    }

    public static void main(String[] args) {
        System.out.println(ends(List.of(3, 1, 2)));
        System.out.println(ends(new ArrayDeque<>(List.of("x", "y"))));
        System.out.println(ends(new TreeSet<>(Set.of(3, 1, 2))));
        System.out.println(ends(new LinkedHashMap<>(Map.of("k", 1)).sequencedKeySet()));
        System.out.println(ends(List.of()));

        var events = new LinkedHashMap<Integer, String>();
        events.put(1, "start");
        events.put(2, "stop");
        System.out.println(newest(events) + " " + newest(new TreeMap<String, String>()));
        // ends(new HashSet<>(Set.of(1)));  // does not compile: HashSet has no order
    }
}
3..2
x..y
1..3
k..k
(empty)
stop null

The parameter type documents that the method depends on the order, and the compiler rejects collections that don't have one, like HashSet. Use SequencedCollection, SequencedSet or SequencedMap as a parameter type when the order matters, and keep returning concrete types like List where callers expect them.

Compatibility

The new methods were added to widely implemented interfaces, so code that already declares a method with the same name but a different return type no longer compiles. For example, a class that extends ArrayList and defines Optional<String> getFirst():

import java.util.*;

public class Compat {
    static class Names extends ArrayList<String> {
        public Optional<String> getFirst() {
            return isEmpty() ? Optional.empty() : Optional.of(get(0));
        }
    }
    public static void main(String[] args) {}
}
Compat.java:5: error: getFirst() in Names cannot implement getFirst() in List
        public Optional<String> getFirst() {
                                ^
  return type Optional<String> is not compatible with String
  where E is a type-variable:
    E extends Object declared in interface List
1 error

The fix is to rename the method. A similar clash can happen with a custom reversed() method on a collection class, or with a class that implements both List and Deque (like LinkedList), which must override reversed() to resolve the conflicting return types. LinkedList itself does this and returns a LinkedList.

Code that calls the new methods needs Java 21 or later. Kotlin has its own removeFirst() and removeLast() extension functions on MutableList. When Kotlin code is compiled against JDK 21 or later, those calls resolve to the new Java member methods instead, which throw NoSuchMethodError on Android versions before 15 because their runtime lacks them. Kotlin code for Android should use removeAt(0) and removeAt(list.lastIndex).

Summary

Related: Lists, Deque, LinkedHashMap, TreeMap and TreeSet.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents