ArrayList vs LinkedList: The Numbers Behind the Table

Both implement List. Both let you call get(3) and add(0, x). One of those calls costs five hundred times more on one of them than on the other, and nothing in the type system tells you which.

The complexity table for this pair is on every interview prep site, and it is correct. What it cannot give you is magnitude — whether O(n) means "measurably slower" or "the request times out". So this article times four operations on both, at real sizes, and one of the four results is not what the folklore says.

Every number below came from the same JDK 21 container, with the JIT warmed before anything was recorded.

The table everyone knows

An ArrayList holds a single array and an element count. get(i) is one memory access. Adding at the end is free until the array fills, then a bigger array is allocated and the contents copied — which is why the javadoc describes add as amortized constant time rather than constant.

A LinkedList holds a chain of nodes, each with the element and a reference to the node before and after it. Adding at either end is a couple of pointer writes. There is no index.

	ArrayList	LinkedList
get(i)	O(1)	O(n)
add(e) at the end	O(1) amortised	O(1)
add(0, e) at the front	O(n)	O(1)
memory per element	one array slot	element + 2 references + header

That is the whole theory, and it is where most articles stop. The useful part starts at the next heading.

Four operations, measured

A JDK 21 container, -Xmx512m, and three warm-up rounds of 10,000 elements on both implementations before any timing was taken. You need a JDK to reproduce this — installing Java 21 covers that if you are starting from nothing.

The harness is deliberately boring, and the warm-up is the part that is not optional:

static long timeIt(Runnable r) {
    long t = System.nanoTime();
    r.run();
    return (System.nanoTime() - t) / 1_000_000;
}

// Without this, the first measurement times the interpreter rather than the code.
for (int w = 0; w < 3; w++) {
    fill(new ArrayList<>(), 10_000);
    fill(new LinkedList<>(), 10_000);
}

System.out.println("ArrayList  " + timeIt(() -> fill(new ArrayList<>(), 100_000)) + " ms");
System.out.println("LinkedList " + timeIt(() -> fill(new LinkedList<>(), 100_000)) + " ms");

This is not a rigorous microbenchmark — JMH exists for that, and it would control for dead-code elimination and on-stack replacement in ways this does not. It is enough to separate five milliseconds from three seconds, which is the question being asked.

Appending 100,000 elements to the end:

ArrayList   1 ms
LinkedList  2 ms

Both fast. If appending is all you do, this comparison has no winner and you should pick on something else.

Reading 100,000 random indexes with get(i):

ArrayList      5 ms
LinkedList  2833 ms

That is the article. Five milliseconds against nearly three seconds — more than five hundred times — for the operation people reach for most often without thinking.

Inserting 50,000 elements at index 0:

ArrayList   106 ms
LinkedList    1 ms

The table's other direction, confirmed. Note the magnitude though: 106 ms is a hundredth of what the LinkedList lost on indexing. The asymmetry in the table is real; the asymmetry in the cost is not symmetric at all.

Iterating everything with for-each, at three sizes:

Elements	ArrayList	LinkedList
100,000	0 ms	1 ms
1,000,000	0 ms	1 ms
5,000,000	3 ms	12 ms

Which brings us to the result worth stopping on.

Iteration: the claim that is simply backwards

You will read that LinkedList is faster to traverse. It is not, at any size measured here. At a hundred thousand and a million elements the two are inside the noise of each other; at five million the ArrayList is four times quicker.

The reason there is no LinkedList advantage is that for-each does not index. It asks for an iterator, and both iterators step one element at a time — the LinkedList's follows a next pointer, the ArrayList's increments a counter. Neither is doing the expensive thing.

The reason ArrayList eventually pulls ahead is that its elements sit in one contiguous array, so walking it reads memory in the order the hardware prefetches. A LinkedList's nodes are wherever the allocator put them, and at five million nodes that scattering costs the nine milliseconds of difference.

Common mistake

Reaching for get(i) in a loop to traverse a LinkedList. That turns one pass into a nested one and is where the 2,833 ms above comes from.

The two versions look almost the same and are not:

