Big-O cheat sheet for collections

For this lesson, we'll focus on the operations interviewers ask you to compare: get, add, remove, contains and iteration for the main Java 21 collections. We'll also cover amortised ArrayList growth, expected versus worst-case hashing, why Big-O hides constants, memory per element ballparks and how to quote complexity without sounding overconfident. This lesson covers the checklist item Time Complexity of Java Collections.

01Picture it first: a heat map, not a scoreboard

Think of the collections table as a heat map for where the work happens. Green cells mean the operation touches one or a few locations. Orange cells mean the operation walks a path or height, like a tree or heap. Red cells mean the operation may scan or shift a number of elements proportional to the collection size.

The diagram below compresses the operations you should keep in your head. It is not a promise that every green cell is equally cheap.

Fig. 1

A heat-map grid compares Java collections by get, add, remove, contains and iteration, showing array-backed lists as cheap for indexed get and append, hash collections as expected constant-time for membership, tree collections as logarithmic, priority queues as heap-ordered and linked structures as costly for random access

Notice the pattern. Arrays win when the index is known and memory is contiguous. Hash tables win when equality lookup matters and hash distribution is reasonable. Trees win when you need sorted navigation. Heaps win when you only need the next best item, not a fully sorted collection.

02The main table

Read this table as Java 21, normal usage, n elements. For maps, get, add, remove and contains mean key operations: get(key), put(key, value), remove(key) and containsKey(key). For sets, get is not applicable.

Two details are easy to miss. HashMap iteration is not pure O(size): it scans the bucket array as well as entries, so a very sparse map costs more to iterate than its size suggests. LinkedHashMap iteration follows the doubly linked list, so it is O(size), which can make it nicer for iteration-heavy caches.

Queue<Job> jobs = new ArrayDeque<>();                 // offer/poll at ends: amortised O(1)
Map<String, User> usersById = new HashMap<>();        // get by key: expected O(1)
NavigableMap<Integer, String> leaderboard = new TreeMap<>(); // nearest scores: O(log n)
List<Listener> listeners = new CopyOnWriteArrayList<>();     // iteration cheap, writes copy

Notice three things:

• The table gives you the cost of the operation, not the best type by itself.
• PriorityQueue would be right for "give me the next highest score", but TreeMap is better for "closest score above and below".
• CopyOnWriteArrayList is terrible for frequent writes and excellent for mostly-read listener lists because each iterator sees a stable array snapshot.

03Amortised O(1): why ArrayList append is not magic

An ArrayList is an Object[] plus a size. A no-argument new ArrayList<>() starts with a shared empty array; the first append allocates capacity 10. Once the array is full, Java grows it to old + (old >> 1), roughly 1.5x, and copies the old references into the new array.

That means a single append can be O(n), because the grow step copies n references. Across a long run of appends, those copies are spread over many cheap inserts, so the average cost per append is O(1). That is what amortised means.

List<Integer> ids = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    ids.add(i);       // most calls write one slot; a few calls copy the whole backing array
}

If the size is known, presize it. new ArrayList<>(1_000_000) allocates enough slots up front and avoids the growth copies. The same idea applies to hash maps: since Java 19, HashMap.newHashMap(expectedMappings) sizes the table for the number of mappings you expect, not just a raw capacity.

04Expected versus worst case for hashing

Hash tables earn expected O(1) by spreading keys across buckets. HashMap stores an array of buckets, hashes the key, masks the hash to pick a bucket, then compares stored hash, == and equals inside that bucket. With a good hash distribution and a load factor around 0.75, buckets stay short.

The honest answer has four parts:

1. Normal get, put, remove and containsKey are expected O(1).
2. A resize is O(n), but happens occasionally and is amortised across inserts.
3. Since Java 8, a bucket that grows past the treeification thresholds can become a red-black tree, so a treeified bin is O(log k) for k entries in that bin.
4. A bad hashCode, mutable key or expensive equals can still dominate your runtime.

record BadKey(int id) {
    @Override public int hashCode() { return 42; }
}

Map<BadKey, String> orders = new HashMap<>();
for (int i = 0; i < 20_000; i++) {
    orders.put(new BadKey(i), "order-" + i);
}

System.out.println(orders.get(new BadKey(19_999))); // works, but collisions do the hard work

This example is intentionally hostile: every key lands in the same bucket. Java 8+ tree bins are a defence against that shape of input, but the interview-safe phrase is still "expected O(1), with tree-bin worst-case protection since Java 8". We cover the thresholds and resize split in Hashing, collisions, treeification and load factor.

05Why Big-O hides constants

