The SequencedMap interface

A SequencedMap<K, V> is a map that remembers the exact order of its entries. Unlike the Map interface, which does not guarantee any specific order, a sequenced map combines standard key-value storage with features of a double-ended queue. We can use it to insert, access, or remove entries from either the beginning or the end of the sequence.

Motivation & use cases

Before Java 21, map ordering was limited to LinkedHashMap for insertion order and TreeMap for sorted order. Neither provided built-in methods for front-or-back operations. Developers often had to write complex workarounds to create things like Least Recently Used (LRU) caches, event logs, or history buffers.

SequencedMap solves this problem. It introduces sequence-sensitive operations, so you get predictable iteration and double-ended access without breaking the standard rules of Java maps.

The SequencedMap<K,V> interface

In the Java collection hierarchy, SequencedMap<K, V> is a direct subinterface of the standard Map<K, V> interface.

It serves as a parent interface for more specific map types, including SortedMap, NavigableMap, and ConcurrentNavigableMap. Some common implementations you will encounter are LinkedHashMap, TreeMap, and ConcurrentSkipListMap.

Because it extends Map, a SequencedMap follows the standard Map contract. For example, it ensures that every key is unique and that methods like equals() and hashCode() behave consistently. SequencedMap adds one major feature to these rules: a predictable iteration sequence. Inherited methods like forEach() or replaceAll() process entries in a strict, well-defined order.

Key API methods

The SequencedMap interface adds double-ended capabilities on top of the standard Map API. These include:

interface SequencedMap<K, V> extends Map<K, V> {
    // new methods
    // Positional insertion
    V putFirst(K k, V v);
    V putLast(K k, V v);
    // Sequenced views
    SequencedMap<K, V> reversed();
    SequencedSet<K> sequencedKeySet();
    SequencedCollection<V> sequencedValues();
    SequencedSet<Map.Entry<K, V>> sequencedEntrySet();

    // methods promoted from NavigableMap
    // Positional access and removal
    Map.Entry<K, V> firstEntry();
    Map.Entry<K, V> lastEntry();
    Map.Entry<K, V> pollFirstEntry();
    Map.Entry<K, V> pollLastEntry();
}

Below is a detailed breakdown of how to use each of these new methods:

• putFirst(K key, V value)։ This method inserts a new key-value mapping at the front of the map. If the key already exists, the map updates the value and moves the entire entry to the front of the sequence:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.put("a", 1);
map.put("b", 2);

// Output: {a=1, b=2}
System.out.println(map);

map.putFirst("b", 3);

// Output: {b=3, a=1}
System.out.println(map);

Implementation requirements: By default, this method throws an UnsupportedOperationException. This happens because not all map implementations support positional insertion. For example, TreeMap automatically sorts entries based on keys, making it impossible to force an entry to be "first". However, LinkedHashMap explicitly overrides this method to support it.

Returns: The previous value associated with the key, or null if there was none.

• putLast(K key, V value): This method inserts a new key-value mapping at the end of the map. If the key is already present, the map updates the value and moves the entry to the end of the sequence:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putFirst("first", 1);
map.putLast("last", 2);

// Output: {first=1, last=2}
System.out.println(map);

map.putLast("first", 10);

// Output: {last=2, first=10}
System.out.println(map);

Implementation requirements: Like putFirst(), the default implementation throws an UnsupportedOperationException unless a class explicitly supports positional insertion.

Returns: The previous value associated with the key, or null.

• firstEntry(): This method returns the first key-value pair in the map according to its encounter order:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("first", 1);
map.putLast("second", 2);

Map.Entry<String, Integer> first = map.firstEntry();

// Output: first: 1
System.out.println(first.getKey() + ": " + first.getValue());

Implementation requirements: The default implementation retrieves an iterator from the map’s entrySet(). It returns an unmodifiable snapshot of the entry. This ensures you cannot accidentally alter the map's state directly through the returned object.

Returns: The first mapping, or null if the map is empty.

• lastEntry(): This method returns the last key-value pair in the map:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("first", 1);
map.putLast("second", 2);

