PHASE 9Intermediate ~20 min· topic 13 of 13

Topic 9.13

Choosing the Right Collection

In one line

Choosing a collection comes down to four questions: duplicates or not, does order matter (and which order), how will you look things up, and do several threads share it? The answers point to ArrayList, HashMap, HashSet, LinkedHashMap, TreeMap, ArrayDeque or PriorityQueue almost every time.

Think of it like this

Choosing a container in a kitchen. Eggs go in a tray with numbered slots (a list: order and position matter). Spices go on a labelled rack where you grab one by name (a map: look up by key). Loose coins go in a jar where you only care whether a coin is there (a set). Orders waiting at the counter form a line (a queue), and the hospital ward sees the most urgent patient first (a priority queue). Pick the container by how you'll use what's inside.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Lookup: Finding an element or value, for example by key in a map or by membership in a set.
Big-O: A way to say how the time of an operation grows as the collection gets bigger: O(1) stays flat, O(n) grows with size, O(log n) grows very slowly.
Range query: Asking for all elements between two values, or the next bigger or smaller one. Sorted collections are good at this.
Legacy: Old classes kept for compatibility. They still work, but newer replacements are better.
Program to the interface: Declaring variables with the interface type (List, Map) instead of the class (ArrayList, HashMap).
LRU: Least Recently Used: a cache that throws away whatever was used longest ago when it's full.

Step by step

01Start with the shape of the data

Ask what one item looks like. A sequence of things where position or duplicates matter: a list. A bag of distinct things: a set. Pairs where you know one half and want the other: a map.

If you catch yourself writing for (Item i : list) if (i.id().equals(id)) return i;, the data wants to be a Map<Id, Item>.

Start with the shape of the datadiagram

Rendering diagram…

02The cost table to remember

ArrayList: get O(1), add at end amortised O(1), add/remove in the middle O(n), contains O(n). ArrayDeque: add/remove at either end O(1). HashMap/HashSet: get, put, contains O(1) on average. LinkedHashMap: same as HashMap, plus a defined order. TreeMap/TreeSet: O(log n) for everything, plus sorted iteration and ranges. PriorityQueue: offer and poll O(log n), peek O(1).

"O(1) on average" for hash collections assumes good hashCodes (Topic 4.8). Bad hashes pile entries into a few buckets; since Java 8 a crowded bucket becomes a tree, so the worst case is O(log n) instead of O(n) (Topic 9.4).

03Order: none, insertion, or sorted

Counting words is a good test. With HashMap the printed order looks random. With LinkedHashMap words appear in the order first seen. With TreeMap they're alphabetical. All three give the same counts; only the order of iteration differs, and so does the cost (TreeMap pays O(log n) per update for sorting).

TreeMap also answers questions the others can't: firstKey(), headMap("m"), ceilingKey(x) (the smallest key at least x).

04Queues and stacks: ArrayDeque by default

For a stack (last in, first out) use Deque<T> stack = new ArrayDeque<>(); stack.push(x); stack.pop();. For a queue (first in, first out) use offer and poll. Both are O(1) and faster than Stack and LinkedList.

When the "next" item is the smallest (or most urgent) rather than the oldest, it's a PriorityQueue (Topic 9.8), the backbone of Dijkstra's algorithm and top-k problems in the DSA course (/dsa/heaps).

05Special jobs: LRU caches and enums

LinkedHashMap built with accessOrder = true moves an entry to the end every time it's read; overriding removeEldestEntry to return size() > capacity gives a complete LRU cache in a few lines.

Keys that are enum constants belong in EnumMap and EnumSet: they're backed by an array or a bit set indexed by the enum's ordinal, smaller and faster than hash collections, and they iterate in declaration order.

06Program to the interface and size it

Map<String, Integer> counts = new HashMap<>(); lets you later switch to TreeMap by changing one word. Method parameters should use the most general type that works: Collection<String> if you only iterate, List<String> if you need positions.

Giving an expected size avoids repeated resizing: an ArrayList grows by 1.5x and copies its array each time (Topic 9.2); a HashMap rehashes every entry when it passes its load factor. HashMap.newHashMap(expectedSize) (Java 19) computes the right capacity for you.

Try it yourself

1
Change one word
In "Same data, three maps", change new LinkedHashMap<>() to new TreeMap<>(). Only one word changes and the program still compiles, because the variable's type is the Map interface.
2
Make the cache bigger
In the LRU example, create the cache with capacity 3 and add cache.put("d", 4); at the end. Predict the contents first. (After c the cache holds {b=2, a=1, c=3} in access order; adding d makes four entries, so the least recently used one, b, is evicted: {a=1, c=3, d=4}.)

Code & diagrams

Same data, three maps New tab

A HashMap would give the same counts in an order you shouldn't rely on, which is why it isn't printed here.

Expected output

TreeMap (sorted):           {apple=3, fig=1, pear=2}
LinkedHashMap (first seen): {pear=2, apple=3, fig=1}
first alphabetically: apple

An LRU cache with LinkedHashMap New tab

Expected output

{a=1, c=3}

Stack, queue and priority queue New tab

Expected output

stack pops: second
queue polls: first
priority queue polls: 1

EnumMap for enum keys New tab

