What each collection actually costs

"Choose the right collection" is advice nobody can act on without knowing what each one costs. This lesson is the numbers, and — more usefully — the several places where the numbers mislead.

The table

* amortised — see resizing below. † O(1) if you already hold the node, which via the List interface you never do. Finding it is O(n).

That footnote is the whole LinkedList story, and it is next.

LinkedList is almost never the answer

The textbook says: ArrayList is slow at inserting in the middle because it shifts elements; LinkedList just relinks pointers. Both halves are true and the conclusion is usually wrong.

To insert in the middle of a LinkedList, you must first walk to the middle — O(n) — and walking means following a pointer to a separate object each time. Each node is an allocation, scattered across the heap, and every hop is a potential cache miss.

ArrayList's shift is System.arraycopy: one contiguous block of memory, moved by an instruction the CPU is extremely good at. Copying 10,000 contiguous ints is faster than following 10,000 pointers.

In practice ArrayList wins almost everywhere, including cases the Big-O table says it should lose. The exceptions are narrow: a genuine queue (use ArrayDeque, which is better still), or holding a ListIterator and inserting repeatedly at that position.

The general lesson is worth more than the specific one: Big-O counts operations and ignores what each operation costs. On modern hardware, memory locality frequently dominates.

ArrayList resizing

ArrayList is an array. When full, it allocates a bigger one — 1.5× — and copies.

Any single add may therefore be O(n). Averaged out it is O(1), which is what "amortised" means. But if you know the size:

List<Delivery> deliveries = new ArrayList<>(10_000);

That is capacity, not size — the list is still empty. It avoids the repeated grow-and-copy, which for a large known-size build is a real saving and costs one argument.

HashMap: O(1) with conditions

HashMap is O(1) if your hashCode spreads keys well. When many keys land in the same bucket, lookup degrades toward O(n).

The classic worst case:

class BadKey {
    @Override public int hashCode() { return 1; }   // legal, and catastrophic
    @Override public boolean equals(Object o) { … }
}

Every key in one bucket. A "hash map" that is a linked list.

Modern Java softens this: since Java 8, a bucket with more than eight entries becomes a balanced tree, so the worst case is O(log n) rather than O(n) — provided the keys are Comparable. A mitigation, not a licence.

Load factor and capacity. Default capacity 16, load factor 0.75 — so it resizes at 12 entries, rehashing everything. Same fix as ArrayList:

// Expecting about 1,000 entries: 1000 / 0.75 ≈ 1334, so start above that.
Map<String, Delivery> index = new HashMap<>(2048);

Worth doing for a map you build once and read many times. Not worth thinking about for a map of five things.

When O(n) is faster than O(1)

// n = 10
List<String> list = List.of("a", "b", …);
list.contains("f");                   // O(n) — ten comparisons

Set<String> set = Set.of("a", "b", …);
set.contains("f");                    // O(1) — one hash, one bucket, one equals

For ten elements the list often wins. Hashing a string means reading every character; the array scan is contiguous and branch-predictable.

The crossover is usually somewhere in the tens. Below that, the constant factors decide and the simpler structure tends to win. Above a few hundred, the asymptotics take over and it is not close.

Which is why "always use a Set for contains" is wrong as a rule and right as a habit for anything that might grow.

The one that actually matters in real code

Not the choice of collection — the shape of the loop.

// O(n × m): for each delivery, scan every subscriber
for (Delivery d : deliveries) {
    for (Subscriber s : subscribers) {
        if (s.name().equals(d.customer())) { … }
    }
}

// O(n + m): index once, then look up
Map<String, Subscriber> byName = subscribers.stream()
        .collect(Collectors.toMap(Subscriber::name, s -> s));

for (Delivery d : deliveries) {
    Subscriber s = byName.get(d.customer());
    …
}

1,000 deliveries and 500 subscribers: 500,000 comparisons against 1,500. That is the difference that gets noticed, and it is exactly what BillingService does in the capstone — it builds a map in its constructor rather than scanning a list per lookup.

A nested loop over two collections is the performance bug you will actually meet. Not the choice between ArrayList and LinkedList.

Memory

Numbers worth carrying, for a 64-bit JVM:

Boxing is the one that surprises people. List<Integer> allocates an object per element; int[] does not. For a million numbers that is the difference between 20 MB and 4 MB — which is why IntStream exists.

Measure, do not guess

Everything above is a starting point for a decision, not a substitute for measuring.

Micro-benchmarking on the JVM is genuinely hard: the JIT optimises differently once warmed, dead code gets eliminated, and a naive System.nanoTime() loop frequently measures nothing at all. If you need a real number, use JMH.

For everyday work the honest advice is:

1. Write the clear version. Almost always ArrayList, HashMap, HashSet.
2. Look for accidental O(n²) — nested loops over collections.
3. Measure if it is slow, and only then.

Most performance problems in real applications are a database query in a loop or a nested scan, not a collection choice. Fix the shape before the structure.

Check your work

Why LinkedList loses even where Big-O says it wins: you must walk to the position, and each hop is a pointer chase to a scattered object; ArrayList's shift is one contiguous arraycopy.

What Big-O ignores: the cost of each operation. Memory locality often dominates.

What "amortised O(1)" means for ArrayList.add: any single add may copy everything; the average is constant.

What breaks HashMap's O(1): a bad hashCode clustering keys — softened since Java 8 by treeified buckets, but only for Comparable keys.

Why presize: both ArrayList and HashMap grow by copying and rehashing.

When a List beats a Set for contains: small sizes, where hashing costs more than a contiguous scan.

The performance bug you will actually meet: a nested loop over two collections — index one into a map instead.

Why int[] beats List<Integer>: boxing allocates an object per element.

The order of operations: write the clear version, look for O(n²), measure only if slow.

Practice

1. Build a million-element ArrayList and LinkedList by appending. Time both.
2. Now insert a million times at index 0 into each. Time both, and explain the reversal.
3. Iterate both summing a field, and time it. Explain the gap.
4. Build a 100,000-entry ArrayList with and without an initial capacity.
5. Write a key class whose hashCode returns 1, put 10,000 in a HashMap, and time a lookup against a proper hashCode.
6. Time contains on a List and a Set of 5, 50, 500 and 5,000 elements. Find your crossover.
7. Write the nested-loop join above with 1,000 and 500 elements, then the map version. Time both.
8. Find the constructor of the capstone's BillingService and explain what it is avoiding.
9. Sum a million int values as List<Integer> and as int[]. Compare time and memory.
10. Take any timing above, run it five times in one JVM, and explain why the first run is slowest.

Next: putting it together — choosing the right collection.