The collections hierarchy

For this lesson, we'll focus on the type map you should be able to draw in an interview: Iterable -> Collection -> List/Set/Queue/Deque, the sorted and navigable variants, Map as a separate hierarchy, Java 21's sequenced interfaces, the main implementations, legacy classes, skeleton classes, optional operations and RandomAccess. Interviewers ask this early because it exposes whether you understand contracts, not only class names.

01Picture it first: contracts first, engines second

Think of the hierarchy like a set of job descriptions. Collection says "I am a bag of elements". List, Set, Queue and Deque add promises about order, uniqueness and removal. Implementations are the engines you hire to fulfill those promises: arrays, hash tables, linked nodes, heaps and trees.

Here is the hierarchy tree I want you to keep in your head. Notice that Map sits next to the collection hierarchy, not underneath it.

Fig. 1

The Java 21 Collections hierarchy shows Iterable above Collection, Collection branching directly to SequencedCollection, Set and Queue, with List, Deque, sequenced set types and Map drawn separately

Notice three things:

• Iterable is about traversal, not storage. Anything with an iterator() can be used in an enhanced for loop.
• Collection is about elements. It has add(E), contains(Object), remove(Object) and size().
• Map is about associations. It has keys, values and entries, so its views are collections, but the map itself is not.

02The element side under the hood

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class InterfaceChoice {
    public static void main(String[] args) {
        List<String> auditLines = new ArrayList<>();
        auditLines.add("created");
        auditLines.add("charged");
        System.out.println(auditLines.get(1));        // charged

        Set<String> processedIds = new HashSet<>();
        System.out.println(processedIds.add("evt-1")); // true
        System.out.println(processedIds.add("evt-1")); // false

        Deque<String> work = new ArrayDeque<>();
        work.addLast("parse");
        work.addLast("index");
        System.out.println(work.removeFirst());       // parse

        Collection<String> batch = auditLines;
        System.out.println(batch.size());             // 2
    }
}

auditLines is a List because index and encounter order matter. processedIds is a Set because duplicates are the bug. work is a Deque because we operate at the ends. batch is a Collection because the caller only needs "a group of strings".

Notice the design habit: expose the weakest useful interface. If a method only needs to count or iterate, accept Collection<? extends Order> or Iterable<? extends Order>. If it needs random index access, say List. If it needs removeFirst, say Deque.

Iterable and Collection

Iterable<E> has one core method: iterator(). The enhanced for loop is syntax over that method, so arrays are special-cased by the language, while collections use Iterator.

Collection<E> is the root of the element hierarchy. The JDK does not provide a direct general-purpose Collection class because "a group of elements" is too vague by itself. You normally pick a more specific subtype: List, Set, Queue or Deque.

A Queue does not always mean FIFO. PriorityQueue is a queue because poll() removes according to priority, not insertion order. If you mean normal FIFO in modern Java, say ArrayDeque unless you need blocking or concurrent handoff.

Sorted and navigable sets

SortedSet gives sorted iteration, first(), last(), headSet, tailSet and subSet. NavigableSet extends it with the operations interviewers like because they map to real product questions: floor(e), ceiling(e), lower(e), higher(e) and descending views.

import java.util.NavigableSet;
import java.util.TreeSet;

public class PriceBands {
    public static void main(String[] args) {
        NavigableSet<Integer> prices = new TreeSet<>();
        prices.add(99);
        prices.add(149);
        prices.add(199);

        System.out.println(prices.floor(160));   // 149
        System.out.println(prices.ceiling(160)); // 199
        System.out.println(prices.descendingSet()); // [199, 149, 99]
    }
}

The implementation here is TreeSet, backed by a red-black tree. Each navigation operation is O(log n), so for 1,000,000 elements it is about 20 comparisons, not a scan across the set.

03Map is a separate hierarchy

A Map<K,V> is not a Collection<E> because it does not contain one kind of element. It contains mappings from keys to values. There is no sensible add(E) operation for a map: should E be a key, a value, or a pair?

The bridge is through collection views:

import java.util.LinkedHashMap;
import java.util.Map;

public class MapViews {
    public static void main(String[] args) {
        Map<String, Integer> stock = new LinkedHashMap<>();
        stock.put("keyboard", 7);
        stock.put("mouse", 12);

        for (String sku : stock.keySet()) {
            System.out.println(sku);
        }
        for (Integer count : stock.values()) {
            System.out.println(count);
        }
        for (Map.Entry<String, Integer> entry : stock.entrySet()) {
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }
    }
}

keySet() is a Set<K>, values() is a Collection<V>, and entrySet() is a Set<Map.Entry<K,V>>. Those are views, not usually independent snapshots. Remove from the entrySet iterator and you remove from the map.

The default map is HashMap. Use LinkedHashMap when iteration order matters, TreeMap when sorted keys or range queries matter, EnumMap when every key is an enum constant, IdentityHashMap when keys must be compared by ==, and ConcurrentHashMap when multiple threads update the map.

04Java 21 sequenced collections

Before Java 21, Java had ordered collections but no shared interface for "has a first element, has a last element, and can be reversed". List used get(0) and get(size - 1), Deque used getFirst() and getLast(), SortedSet used first() and last(), and LinkedHashSet had no cheap last-element method. JEP 431 filled that gap.

Java 21 added three interfaces:

import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.SequencedMap;
import java.util.SequencedSet;

