Collections Roadmap:Pick the JDK Type for the Job You Have

You need a bag of orders, a unique set of SKUs, a map from order id to total, or a queue of work for the next worker. The JDK already named those jobs. Reaching for ArrayList for all of them compiles. It also turns uniqueness into a scan, a map into a linear search, and a hand-off into a busy loop.

A collection type is a contract: what you can ask, what order means, and whether another thread may look. The class you new is how the JDK delivers that contract. This series is the contracts and the JDK types, not a second data-structures course.

This post is the series glossary and index: the hierarchy, the words later posts will use without re-defining, a matrix for nulls / order / threads, and a living catalog of every post in this section. Later posts link back here instead of re-lecturing fail-fast, optional operations, or why Map is not a Collection.

How to use this page

You do not need to read twenty-five posts before you write new HashMap<>().

• Jump by contract — List, Set, Queue/Deque, Map — if you already know the name and want the API, the views, and the interview questions.
• Jump by implementation — ArrayList, HashMap, ConcurrentHashMap — if you are picking a class today.
• Follow Start here if you want the contracts first, then the defaults, then concurrent types.
• Treat this page as the map. Family posts stand alone for their own title. Definitions of Collection vs Map, optional operations, fail-fast vs weakly consistent vs snapshot, unmodifiable vs immutable, views vs copies, RandomAccess, sequenced as a name, and keys that honor equals/hashCode live here.

What this series unlocks, not what it replaces: Data Structures owns layout (why a dynamic array grows, why a hash table is usually O(1)). Java Streams owns the pipeline. This series owns the JDK types you import from java.util and java.util.concurrent.

When they shipped

Release	Status	Notes
Java 1.2	Collections Framework	Collection, List, Set, Map, Iterator; ArrayList, HashMap, HashSet, TreeMap
Java 1.5	Generics + Queue	No more raw types in new code; Queue and concurrent packages
Java 6	Deque, Navigable*	Two ends and ceiling/floor without rolling your own
Java 9	Factories	List.of, Set.of, Map.of, copyOf
Java 21	Sequenced	Uniform first / last / reversed — see Sequenced Collections
Today	Core skill	Every backend service still picks these types on the hot path

Use a current JDK for this series. Examples assume Java 21+ so sequenced methods and SequencedCollection are available; factories are called out as Java 9.

Collection vs Map

A Collection is a group of elements. A Map is a group of key-value mappings. Map does not extend Collection. That is not an accident.

Collection<Order> open = new ArrayList<>();
Map<String, Order> byId = new HashMap<>();

open.contains(order) asks about an element. byId.containsKey(id) asks about a key. The views on a map (keySet, values, entrySet) are collections. The map itself is not. Interviewers draw this split first. Later posts do not re-draw it.

Iterable sits under Collection: you can for-each a list or a set. You cannot for-each a map; you iterate a view.

The hierarchy, one screen

Iterable
  Collection
    List            indexed, duplicates allowed, encounter order
    Set             unique elements
    Queue           insert at one end, take from the other (usually)
    Deque           both ends (also a Queue)
  — Map is a sibling, not a Collection —
    SortedMap / NavigableMap
    SequencedMap    (Java 21)

SortedSet / NavigableSet sit on Set.
SequencedCollection / SequencedSet sit on Collection / Set (Java 21).

Interfaces describe the job. Classes deliver it. List is the contract; ArrayList is the usual delivery. Program to the interface on fields and parameters. new the class that matches the hot operation.

Terms this series will not re-teach

Read these once. Later posts link here instead of repeating them.

Optional operations. Collection.add is allowed to throw UnsupportedOperationException. Unmodifiable lists, factory lists (List.of), and some views do. The interface is wider than any one implementation. Catching that exception as control flow is a bug — pick a type that supports the mutation you need.

