ArrayList vs LinkedList, measured

the picture

you know the table every data structures course hands out? LinkedList: O(1) insert, O(n) access. ArrayList: O(1) access, O(n) insert. so for anything insert-heavy, linked list, right? that table counts how many steps each operation takes. it says nothing about how long a step takes, and on a modern CPU the answer ranges from a fraction of a nanosecond (data already in cache, or on its way) to around a hundred (a trip to main memory).

an array is a row of houses on one street: walk along and the next door is always right there, and you can see the next ten doors coming. a linked list is a scavenger hunt: each house has a note with the address of the next one, which could be across town, and you can't even start walking until you've read the note.

the basics (what each list holds, the node layout, ArrayDeque) are in ArrayList and LinkedList and ArrayDeque. this chapter measures.

big-O vs the stopwatch

four operations, measured on the same machine, each in a fresh JVM. pick one and compare what big-O predicts with what happened.

two of the four go the way big-O says (get(i) and adding at the front). the other two are where the CPU disagrees with the textbook. iteration is the big one, because it's what most code does most of the time, and its big-O is identical for both lists.

why iteration isn't equal

here are the addresses a for-each loop actually reads, in order, for 32 elements.

three things add up:

1. bytes per element. an ArrayList reads a 4-byte slot and the 16-byte Integer. a LinkedList reads a 24-byte node and the Integer. twice the memory traffic for the same data.
2. dependent loads. in an array, the address of slot i + 1 is known before you finish with slot i, so the CPU starts several loads at once. in a linked list, the address of the next node is inside the current node, so each load waits for the one before it. no overlap.
3. order. a fresh LinkedList was allocated in order, so its nodes sit next to each other and the hardware prefetcher keeps up. a list that's been built by inserting at random positions (or has lived through enough add and remove in the middle) points all over the heap, and every hop is a guess the prefetcher gets wrong.

the collections chapter measured the fresh case and noted the gap would grow as nodes scatter. here's how much: 1.6 ns per element fresh, 8.9 shuffled, against 0.34 for the ArrayList. a garbage collector that copies objects can sometimes put a list's nodes back in order, which is why the shuffled number is a bad day, not a constant.

memory per element

measured with jcmd GC.class_histogram on a million Integers (values from 1,000 up, so none come from the integer cache):

so a LinkedList roughly doubles the memory per element, and turning off compressed references (above a 32 GB heap they turn off by themselves, see object layout) makes the gap wider, since a node has three references and an array slot has one.

where LinkedList actually wins

removing elements while you iterate. LinkedList's iterator unlinks a node in O(1); ArrayList's shifts everything after it, every time.

so LinkedList is genuinely good at exactly one thing: changing a list at a spot you're already standing on, through a ListIterator. 9.7 ns for an insert and remove in the middle, against 6 µs for ArrayList. if your algorithm does a lot of that, on a big list, it's a real win. in practice that's rare enough that the person who wrote LinkedList, Joshua Bloch, has said he never uses it.

how these were measured

no JMH, so the harness had to be careful on its own. the core of it:

// runs op() in rounds of `reps` calls; the first 5 rounds are warmup; prints the median round
static void time(String name, int reps, long opsPerCall, LongSupplier op) {
    int rounds = 21;
    double[] ns = new double[rounds - 5];
    for (int r = 0; r < rounds; r++) {
        long t0 = System.nanoTime();
        long acc = 0;
        for (int i = 0; i < reps; i++) acc += op.getAsLong();   // results feed a sum...
        long t = System.nanoTime() - t0;
        sink += acc;                                            // ...that escapes, so the JIT can't delete the work
        if (r >= 5) ns[r - 5] = (double) t / reps / opsPerCall;
    }
    Arrays.sort(ns);
    System.out.printf("%-28s %10.2f ns/op%n", name, ns[ns.length / 2]);
}

java -Xms4g -Xmx4g -Xmn2g -cp . Bench iter-ll-scattered 100000

• one case per JVM. if one method calls get on both lists, the call site becomes polymorphic and the JIT optimizes it worse for both. a fresh JVM per case keeps every measurement monomorphic.
• warmup rounds thrown away, so the code is compiled by C2 before anything counts.
• a sink. every result is added into a static volatile field. without that, C2 is allowed to notice nobody uses the sum and delete the loop.
• a huge young gen (-Xmn2g), so no GC runs in the middle of a measurement and moves the shuffled nodes back into order.
• median, three runs, busy machine. the laptop was running other work (load average 10 to 19), so single runs wobbled, one case by almost 2x between runs. the ratios barely moved.

for anything you'd publish or base a decision on, use JMH. it does all of this and more (forking, blackholes, statistics), and it catches the mistakes you didn't think of.