// O(n²) on a LinkedList: every get(i) walks the chain again
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

// O(n) on either: the iterator holds its position
for (String item : list) {
    process(item);
}

The indexed version is correct on both implementations and fast on only one. That is the trap in programming to List rather than to an implementation: the interface promises behaviour, never cost. List says what get(int) returns and says nothing about what it costs.

Why indexing is that expensive

The mechanism is documented rather than mysterious. The LinkedList javadoc says operations that index into the list "traverse the list from the beginning or the end, whichever is closer to the specified index".

So the implementation is doing the best it can — it already halves the work by picking the nearer end — and it is still a walk. For random indexes into a 100,000-element list the average walk is 25,000 nodes, and each node is a pointer dereference to somewhere else in memory.

The ArrayList javadoc is explicit about the other side of it, and goes further than the complexity table does: it notes that its constant factor is low compared to LinkedList's. Two operations can both be O(1) and still differ by a lot, which is the general lesson hiding in this specific comparison.

The resize you can pay less for

The javadoc calls add amortised constant rather than constant because of one thing: when the backing array fills, a larger one is allocated and every element is copied across. That happens repeatedly as a list grows, and it is the only cost in ArrayList that a caller can remove.

Appending five million elements:

default initial capacity   147 ms
pre-sized to 5,000,000      92 ms

// The array is replaced and copied repeatedly on the way up
List<Integer> growing = new ArrayList<>();

// One allocation, no copying
List<Integer> sized = new ArrayList<>(5_000_000);

A third off, for knowing the size in advance. Worth doing when you do know it — reading a result set of known length, copying a collection — and not worth a second's thought otherwise. Fifty-five milliseconds across five million elements is not where your latency is.

The memory nobody counts

Measured one collection per JVM, with -XX:+UseSerialGC, holding a million Integer elements:

ArrayList   21 MB of live heap
LinkedList  39 MB

Almost double, for the same data. An array slot is one reference; a LinkedList node is an object with a header, the element reference, and references to its neighbours — three times the bookkeeping for the same payload.

This rarely decides a benchmark and often decides an incident, because it is the number that shows up as heap pressure in a service that holds a lot of lists and shares its heap with everything else. That heap is the JVM's, not the machine's, and it is smaller than people assume.

Note

The two measurements had to be taken in separate JVMs. Filling both in one process and taking the difference reported zero, because the heap grew to accommodate the second collection and the delta washed out. It is a good reminder that a memory measurement is easy to take and easier to take wrongly.

So when is LinkedList the right answer?

Narrower than the two-column table implies.

The case for it is real: a collection you only add to and remove from at the ends, and never index. A queue, a work list, an undo stack. LinkedList implements Deque as well as List, so it does that job correctly.

Except ArrayDeque also implements Deque, does the same job with one array instead of a million node objects, and gets the contiguity benefit the iteration measurement showed. Once you account for that, the set of problems where LinkedList is the best available answer is very small.

Which makes the practical rule shorter than the comparison suggests:

• Use ArrayList for a list. It is the default, and the measurements say the default is right.
• Use ArrayDeque when you want a queue or a stack.
• Use LinkedList when you have a specific reason you can say out loud.

A List returned from a method or serialised out of an API is almost always better as an ArrayList, and not because of the benchmark — because the next person to touch it will call get(i) on it eventually, and only one of these two survives that.

How to answer this in an interview

The table alone is a memorised answer. Three sentences make it a considered one:

1. The mechanism: array versus linked nodes, and the complexities that follow.
2. A magnitude: indexing a LinkedList is not slightly slower, it is hundreds of times slower, because it is a traversal.
3. The trade-off: LinkedList wins at the ends, ArrayDeque usually wins that case anyway, so ArrayList is the default.

And be ready for the follow-up, because a good interviewer asks it: is LinkedList faster to iterate? No. Equal at small sizes, slower at large ones, and the reason is memory locality rather than the data structure's shape.

What a good answer avoids is the claim that they are two reasonable options to pick between on taste. They are not. One is the default and the other needs a justification.