Big-O ignores constant factors, allocation, cache locality, branch prediction and the cost of user code such as equals, hashCode and compare. In real Java, those constants decide many close calls.

ArrayList and LinkedList are the classic trap. Removing from the middle of a LinkedList is O(1) only if you already have the ListIterator positioned at that node. If all you have is an index or a value, the list must first walk node by node, which is O(n). Each node is a separate object, so that walk is also cache-unfriendly.

List<Integer> array = new ArrayList<>(List.of(10, 20, 30, 40));
array.add(2, 25);          // shifts 30 and 40 with System.arraycopy

List<Integer> linked = new LinkedList<>(List.of(10, 20, 30, 40));
ListIterator<Integer> it = linked.listIterator(2);
it.add(25);                // O(1) after the iterator is already at index 2

The default recommendation is practical: start with ArrayList for lists unless you have a measured reason not to. Use ArrayDeque for stack and queue behavior. Use LinkedList only when you specifically benefit from iterator-position inserts/removes or need a Deque that permits null, which is rare.

06Memory overhead ballparks

Complexity tells you growth rate; memory tells you whether the structure fits in cache or in the heap. These numbers vary with JVM, object alignment, compressed oops and field layout, so quote them as ballparks, not laws.

This is why a million-entry HashMap is not just a million keys and values. It also has a bucket array and a node object per entry. If the keys and values are small, the overhead can be the majority of the memory footprint.

07Advanced: collection-specific caveats

Lists and deques

ArrayList.contains is O(n), because it must compare elements until it finds a match. ArrayDeque.contains is also O(n). If your hot path asks "have I seen this?", a HashSet is usually the companion structure you want.

ArrayDeque is a circular array. Adding or removing at either end is amortised O(1), and it rejects null so that poll() returning null can mean "empty". For stack code, prefer ArrayDeque over the legacy synchronized Stack.

Maps and sets

HashSet is backed by a HashMap, LinkedHashSet by a LinkedHashMap, and TreeSet by a TreeMap. So the set costs mirror the map costs. The extra thing to remember is iteration order: none for HashSet, insertion order for LinkedHashSet, sorted order for TreeSet.

EnumMap and EnumSet are special because enum constants have dense ordinals. An EnumMap stores values in an array indexed by ordinal; an EnumSet stores bits in one or more longs. If your key type is an enum, they are usually both faster and smaller than hash-based alternatives.

Priority queues

A PriorityQueue is a binary heap in an array. peek() is O(1) because the minimum element is at the root. offer() and poll() are O(log n) because the element bubbles up or down the heap height.

The iterator is the gotcha: it walks the heap array, not sorted order. To consume in priority order, repeatedly call poll(), or copy the queue first if you need to preserve it.

Concurrent collections

ConcurrentHashMap has expected O(1) reads and updates, but its iterators are weakly consistent: they may reflect some concurrent updates and never throw ConcurrentModificationException. It also rejects null keys and values so get(k) == null always means absent.

ConcurrentSkipListMap is the concurrent sorted-map option. It uses a skip-list structure, so core operations are O(log n), and it gives you NavigableMap methods such as floorEntry, ceilingEntry and subMap under concurrent access.

CopyOnWriteArrayList is the opposite trade-off. Reads and iteration use a stable array and need no locks, while every write copies the entire array. I use it for listener lists and small registry-style collections, not for request streams.

08How to quote complexity in an interview

When I ask collection complexity, I'm listening for careful language. You do not need to recite every cell. I want to hear that you know the engine underneath the collection and can tie the cost to that engine.

A good answer follows this pattern: name the collection, name the backing structure, say average/amortised/worst-case, then mention the constant that matters. For example: "ArrayList.add(e) is amortised O(1) because it usually writes the next array slot, but a grow copies the array. HashMap.get is expected O(1), with tree-bin protection for heavy collisions since Java 8, and the real cost includes hashCode and equals."

ArrayList      get O(1), append amortised O(1), middle add/remove O(n)
LinkedList     get/contains O(n), O(1) edit only with iterator at node
ArrayDeque     ends amortised O(1), contains O(n), no nulls
HashMap/Set    expected O(1), resize O(n), tree bins O(log n) since Java 8
LinkedHash*    expected O(1), iteration O(n) in insertion/access order
TreeMap/Set    O(log n), sorted/range operations
PriorityQueue  peek O(1), offer/poll O(log n), remove/contains O(n)
EnumMap/Set    O(1), compact array/bit-vector for enum keys
COWAL          read O(1), write O(n) copy, snapshot iteration
CHM            expected O(1), weakly consistent iteration, no nulls
Big-O caveat   constants matter: cache locality, equals/hashCode/comparator, memory