Map.Entry<String, Integer> last = map.lastEntry();

// Output: second: 2
System.out.println(last.getKey() + ": " + last.getValue());

Implementation requirements: It obtains an iterator from the reversed view of the map’s entrySet() and returns an unmodifiable snapshot of the first element it finds.

Returns: The last mapping, or null if empty.

• pollFirstEntry(): This method removes and returns the first key-value pair in the map. Unlike firstEntry(), which only inspects the element, this method actually modifies the map:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("first", 1);
map.putLast("second", 2);

Map.Entry<String, Integer> removedFirst = map.pollFirstEntry();

// Output: Removed: first=1
System.out.println("Removed: " + removedFirst);

// Output: Remaining: {second=2}
System.out.println("Remaining: " + map);

Implementation requirements: It retrieves an iterator from the map’s entrySet(), removes the first element from the underlying map, and returns an unmodifiable snapshot of it.

Returns: The removed first entry, or null if empty.

• pollLastEntry(): This method removes and returns the last key-value pair in the map:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("first", 1);
map.putLast("last", 2);

Map.Entry<String, Integer> removedLast = map.pollLastEntry();

// Output: Removed: last=2
System.out.println("Removed: " + removedLast);

// Output: Remaining: {first=1}
System.out.println("Remaining: " + map);

Implementation requirements: It retrieves an iterator from the reversed view of the map’s entrySet(), removes the element, and returns an unmodifiable snapshot.

Returns: The removed last entry, or null if empty.

• sequencedKeySet(), sequencedValues(), sequencedEntrySet(): These three methods return sequenced views of the map's keys (SequencedSet<K>), values (SequencedCollection<V>), and entries (SequencedSet<Map.Entry<K,V>>):

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("first", 1);
map.putLast("second", 2);

// Output: Keys: first, second
System.out.print("Keys: ");
for (String key : map.sequencedKeySet()) {
    System.out.print(key + ", ");
}

// Output: Values: 1, 2
System.out.print("\nValues: ");
for (Integer val : map.sequencedValues()) {
    System.out.print(val + ", ");
}

// Output: Entries: first=1, second=2
System.out.print("\nEntries: ");
for (var entry : map.sequencedEntrySet()) {
    System.out.print(entry.getKey() + "=" + entry.getValue() + ", ");
}

Implementation requirements: These views are partially immutable. If you call add() or addAll() on them, they will throw an UnsupportedOperationException. This prevents you from adding elements directly through the view. However, you can remove elements, and those changes will reflect directly on the underlying map.

Returns: A sequenced view consistent with the map's encounter order.

• reversed(): This method returns a reverse-ordered view of the map. The encounter order is the exact inverse of the original map:

SequencedMap<String, Integer> map = new LinkedHashMap<>();
map.putLast("first", 1);
map.putLast("second", 2);

SequencedMap<String, Integer> reverseMap = map.reversed();

// Output: second=2, first=1
for (var entry : reverseMap.sequencedEntrySet()) {
    System.out.print(entry.getKey() + "=" + entry.getValue() + ", ");
}

Implementation requirements: The method returns a live view, not a copy. If the implementation allows modifications through the reversed view, those changes apply directly to the underlying map. Likewise, updates to the original map are immediately visible in the reversed view.

Returns: A reverse-ordered view of the map.

• Collections.unmodifiableSequencedMap(SequencedMap<K,V> map): This utility method returns an unmodifiable view of a specific SequencedMap:

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

SequencedMap<String, Integer> readOnlyMap = Collections.unmodifiableSequencedMap(map);

// Reading works perfectly
// Output: A=1
System.out.println(readOnlyMap.firstEntry());

// This will throw an UnsupportedOperationException
readOnlyMap.putLast("C", 3);

Implementation requirements: It wraps the provided map in a view that blocks any structural modifications. If you call mutating methods like put(), remove(), or pollFirstEntry(), the program will throw an UnsupportedOperationException.

Returns: A read-only sequenced map view.

Iteration and traversal

