the big picture

the picture

you know how there are like forty classes in java.util and they all kinda sound the same? ArrayList, ArrayDeque, LinkedList, LinkedHashSet. it's less chaos than it looks.

think of a hiring board. the interfaces are job descriptions ("must keep things in order", "must never hold two of the same thing"). the classes are the people hired for those jobs, each with a different way of getting it done (an array, a chain of nodes, a tree). you write your code against the job description, and you can swap the hire later.

read the arrows as "is a". a Deque is a Queue and also a SequencedCollection. a NavigableSet is a SortedSet is a SequencedSet is a Set is a Collection is an Iterable. that last one is why every collection works in a for-each loop (the loop just asks for an iterator, more in iterators and fail-fast).

four shapes of data

forget the class names for a second. almost every collection you'll ever need is one of four shapes.

and then each shape has a couple of ways to be stored. that's where the real differences live: speed, memory, ordering.

see the pattern? there are really only four storage tricks in here: a flat array, linked nodes, a hash table and a balanced tree. every class is one of those (or two of them glued together).

sequenced collections java 21+

here's a fun one. before java 21, "give me the last element" was spelled differently for every collection:

list.get(list.size() - 1);
deque.getLast();
sortedSet.last();
// LinkedHashSet: walk the whole thing
String last = null;
for (String s : linkedSet) last = s;

list.getLast();
deque.getLast();
sortedSet.getLast();
linkedSet.getLast();

JEP 431 added three interfaces: SequencedCollection, SequencedSet and SequencedMap. anything with a defined encounter order got getFirst, getLast, addFirst, addLast, removeFirst, removeLast and reversed() (maps got firstEntry, lastEntry, putFirst, putLast and friends).

void main() {
    List<String> list = new ArrayList<>(List.of("a", "b", "c"));
    Deque<String> deque = new ArrayDeque<>(List.of("a", "b", "c"));
    SequencedSet<String> set = new LinkedHashSet<>(List.of("a", "b", "c"));
    SequencedMap<String, Integer> map = new TreeMap<>(Map.of("a", 1, "b", 2, "c", 3));
 
    IO.println(list.getLast() + " " + deque.getLast() + " " + set.getLast() + " " + map.lastEntry());
    IO.println(list.reversed() + " " + set.reversed() + " " + map.reversed());
}

c c c c=3
[c, b, a] [c, b, a] {c=3, b=2, a=1}

(no imports: a compact source file gets all of java.base imported for free, java.util included.)

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
List<Integer> r = list.reversed();
list.add(4);
IO.println(r);

program to the interface

declare the variable as the job, not the hire:

List<String> names = new ArrayList<>();     // the type says "a list"
Map<String, Integer> ages = new HashMap<>(); // the type says "a map"

now every method that takes names only promises to use list things. if a profiler later tells you a different implementation fits better, you change one new and nothing else.

but pick the right interface. Collection is the most flexible type and the least useful one: it has no get(i), no order and no idea about keys. take the narrowest thing that has the methods you actually call.

the legacy ones

Vector, Hashtable, Stack and Enumeration are from java 1.0, before the collections framework existed (it arrived in 1.2). they still compile, they still work, and they make every single method synchronized, which costs you on every call and still doesn't make compound actions like "check then add" safe.

if you really need thread-safety, reach for the concurrent collections, which were designed for it instead of patched for it.