Choosing the right collection

Six lessons of detail, and in daily work the decision comes down to a few questions asked in order. This lesson is the decision procedure, backed by measurements rather than assertions — because the received wisdom about LinkedList in particular is wrong, and you will hear it repeated in interviews.

The decision, in order

1. Do I look things up by a key? → Map.

2. Do I only care whether something is present, with no duplicates? → Set.

3. Does order or position matter, or are duplicates meaningful? → List.

4. Am I only adding and removing at the ends? → Deque.

Then, having picked the shape, pick the implementation:

Nine times out of ten the answer is ArrayList, HashMap or HashSet. The skill is recognising the tenth.

The measurements

All on 200,000 elements, on the machine these lessons were written on. Your absolute numbers will differ; the ratios are the point.

ArrayList  add at end     :     0 ms
LinkedList add at end     :     1 ms

ArrayList  get(i)  x200k  :     0 ms
LinkedList get(i)  x20k   :   311 ms

ArrayList  add(0, x) x50k :   102 ms
LinkedList add(0, x) x50k :     0 ms
ArrayDeque addFirst  x50k :     0 ms

ArrayList  contains x2000 :   183 ms
HashSet    contains x2000 :     0 ms

HashMap    get x200k      :     0 ms
TreeMap    get x200k      :    11 ms

Four conclusions, each worth stating plainly.

LinkedList.get(i) is catastrophic. Twenty thousand indexed reads took 311 ms; two hundred thousand from an ArrayList took under a millisecond. A LinkedList has to walk the chain from one end for every get, so an ordinary for (int i = 0; i < list.size(); i++) loop over one is quadratic. This is the single most expensive accidental choice in this module.

ArrayList.add(0, x) is the mirror image, and the reason LinkedList is taught at all. But note the third line: ArrayDeque is just as fast and is faster at everything else. If you need to add at the front, you want a Deque, not a LinkedList.

contains on a list is the bug you will actually write. 183 ms against effectively zero, and it gets worse as the list grows. Any contains inside a loop means a Set.

TreeMap costs about ten times a HashMap per lookup, which is small in absolute terms. Use it freely when you need sorted keys or ranges; do not use it by default.

So when is LinkedList right?

Almost never. It wins only when you are inserting and removing in the middle while already holding an iterator at that position — and if you are doing that, you are usually writing something that wants a different data structure entirely.

Use ArrayDeque for queues and stacks. Also: do not use Stack, which is a legacy class extending Vector and synchronised for no reason you want to pay for.

Deque<String> queue = new ArrayDeque<>();
queue.addLast("Priya");      // enqueue
queue.pollFirst();           // dequeue

Deque<String> stack = new ArrayDeque<>();
stack.push("Priya");         // push
stack.pop();                 // pop

Complexity, for the interview and the instinct

Two footnotes on that table. "Amortised" means the backing array is occasionally copied, and averaging that cost over many additions leaves it constant. And LinkedList.remove(i) is O(n) despite unlinking being O(1), because finding the position still means walking the chain.

O(1) is not free, and O(log n) is not slow. The table tells you how cost grows, not what it is. A TreeMap lookup on a thousand entries is perfectly fast; an ArrayList.contains on a million is not.

Immutable collections

private static final Set<String> SERVICEABLE = Set.of("411014", "411207", "411028");

Use the of factories for anything that should not change: constants, method returns you do not want mutated, and values you hand to callers. They are smaller, faster, thread-safe, and they fail loudly if something tries to modify them.

List.copyOf(list) makes an immutable snapshot of an existing collection, which is the defensive copy from the encapsulation lesson in one call.

Thread safety, briefly

ArrayList and HashMap are not safe for concurrent modification. Two threads adding at once can corrupt them silently — not throw, corrupt.

• Do not use Vector or Hashtable. They are obsolete, synchronise every single call, and still do not make compound operations safe.
• Do not rely on Collections.synchronizedList(...) for compound operations either: if (!list.contains(x)) list.add(x) is still a race.
• Use ConcurrentHashMap and CopyOnWriteArrayList when you genuinely share across threads, and prefer confining a collection to one thread when you can.

Module 9 covers this properly. The point here is only to know that the default implementations are single-threaded by design, and that the fix is not the class with "synchronized" in its name.

A worked choice

A tiffin service needs: the delivery order for each round, the set of pincodes it serves, this month's tiffin count per customer, and the last twenty complaints newest first.

Four questions, four different answers, none of them LinkedList.

Check your work

What are the four questions, in order? Key lookup → Map. Membership without duplicates → Set. Order or duplicates matter → List. Ends only → Deque.

What are the three defaults? ArrayList, HashMap, HashSet.

Why is LinkedList.get(i) so slow? It walks the chain from one end for every call, so an indexed loop over one is quadratic. 20,000 reads took 311 ms against under a millisecond for 200,000 from an ArrayList.

If you need to insert at the front, what should you use? ArrayDeque. It matches LinkedList at the front and beats it everywhere else.

What is the most common accidental performance bug in this module? contains on a List inside a loop. Use a Set.

Is TreeMap slow? About ten times a HashMap per lookup, which is small. Use it when you need sorted keys or ranges; do not use it by default.

Which legacy classes should you avoid, and why is Collections.synchronizedList not a general answer? Vector, Hashtable and Stack — obsolete and synchronised per call. And per-call synchronisation does not make check-then-act sequences safe, because another thread can act between the two calls.

Practice 4, the four choices. Delivery rounds: Map<String, List<String>>. Pincodes: Set.of(...). Tiffins per customer: HashMap<String, Integer>. Last twenty complaints: ArrayDeque, adding at the front and removing from the back once it exceeds twenty. If you chose List for the pincodes, ask what operation you will perform on it most — it is contains.

Practice

1. Run the benchmarks yourself. Time LinkedList.get(i) against ArrayList.get(i), and ArrayList.add(0, x) against ArrayDeque.addFirst. Warm the JVM up first by running each loop a few times before timing, and note how much the first untimed run differs — that is the JIT from module 1.

2. Find the crossover. Time list.contains and set.contains at 1,000, 10,000 and 100,000 elements. At what size does the difference stop being negligible? That number is more useful than any rule of thumb.

3. Replace a Stack. Write a bracket-matching check using java.util.Stack, then rewrite it with ArrayDeque. Note which methods changed name and which class you would use again.

4. Choose for the tiffin service. Four requirements, four types, one sentence of justification each. Then write the declarations.

5. Build a bounded history. Keep the last twenty complaints, newest first, using an ArrayDeque. Add fifty and confirm the size stays at twenty and the order is right.

6. Harder — profile a real choice. Write a program that loads 100,000 delivery rows and answers: which customers ordered on both of two given days, the top ten customers by tiffin count, and whether a given pincode is serviceable. Implement it once with ArrayList for everything, then again with the right types, and time both. Write down which single change made the biggest difference — it will be one of the two named in this lesson.

---

That is module five. You can pick between List, Set and Map with a reason, remove from a collection without corrupting it, write equals and hashCode that a HashSet respects, sort by anything without the subtraction trap, and justify an implementation choice with numbers rather than folklore.

Next module: streams — the same collections, expressed as what you want rather than how to loop over them.