Expected output

{MON=8, WED=3}
[MON, TUE]

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Searching a list in a loop

Store 100,000 customer IDs in an ArrayList and call list.contains(id) once per incoming order.

terminal

$ profile the service

── what you'll see ──

CPU time grows with the square of the data size; 100,000 lookups take seconds instead of milliseconds.

Myth vs fact

Myth

LinkedList is faster than ArrayList for inserts.

Fact

Only if you already hold the node. Finding the position is O(n), and ArrayList's array copy is very fast. ArrayList or ArrayDeque wins in most real code.

Myth

TreeMap is always better because it's sorted.

Fact

Sorting costs O(log n) on every operation. Use HashMap unless you need sorted order or range queries.

Myth

Vector and Hashtable are the thread-safe choice.

Fact

They're legacy. Use ConcurrentHashMap, concurrent queues or immutable collections.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Memory matters at scale: an ArrayList<Integer> stores references to boxed Integer objects (16 bytes each on a typical 64-bit JVM with compressed oops), so a million ints take about 20 MB, versus 4 MB for an int[]. Primitive collections libraries (Eclipse Collections, fastutil) close that gap.
▸
HashMap iteration order depends on capacity and hash values, so it can change when the map resizes or between JDK versions. Tests that compare HashMap.toString() output are flaky by design.
▸
EnumSet is a bit vector (RegularEnumSet uses a single long for up to 64 constants), so set operations are single CPU instructions. It's the right tool for flags and permissions modelled as enums.
▸
For read-mostly data shared across threads, building a new immutable map and publishing it through a volatile field (copy-on-write) often beats locking or ConcurrentHashMap.

Remember this

1
Question 1: list, set or map? A list keeps elements in positions and allows duplicates. A set keeps each element at most once. A map stores key-to-value pairs and looks values up by key. Most bugs from the wrong choice are "I used a list and then searched it in a loop" (should be a set or map).
2
Question 2: what order? None needed: HashMap/HashSet (fastest). Insertion order: LinkedHashMap/LinkedHashSet. Sorted order or range queries ("all keys between a and m", "next bigger"): TreeMap/TreeSet. Position matters: ArrayList.
3
Question 3: how will you access it? By index: ArrayList (O(1) get). By key or membership: HashMap/HashSet (O(1) on average). From both ends: ArrayDeque (stack or queue). Smallest or largest first, repeatedly: PriorityQueue (O(log n) add and poll). Sorted with fast lookup and ranges: TreeMap (O(log n)).
4
Question 4: shared between threads? Plain collections are not thread-safe. For maps use ConcurrentHashMap; for queues between producer and consumer threads, ArrayBlockingQueue or LinkedBlockingQueue; for rarely-changed lists read by many threads, CopyOnWriteArrayList (Topic 13.8). Data that never changes after creation can simply be an immutable List.of/Map.of (Topic 9.11).
5
Two classic "don't"s. **LinkedList** is rarely the best choice: its O(1) insert needs you to already be at the right node, and its pointer-chasing is cache-unfriendly; ArrayList or ArrayDeque is usually faster (Topic 9.3). **Vector, Stack and Hashtable** are legacy (Java 1.0) synchronized classes; use ArrayList, ArrayDeque and HashMap/ConcurrentHashMap instead.
6
Always program to the interface (List<String> names = new ArrayList<>();), so you can swap the implementation later without touching the rest of the code, and give a capacity hint when you know the size (new ArrayList<>(10_000), HashMap.newHashMap(n) in Java 19+) to avoid repeated resizing.

Explain it without notes

Walk through how you would choose between HashMap, LinkedHashMap and TreeMap.

Why is ArrayDeque usually preferred over Stack and LinkedList?

Why should you declare variables as List or Map rather than ArrayList or HashMap?

Practice

Pick and justify a collection for each: (a) the last 10 search terms, newest first; (b) unique visitor IDs; (c) a leaderboard sorted by score; (d) tasks processed in arrival order by worker threads.

Count characters in "mississippi" and print the counts in alphabetical order.

Trade-offs

↔
Hash collections are fastest on average but unordered; linked versions add order for a little memory; tree versions add sorting and ranges for O(log n).
↔
Arrays and ArrayList are compact and cache-friendly but slow to insert in the middle; linked structures insert cheaply only when you already hold the position.
↔
Thread-safe collections cost throughput; immutable collections cost a rebuild per change but need no locking at all.

Done when you can

Done when you can answer the four questions (shape, order, access, threads) for any data you store.
Done when you can quote the big-O of get, add and contains for ArrayList, HashMap, TreeMap, ArrayDeque and PriorityQueue.
Done when you reach for ArrayDeque instead of Stack or LinkedList, and HashMap/ConcurrentHashMap instead of Hashtable.
Done when you can build an LRU cache with LinkedHashMap and know when EnumMap fits.

Command Palette

Words you'll meet

Step by step

01Start with the shape of the data

02The cost table to remember

03Order: none, insertion, or sorted

04Queues and stacks: ArrayDeque by default

05Special jobs: LRU caches and enums

06Program to the interface and size it

Try it yourself

Change one word

Make the cache bigger

Code & diagrams

Break it on purpose

Searching a list in a loop

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can