skip to content

Which existing collection types now implement the Sequenced interfaces, and which do not?

level: middleimportance: should knowfreq 48%

answer

  1. Ordered → sequenced; hash-based → not
  2. List & Deque → SequencedCollection
  3. LinkedHashSet & Sorted/Navigable Set → SequencedSet
  4. LinkedHashMap & Sorted/Navigable Map → SequencedMap
  5. HashSet/HashMap excluded; Sorted* addFirst/Last throws UOE

basics

~10 s

Types with a defined order implement them: List (so ArrayList, LinkedList), Deque (ArrayDeque, LinkedList), LinkedHashSet, SortedSet/NavigableSet (TreeSet) are SequencedCollection/SequencedSet; LinkedHashMap and SortedMap/NavigableMap (TreeMap) are SequencedMap. Unordered types like HashSet and HashMap do not.

solid answer

~40 s

The retrofit follows encounter order. On the collection side: `List` now extends `SequencedCollection`, so `ArrayList` and `LinkedList` get the methods; `Deque` extends `SequencedCollection`, covering `ArrayDeque` and `LinkedList`; `LinkedHashSet` becomes a `SequencedSet`; and `SortedSet`/`NavigableSet` extend `SequencedSet`, so `TreeSet` qualifies. On the map side: `LinkedHashMap` becomes a `SequencedMap`, and `SortedMap`/`NavigableMap` extend `SequencedMap`, covering `TreeMap`. The unordered hash-based types — `HashSet` and `HashMap` — deliberately do **not** implement these interfaces, because they have no defined encounter order, so first/last/reversed would be meaningless. A subtle point: a `SortedSet`'s `reversed()` returns a view ordered by the reverse comparator, and its `addFirst`/`addLast` throw `UnsupportedOperationException` because position is dictated by the sort order, not by you.

go deeper

for a junior

Can say ordered collections like List and LinkedHashSet got the methods and HashSet/HashMap did not.

for a middle

Maps each concrete type to the right interface and knows hash-based types are excluded.

for a senior

Explains the SortedSet/SortedMap UnsupportedOperationException for addFirst/addLast and why position-by-comparator forbids it.

for a principal

Reasons about the interface-injection design across the hierarchy, immutable-list edge cases, and the contract guarantees an API can rely on when accepting a SequencedCollection.

## The retrofit principle JEP 431 added the `Sequenced*` interfaces and then **wired them into the existing collection hierarchy** for every type that already had a *defined encounter order* (a deterministic iteration order). Types whose order is arbitrary (hash-based) were left out on purpose. ## Collection side (SequencedCollection / SequencedSet) - **`List`** → now `extends SequencedCollection`. Concrete: `ArrayList`, `LinkedList`, `Vector`, `CopyOnWriteArrayList`, and the lists returned by `List.of(...)` / `Arrays.asList(...)` (immutable/fixed-size ones throw on mutating end-ops). For a `List`, `getFirst()` ≡ `get(0)`, `getLast()` ≡ `get(size()-1)`. - **`Deque`** → now `extends SequencedCollection`. Concrete: `ArrayDeque`, `LinkedList` (a Deque too). Deques already had `addFirst`/`getFirst` etc., so the interface formalizes what they did. - **`LinkedHashSet`** → now a `SequencedSet`. It keeps insertion order, so end access is meaningful. - **`SortedSet` / `NavigableSet`** → now `extends SequencedSet`. Concrete: `TreeSet`. Order is the comparator's order. ## Map side (SequencedMap) `SequencedMap<K,V>` adds: `firstEntry()`, `lastEntry()`, `pollFirstEntry()`, `pollLastEntry()`, `putFirst(k,v)`, `putLast(k,v)`, and `reversed()` (a reversed-order `SequencedMap` view). Its `sequencedKeySet()`, `sequencedValues()`, `sequencedEntrySet()` return Sequenced views. - **`LinkedHashMap`** → now a `SequencedMap`. - **`SortedMap` / `NavigableMap`** → now `extends SequencedMap`. Concrete: `TreeMap`. ## What is NOT sequenced - **`HashSet`**, **`HashMap`** — no defined encounter order, so they are intentionally excluded. Calling for first/last on them makes no sense, so the interfaces simply don't apply. - Concurrent unordered maps like `ConcurrentHashMap` are likewise not sequenced. ## Position-control caveat for sorted types For a `SortedSet`/`SortedMap` the position of an element is determined by the **comparator**, not by the caller. Therefore `addFirst`/`addLast` (and `putFirst`/`putLast`) throw `UnsupportedOperationException` on those types: you cannot force an element to the front if the sort order says otherwise. `getFirst`/`getLast`/`reversed()` work fine — they just report the comparator-defined ends. This is the key gotcha when treating a `TreeSet` polymorphically as a `SequencedCollection`.

  • Why does TreeSet.addFirst(x) throw UnsupportedOperationException?
    Because a TreeSet places elements by its comparator; you can't override where an element goes, so forcing it to the front is unsupported. Read-side end access (getFirst/getLast/reversed) still works.
  • Does ArrayList get the new methods, or only LinkedList?
    ArrayList gets them too — List itself extends SequencedCollection, so every List implementation has getFirst/getLast/addFirst/addLast/reversed.

saying these in an interview costs you the question

  • Saying HashSet/HashMap implement the interfaces — they don't (no order)
  • Forgetting that SortedSet/SortedMap addFirst/addLast/putFirst/putLast throw UnsupportedOperationException
  • Thinking only LinkedList/ArrayDeque got it and forgetting plain ArrayList
  • Assuming ConcurrentHashMap became sequenced

context

resolving links…