Fail-fast vs weakly consistent vs snapshot. A fail-fast iterator (most java.util collections) throws ConcurrentModificationException if the collection is structurally changed while it iterates, except through Iterator.remove. A weakly consistent iterator (ConcurrentHashMap, ConcurrentLinkedQueue) may reflect some later updates and will not throw CME. A snapshot iterator (CopyOnWriteArrayList) walks the array that existed at creation. None of these is a memory barrier for your business logic. They are iterator contracts.

Unmodifiable vs immutable. Collections.unmodifiableList(list) is a view: mutate list and the wrapper shows it. List.of and List.copyOf are unmodifiable and independent of a later mutation of the source (copyOf copies). True immutability also requires immutable elements. The wrapper does not freeze Order fields.

Views vs copies. list.subList(1, 3), map.keySet(), and Collections.unmodifiableXxx are windows on the same storage. new ArrayList<>(other) and List.copyOf(other) allocate. Structural changes through a view write through; a copy does not.

RandomAccess. A marker that get(i) is cheap. ArrayList has it. LinkedList does not. Algorithms that index in a loop should check it — or accept an ArrayList.

Sequenced. Java 21’s name for “this collection has a first and a last.” ArrayList, LinkedHashSet, TreeSet, LinkedHashMap, and deques are sequenced. HashSet and HashMap are not. Details stay in Sequenced Collections.

Keys must honor equals and hashCode. A HashMap / HashSet bucket is hashCode then equals. Mutating a key after insert loses the entry. record components make honest keys; a mutable Order used as a key does not. Sorted maps use compareTo / Comparator instead of hashing — the comparison must be consistent with equals or you will not find what you put. The full contract is equals and hashCode.

Nulls, order, threads

The question is not “which collection is fastest.” It is which combination of nulls, encounter order, and thread safety you actually need.

Type	Nulls	Encounter order	Thread-safe
ArrayList	yes	insertion (index)	no
LinkedList	yes	insertion	no
ArrayDeque	no	insertion (ends)	no
HashSet	one null	none	no
LinkedHashSet	one null	insertion	no
TreeSet	no (natural order)	sorted	no
HashMap	one null key, null values	none (Java 8+ iterates in a repeatable but unspecified order)	no
LinkedHashMap	one null key, null values	insertion or access	no
TreeMap	no null key (natural order)	sorted by key	no
ConcurrentHashMap	no nulls	none	yes (map operations)
CopyOnWriteArrayList	yes	insertion	yes (snapshot iterators)
ArrayBlockingQueue	no	FIFO	yes (blocking)

Default in application code: ArrayList, HashSet, HashMap, ArrayDeque. Reach past those when order, sorting, null policy, or another thread forces it.

The lab domain: order, line item, SKU

Every post in this series uses the same tiny checkout domain as the functional interfaces, SOLID, and design-patterns series.

public record Order(
        String id,
        String customerEmail,
        List<LineItem> items,
        BigDecimal total,
        boolean active) {}

public record LineItem(String sku, int quantity, BigDecimal unitPrice) {}

Order.id is a map key. LineItem.sku is a set element. Order.items is a list. A warehouse worker’s next pick is a queue. If records are new, Java Records covers the shape.

When collections are cargo-cult

• ArrayList as a set. open.contains(order) on thousands of orders is a scan. HashSet is the uniqueness type.
• Vector / Hashtable because they are “thread-safe.” They lock the whole table on every call. ConcurrentHashMap and CopyOnWriteArrayList exist for shared data. Collections.synchronizedList still needs the iterator locked by you.
• LinkedList as a default list or deque. Indexing is O(n). As a deque, ArrayDeque wins. Linked nodes win only when you already hold the node and splice.
• A synchronized wrapper around a map you then stream. The wrapper does not make the stream safe. Pick a concurrent type or don’t share.
• Mutable keys. Put an Order in a HashMap, then change id. The entry is gone from the hash’s point of view. Why, and how to implement the pair: equals and hashCode.

The type that compiles is not always the type whose hot operation is cheap.

The catalog

Jump to the contract or the class that matches the job.