public class SequencedDemo {
    public static void main(String[] args) {
        SequencedSet<String> signups = new LinkedHashSet<>();
        signups.add("asha");
        signups.add("ravi");
        signups.addFirst("founder");
        System.out.println(signups.getFirst());        // founder
        System.out.println(signups.reversed());        // [ravi, asha, founder]

        SequencedMap<String, Integer> scores = new LinkedHashMap<>();
        scores.put("blue", 10);
        scores.put("green", 20);
        System.out.println(scores.firstEntry());       // blue=10
        scores.putFirst("green", 25);                 // reposition existing key
        System.out.println(scores.sequencedKeySet());  // [green, blue]
    }
}

Here is the catch: the interface can declare an operation that an implementation cannot honor. A sorted set decides position from the comparator, so new TreeSet<String>().addFirst("x") is allowed to throw UnsupportedOperationException. That brings us to optional operations.

05Real world: optional operations and views

The collection interfaces mark some mutating methods as optional operations. An implementation that cannot support one should throw UnsupportedOperationException. That is why List.of("a").add("b"), Collections.unmodifiableList(list).remove(0), and TreeSet.addFirst(x) can fail even though the method exists on the type.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class OptionalOperations {
    public static void main(String[] args) {
        List<String> source = new ArrayList<>(List.of("draft"));
        List<String> view = Collections.unmodifiableList(source);
        List<String> snapshot = List.copyOf(source);

        source.add("approved");
        System.out.println(view);     // [draft, approved]
        System.out.println(snapshot); // [draft]

        try {
            view.add("paid");
        } catch (UnsupportedOperationException ex) {
            System.out.println("view is read-only");
        }
    }
}

This is not a type-system failure. It is a deliberate compromise in the Collections Framework, which lets one interface cover mutable, fixed-size, unmodifiable, view-backed and sorted structures. In interviews, say the operation is optional and the implementation decides whether it is supported.

06Advanced: names, skeletons, markers and legacy classes

Collection vs Collections

Collection is an interface. Collections is a utility class full of static methods: sort, binarySearch, reverse, shuffle, unmodifiableList, synchronizedMap, emptyList and so on. The plural name is not the framework; it is one helper class inside the framework.

This naming trips people because we casually say "Java collections" to mean the whole ecosystem. In code, Collection is a type you can accept as a parameter, while Collections is never instantiated.

Abstract skeleton classes

The framework includes skeletal implementations: AbstractCollection, AbstractList, AbstractSequentialList, AbstractSet, AbstractQueue and AbstractMap. They exist so custom collections can implement a few core methods and inherit the rest. For example, a read-only list can extend AbstractList and implement get(int) plus size().

import java.util.AbstractList;
import java.util.List;

public class RecentIds {
    static List<String> lastThree(List<String> ids) {
        int from = Math.max(0, ids.size() - 3);
        return new AbstractList<>() {
            @Override public String get(int index) {
                return ids.get(from + index);
            }
            @Override public int size() {
                return ids.size() - from;
            }
        };
    }

    public static void main(String[] args) {
        System.out.println(lastThree(List.of("a", "b", "c", "d"))); // [b, c, d]
    }
}

Because we did not override mutators, add and remove throw UnsupportedOperationException. That is exactly the skeleton-class pattern: implement the irreducible operations, inherit default behavior, and override more methods when performance or mutability requires it.

RandomAccess marker

RandomAccess is a marker interface: it has no methods. ArrayList implements it to say get(i) is generally constant time. LinkedList does not, because get(i) requires walking from an end.

If you write generic list code, this matters:

import java.util.Iterator;
import java.util.List;
import java.util.RandomAccess;

public class ListTraversal {
    static long sum(List<Integer> values) {
        long total = 0;
        if (values instanceof RandomAccess) {
            for (int i = 0; i < values.size(); i++) total += values.get(i);
        } else {
            for (Iterator<Integer> it = values.iterator(); it.hasNext(); ) total += it.next();
        }
        return total;
    }
}

You do not write this branch often in application code. You should know it because it explains why ArrayList is the default list and why generic algorithms sometimes check a marker interface.

Legacy classes to avoid

Vector, Stack and Hashtable came from Java 1.0, before the modern Collections Framework landed in Java 1.2. They synchronize individual methods, which sounds safe but is usually the wrong contract. Per-method locking does not make a multi-step operation atomic, and it adds lock overhead even when the collection is thread-confined.

Many candidates say "use Stack for stack" because the name is tempting. In modern Java, use ArrayDeque: push, pop and peek are available, it has no legacy Vector baggage, and it also handles FIFO queues with addLast and removeFirst.

07The implementation map you should carry

Here is the practical lookup table. It is not the full JDK, but it covers the classes you will actually mention in interviews.

The simple option is almost always one of four: ArrayList, HashMap, HashSet, ArrayDeque. It stops being enough when the requirement says order, sorted range, priority, concurrent mutation, enum-only keys, weak reachability or reference identity. That is the decision path we cover next in Choosing the right collection.

08How to say it in the interview

When I ask this, I'm listening for the shape first. Can you draw Iterable, Collection, the four main element interfaces and the separate Map hierarchy? Then I listen for the practical defaults, the Java 21 update, and whether you avoid legacy classes without overclaiming about thread safety.

Iterable -> Collection -> List / Set / Queue
                        -> SequencedCollection (Java 21)
List: ArrayList default, LinkedList rare, RandomAccess marker
Set: HashSet, LinkedHashSet, TreeSet
     SortedSet -> NavigableSet: floor/ceiling/lower/higher
Queue -> Deque: ArrayDeque default; PriorityQueue is priority, not sorted iteration
Map is separate: keys -> values, no add(E)
Map views: keySet(), values(), entrySet()
SortedMap -> NavigableMap; SequencedMap in Java 21
Collection = interface; Collections = static utilities
Optional ops may throw UnsupportedOperationException
Avoid Vector / Stack / Hashtable in new code