Which structure, which collection

Textbook data structures and java.util are the same subject taught twice, and most people learn them separately — the structures in an algorithms course, the collections at work — and never quite join them up.

This lesson is the join. Everything below is covered in depth by the collections course; what is here is which is which, and how to choose.

#The map

Two rows in that table are the ones people get wrong, and both are about reaching an element rather than changing it.

#LinkedList is O(1) at the ends and nowhere else

The textbook says linked lists are good at insertion. Measured three ways on 200,000 elements:

### 1. insert at the FRONT
###    ArrayList      1844 ms
###    LinkedList        5 ms
 
### 2. insert in the MIDDLE, by index
###    ArrayList        24 ms
###    LinkedList      429 ms
 
### 3. walk the whole list by index, get(i)
###    ArrayList         1 ms
###    LinkedList     3252 ms

The textbook is right about the first and wrong about the second, which is the case people usually mean.

Inserting into a linked list is O(1) once you are holding the node. add(index, e) is not holding the node — it walks there first, which is O(n). So the advertised O(1) applies at the head, at the tail, and through an Iterator you already have, and nowhere else.

The third row is the same fact and the reason LinkedList is almost never the right choice in practice: get(i) in a loop is O(n²) overall, and the elements are scattered across the heap rather than contiguous, so every step is a cache miss. ArrayList wins by three thousand times at a task the two structures are supposedly comparable at.

#Hash or tree: the question is whether you need order

HashMap and TreeMap both map keys to values. The choice is not performance, it is what you need besides lookup:

• HashMap — O(1) average, no order at all. Iteration order is not a contract and has changed between Java versions.
• TreeMap — O(log n), kept sorted, and that buys you operations a hash cannot do at any price: firstKey, lastKey, headMap, tailMap, subMap, floorKey, ceilingKey.

So: "every order between £100 and £500" is a TreeMap question. "the order with this id" is a HashMap question. If you find yourself sorting a HashMap's entries on every request, you wanted a TreeMap.

And LinkedHashMap is the third answer people forget: hash lookup, plus iteration in insertion order (or access order, which is how you build an LRU cache in about six lines).

#The heap is a priority queue, not a sorted list

PriorityQueue keeps the smallest element at the head and everything else only loosely arranged. That distinction has one consequence that surprises everybody exactly once:

Iterating a PriorityQueue does not give you sorted order. Only poll() does, one element at a time. A for (T t : queue) walks the backing array, which is heap-ordered, not sorted.

What it is for: "the k largest of a very large stream". Keep a heap of size k, push, and drop the smallest when it grows past k — O(n log k) and O(k) memory, where sorting everything is O(n log n) and O(n) memory. On a hundred million elements that is the difference between running and not.

#Choosing, as a sequence of questions

1. Do I look things up by key? → HashMap. Unless I also need order → TreeMap.
2. Do I need to know whether I have seen something? → HashSet. This is the single most valuable swap in ordinary code, and the big-O lesson measured it: List.contains in a loop was 1,900× slower at 100,000 elements.
3. Is it a list I index? → ArrayList, pre-sized if I know the size.
4. Do I add and remove at the ends? → ArrayDeque, for both stack and queue.
5. Do I repeatedly need the smallest or largest? → PriorityQueue.
6. Do I need insertion order and fast lookup? → LinkedHashMap.

#What has no collection, and why

Two structures in this course have no java.util equivalent, and that is the reason they get their own lessons:

• Tries — nothing in the standard library does prefix search. A TreeMap gets close with subMap, and a trie is the structure the problem actually wants.
• Graphs — Java has no graph type at all. You build one from the collections above, and which ones you choose is the first real decision in any graph problem.