Wave 1 — contracts

Type	Pain it targets	Post
Collection, Iterator	Optional ops, fail-fast, removeIf, bulk methods	Collection and Iterator: The Contract Every List and Set Shares
List	Indexes, subList views, RandomAccess	List: Index, SubList, and Random Access as a Type
Set	Uniqueness without scanning	Set: Uniqueness Without Scanning the List
Queue, Deque	Ends, not indexes; offer vs add	Queue and Deque: Ends, Not Indexes
Map	Keys, compute/merge, live views	Map: Keys, Values, and the Views That Stay in Sync

Wave 2 — everyday implementations

Type	Pain it targets	Post
ArrayList	The default list; growth and ensureCapacity	ArrayList: The Default List and When Growth Bites
LinkedList	When a node list is the honest choice (rarely)	LinkedList: Nodes When ArrayList and ArrayDeque Already Lost
ArrayDeque	Stack and queue without Vector or LinkedList	ArrayDeque: Stack and Queue Without Vector or LinkedList
HashSet, LinkedHashSet	Unique elements, with or without encounter order	HashSet and LinkedHashSet: Unique Elements, With or Without Encounter Order
HashMap	The default map; what the table actually does	HashMap: The Default Map and What the Table Actually Does
LinkedHashMap	Insertion order, access order, LRU	LinkedHashMap: Insertion Order, Access Order, and a Real LRU
PriorityQueue	Next-best without sorting the whole list	PriorityQueue: Next-Best Without Sorting the Whole List

Wave 3 — ordered, special, and JDK helpers

Type	Pain it targets	Post
TreeSet, TreeMap, Comparator	Sorted keys, ceiling/floor, the comparison contract	Navigable Collections: TreeSet, TreeMap, and the Comparator Contract
EnumSet, EnumMap	A small closed universe of keys without hashing	EnumSet and EnumMap: Universe-Sized Keys Without a Hash
IdentityHashMap, WeakHashMap	== keys, and keys the GC may collect	IdentityHashMap and WeakHashMap: == Keys and GC-able Keys
List.of, Map.copyOf	Unmodifiable copies without unmodifiableList ceremony	Collection Factories: List.of and Map.copyOf Without the Mutable Default
Collections, Arrays	Sort, wrap, copy, asList, synchronized wrappers	Collections and Arrays: Sort, Wrap, Copy, and the Methods You Forget
Vector, Stack, Hashtable	Why they still compile and why you still skip them	Legacy Collections: Vector, Stack, Hashtable, and Why They Still Compile

Wave 4 — concurrent

Type	Pain it targets	Post
ConcurrentHashMap	Shared maps without locking the whole table	ConcurrentHashMap: Shared Maps Without Synchronizing the Whole Table
CopyOnWriteArrayList, CopyOnWriteArraySet	Snapshot iterators when reads dominate	Copy-On-Write: Snapshot Iterators When Reads Dominate
BlockingQueue	Hand off work without a busy wait	BlockingQueue: Hand Off Work Without a Busy Wait
ConcurrentLinkedQueue, ConcurrentLinkedDeque, ConcurrentSkipListMap, ConcurrentSkipListSet	Lock-free ends and concurrent sorted maps / sets	Concurrent Queues and Skip Lists: Lock-Free Ends and Concurrent Order

Wave 5 — interop, sequenced, choose

Type	Pain it targets	Post
Spliterator, Collectors	Split a collection and put a stream back into one	Spliterator and Collectors: Split a Collection and Put It Back Together
SequencedCollection	First, last, reversed without ceremony	Sequenced Collections: First, Last, and Reversed Without the Ceremony
Decision guide	Nulls, order, threads, and the hot operation	Pick the Collection: Nulls, Order, Threads, and the Hot Operation

Start here

Interface order is a catalog, not a curriculum. If you are picking a first path, start with the contracts, then the defaults you will type every day.