Traversing elements in both forward and reverse order is straightforward. You do not need to use backwards loops or convert the map to an array.

By leveraging sequencedEntrySet(), sequencedKeySet(), and the reversed() view, you can use standard for-each loops to iterate over your data:

import java.util.SequencedMap;
import java.util.LinkedHashMap;

public class IterationDemo {
    public static void main(String[] args) {
        SequencedMap<String, Integer> map = new LinkedHashMap<>();
        map.putLast("A", 1);
        map.putLast("B", 2);
        map.putLast("C", 3);

        // Output: Forward order: A=1 B=2 C=3 
        System.out.print("Forward order: ");
        for (var entry : map.sequencedEntrySet()) {
            System.out.print(entry.getKey() + "=" + entry.getValue() + " ");
        }

        // Output: Reverse order: C=3 B=2 A=1 
        System.out.print("\nReverse order: ");
        for (var entry : map.reversed().sequencedEntrySet()) {
            System.out.print(entry.getKey() + "=" + entry.getValue() + " ");
        }

        // Output: Keys in reverse: C B A 
        System.out.print("\nKeys in reverse: ");
        for (var key : map.reversed().sequencedKeySet()) {
            System.out.print(key + " ");
        }
    }
}

Practical code example

Let's see how we can use a SequencedMap to manage a dynamic task list. We want to process items based on urgency. The workflow operates as follows:

1. Add new standard tasks to the back of the map using putLast().

2. Add highly urgent tasks directly to the front of the map using putFirst().

3. Inspect the current highest-priority task using firstEntry().

4. Complete and remove the task from the front using pollFirstEntry().

import java.util.SequencedMap;
import java.util.LinkedHashMap;

public class TaskPriorityExample {
    public static void main(String[] args) {
        SequencedMap<String, String> tasks = new LinkedHashMap<>();

        // 1. Add standard tasks to the back
        tasks.putLast("TASK-1", "Write documentation");
        tasks.putLast("TASK-2", "Implement new feature");
        
        // 2. Add an urgent task to the front
        tasks.putFirst("BUG-99", "Fix critical production issue");

        System.out.println("Current tasks:");
        for (var entry : tasks.sequencedEntrySet()) {
            System.out.println("- " + entry.getKey() + ": " + entry.getValue());
        }

        // 3. Inspect the highest priority task
        var currentTask = tasks.firstEntry();
        System.out.println("\nNext to process: " + currentTask.getKey());

        // 4. Complete and remove the task
        tasks.pollFirstEntry();
        System.out.println("Completed: " + currentTask.getKey());

        System.out.println("\nRemaining tasks:");
        for (var key : tasks.sequencedKeySet()) {
            System.out.println("- " + key);
        }
    }
}

Performance characteristics

Since SequencedMap is an interface, its performance depends entirely on the backing implementation. It inherits the time and space complexity of its underlying class.

Time complexity

Methods like putFirst(), putLast(), firstEntry(), and pollFirstEntry() typically run in constant time $O(1)$ when using a linked-entry implementation like LinkedHashMap. The entries are internally linked in order, allowing immediate access to the head or tail.

However, in tree-based implementations like TreeMap, positional operations require navigating the tree structure. This results in logarithmic time complexity $O(\log n)$ due to search and re-balancing operations. Creating a reversed() view is an $O(1)$ operation across implementations, though traversing that view still takes $O(n)$ time.

Space overhead

The space overhead in classes like LinkedHashMap comes from the additional pointers maintained internally to keep track of the forward and backward encounter order. This generally adds an $O(1)$ memory overhead per entry. This design is identical to how LinkedHashMap functioned prior to Java 21, so using the SequencedMap interface introduces no unexpected memory overhead.

Conclusion

SequencedMap brings practical, order-sensitive features to Java maps. By providing standard methods for double-ended insertion, retrieval, and reverse traversal, it simplifies ordered collections. Whether you use a LinkedHashMap for fast positional updates or a TreeMap for sorted navigation, SequencedMap helps you write cleaner, more readable code without relying on complex workarounds.