Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Choosing a collection

List, Set, Map, Queue and Deque, their main classes, what each operation costs, and the immutable versions.

Work out the main operation, then the order you need.

  • Positions, in order → ArrayList.
  • "Have I seen this?", no duplicates → HashSet (TreeSet if it must stay sorted).
  • Look up a value by a key → HashMap (TreeMap for sorted keys, LinkedHashMap for insertion order).
  • Oldest first, or newest first → ArrayDeque as a queue (offer/poll) or a stack (push/pop).
  • Most urgent first → PriorityQueue.
  • Never changes after it's built → List.of, Set.of, Map.of.

Then check the costs: a contains on a list inside a loop is the classic hidden slowdown.

The interfaces

Collection, List, Set, Queue and Map, and why you declare the interface type.

Positions, duplicates allowed.

Section

Sets

No duplicates: HashSet, LinkedHashSet, TreeSet.

Section

Maps

Keys to values: HashMap, LinkedHashMap, TreeMap.

ArrayDeque both ways, and PriorityQueue.

Costs and the choice

Choosing a collection →

Formal. With n elements: ArrayList.get(i), set(i, x) and add(x) (amortized) are O(1); add(0, x), remove(0) and contains(x) are O(n). LinkedList.get(i) is O(n); adding or removing at either end is O(1). HashMap.get, put and containsKey, and HashSet.add and contains, are O(1) on average. TreeMap and TreeSet operations are O(log n). PriorityQueue.peek is O(1); offer and poll are O(log n).

In plain English. Jumping to a numbered slot or looking up a key in a hash table takes the same time however big the collection is. Searching a list checks every item, so it grows with the list. A sorted tree takes a few more steps each time the data doubles, about 20 steps for a million items.

Example. Checking a million IDs with list.contains(id) inside a loop over another million IDs is quadratic: about a trillion steps. Putting the IDs in a HashSet first makes each check constant and the whole loop linear.

Why this rule exists. The costs follow from how each class stores its elements: an array for ArrayList, a chain of nodes for LinkedList, buckets chosen by hashCode for HashMap, a balanced tree for TreeMap.

What get, contains and lookups cost in each class.

See section →
Work that stays the same however many elements there are.

The same cost at any size.

Big-O in plain words, how the classes work inside, and a procedure for choosing.

Read-only collections

List.of, copyOf, unmodifiable views, and first/last on sequenced collections.