1. Collection and Iterator: The Contract Every List and Set Shares
2. List: Index, SubList, and Random Access as a Type
3. Set: Uniqueness Without Scanning the List
4. Queue and Deque: Ends, Not Indexes
5. Map: Keys, Values, and the Views That Stay in Sync
6. ArrayList: The Default List and When Growth Bites
7. HashSet and LinkedHashSet: Unique Elements, With or Without Encounter Order
8. HashMap: The Default Map and What the Table Actually Does
9. ArrayDeque: Stack and Queue Without Vector or LinkedList
10. ConcurrentHashMap: Shared Maps Without Synchronizing the Whole Table
11. Sequenced Collections
12. Pick the Collection: Nulls, Order, Threads, and the Hot Operation

Read the post that matches the type in front of you. Come back here for fail-fast, optional operations, and the “when to skip it” test.

Interview lens

Interviewers do not want twenty class names. They want the hierarchy, the iterator contract, and a default for each job.

What to draw. Iterable → Collection → List / Set / Queue. Map off to the side. One implementation under each: ArrayList, HashSet, ArrayDeque, HashMap.

Complexity they expect you to know without a table: ArrayList.get O(1), ArrayList.add amortized O(1), LinkedList.get O(n), HashMap.get expected O(1), TreeMap.get O(log n).

Typical questions this page answers:

Question	Honest answer
Why is Map not a Collection?	A map is mappings, not elements. Its views are collections.
What does fail-fast actually mean?	Structural change during iteration → ConcurrentModificationException, except Iterator.remove. It is not a concurrency guarantee.
Vector vs ArrayList?	Vector is a legacy synchronized list. It is not the thread-safe ArrayList you want.
When is LinkedList the right list?	Almost never as a List. As a deque, prefer ArrayDeque.
HashMap vs Hashtable vs ConcurrentHashMap?	HashMap default, no nulls story on the concurrent type, Hashtable is the legacy whole-table lock.
Can HashSet iteration order be a sequence?	No. Use LinkedHashSet or a sequenced type.

Wrong answer: “Vector is the thread-safe ArrayList.” Whole-table synchronized is not how you share a list in 2026. Name CopyOnWriteArrayList or “don’t share, confine.”

Cheat sheet

Collection     group of elements; Map is a sibling, not a subtype
Optional ops   add/remove may throw UnsupportedOperationException
Fail-fast      CME on structural change during iteration (java.util)
Weakly cons.   concurrent types; no CME; may see later updates
Snapshot       CopyOnWrite*; walks the array at iterator creation
View           subList, keySet, unmodifiableXxx — same storage
Copy           new ArrayList<>(x), List.copyOf(x)
RandomAccess   get(i) is cheap — ArrayList yes, LinkedList no
Sequenced      first/last/reversed (Java 21); HashSet is not
Keys           equals + hashCode; do not mutate after insert

Defaults       List ArrayList | Set HashSet | Map HashMap | deque ArrayDeque
Shared map     ConcurrentHashMap, not Hashtable, not synchronizedMap as a default

Do:

• Program to List / Set / Map / Deque. new the class that matches the hot operation.
• Treat List.of / Map.copyOf as unmodifiable copies, not as a frozen view of a live list.
• Put uniqueness in a Set and lookup in a Map. Do not scan a list to fake either.

Don’t:

• Reach for Vector or Hashtable because they say “synchronized”.
• Use HashSet order as a sequence.
• Mutate a key that is already in a hash map or hash set.

Wrap-up

The Collections Framework is a small set of contracts and a larger set of deliveries. Collection is elements; Map is mappings. Optional operations, iterator failure modes, and views vs copies are the rules every implementation inherits. Pick ArrayList, HashSet, HashMap, and ArrayDeque until order, sorting, null policy, or another thread says otherwise.

The catalog on this page is the map of the section. Start with the Collection and Iterator contract, because every list and set you already write sits on it.

Continue with Collection and Iterator: The Contract Every List and Set Shares →