Lists: ArrayList vs LinkedList

"ArrayList or LinkedList?" is asked in every interview and answered wrongly in most textbooks. The textbook says LinkedList is O(1) for insertion and ArrayList is O(n), so use LinkedList when you insert a lot. On a real CPU, ArrayList wins almost every benchmark, including most of the insertion-heavy ones. This lesson is about why, in bytes and cache lines, and about the one case where the textbook is right.

#ArrayList

An ArrayList is a resizable array. It holds an Object[] elementData and an int size. get(i) is a bounds check and an array index: O(1), and a single cache-friendly memory read. add(e) writes at size and increments it: O(1) — unless the array is full, in which case it allocates a new array and copies. That copy is O(n), but it happens rarely enough that the amortised cost per add is O(1).

add(i, e) and remove(i) in the middle shift every subsequent element with System.arraycopy: O(n). contains and indexOf scan: O(n).

#Under the hood: growth, memory, and the cache

Growth is by half. A new ArrayList holds a shared empty array and allocates its first real array of 10 on the first add. When full, grow() computes oldCapacity + (oldCapacity >> 1): 10, 15, 22, 33, 49, 73, … The total copying over n appends is bounded by about 3n element moves, which is what "amortised O(1)" means in this class, and why new ArrayList<>(expected) matters only for lists in the hundreds of thousands, where it saves twenty or so resizes and the garbage they make.

Memory per element. An ArrayList slot is one reference: 4 bytes with compressed oops (heaps under 32 GB), 8 without. A LinkedList.Node is an object: 12-byte header + item + next + prev references = 24 bytes, plus the same 4-byte reference from wherever the node is pointed at. Per element, the linked list costs six times the array's slot before counting the element itself.

The cache is the whole story. A CPU reads memory in 64-byte lines. One line of an ArrayList's array holds 16 references, so iterating touches one line per 16 elements, and the hardware prefetcher, seeing sequential addresses, has the next line ready before it is asked. A LinkedList node is wherever the allocator put it; iterating is a pointer chase, each next a potential cache miss of 100 or more cycles, and the prefetcher cannot guess where the next node is. Big-O counts operations; the memory hierarchy charges per line.

#LinkedList

A LinkedList is a doubly linked chain of nodes, each holding an element and two references. addFirst, addLast, removeFirst, removeLast are O(1) — no shifting, no resizing. get(i) walks from the nearer end: O(n). add(i, e) is O(1) once you are at position i, but getting there is O(n), so through the List interface it is O(n) too.

#The benchmark reality

The middle-insert row surprises people. System.arraycopy of a few thousand references is a tight memmove that runs at memory bandwidth, tens of gigabytes per second; walking a few thousand nodes is a few thousand cache misses. The crossover where LinkedList wins for random middle insertion is at sizes where you should be using a different structure anyway.

#Walkthrough: the middle-insert benchmark, with numbers

A JMH benchmark inserts at a random index into a list of 10,000 Integers, ten thousand times, on a laptop. Representative results, and where each microsecond goes:

1. ArrayList, random add(i, e): about 1.2 µs per insert. The average shift is 5,000 references, 20 KB, moved by arraycopy at roughly 20 GB/s: one microsecond. The bounds check, the write and the occasional grow are noise.
2. LinkedList, random add(i, e): about 9 µs per insert. The walk to index i averages 2,500 hops from the nearer end; a hop whose node is not in cache is 50 to 100 ns; even with a warm cache holding a fraction of the nodes, the walk dominates. The insertion itself, four pointer writes and a 24-byte allocation, is under 50 ns and is the part the textbook counted.
3. At 100,000 elements the shift is 200 KB (10 µs) and the walk is 25,000 hops (most of them misses: over a millisecond). The array is still winning by a hundred to one, because the copy scales with bandwidth and the walk scales with latency.
4. At the front, add(0, e): the array shifts everything, 40 µs at 10,000 elements; the linked list writes four pointers, 30 ns. This is the row where the textbook is right, and it is the row ArrayDeque answers in 10 ns with a contiguous ring buffer.

The lesson is not "ArrayList always wins". It is that a comparison of operation counts that ignores what each operation costs in memory traffic predicts the wrong winner, and that the case where the linked list wins already has a better answer.

#When LinkedList is not a mistake

You are holding a ListIterator positioned somewhere in a long list and doing many inserts and removes at that position without re-seeking. A text buffer being edited at a cursor, a scheduler splicing entries near a known node. It is rare, and even then ArrayDeque or a gap buffer often wins.

#Sizing an ArrayList

new ArrayList<>() starts with capacity 10 (lazily allocated). If you know you will add 100,000 elements, new ArrayList<>(100_000) avoids about 30 resize-and-copy cycles. ensureCapacity does the same later. trimToSize releases slack if a list will live a long time at a fixed size. None of this matters for small lists; all of it matters when you build a list of millions inside a loop.

#Arrays.asList and List.of

Arrays.asList(a, b, c) returns a fixed-size list backed by an array: set works, add throws. List.of(a, b, c) returns an immutable list that also rejects null. Neither is an ArrayList; new ArrayList<>(List.of(a, b, c)) is the way to get a mutable one with initial content. Both remove overloads bite here too: list.remove(1) on a List<Integer> removes index 1, list.remove(Integer.valueOf(1)) removes the value.

#CopyOnWriteArrayList

For completeness: a thread-safe list that copies the whole array on every write. Reads are lock-free and consistent; writes are O(n). Right for a listener list that changes rarely and is iterated constantly; wrong for anything written frequently. Concurrency has its own lesson.

#Try it yourself

List<Integer> scores = new ArrayList<>(List.of(10, 20, 30));
scores.remove(1);
scores.remove(Integer.valueOf(30));
System.out.println(scores);

#Misconceptions

• "LinkedList is O(1) insert, so it is faster for inserts." O(1) once you are at the position, and O(n) cache misses to get there. The array's O(n) shift is one memmove at memory bandwidth.
• "ArrayList doubles when it grows." It grows by half (+ oldCapacity >> 1). HashMap doubles; ArrayList does not.
• "Big-O is what matters at scale." At scale the memory hierarchy matters more: an operation count that ignores cache lines predicts the wrong winner here by a factor of ten to a hundred.
• "LinkedList is the Java stack or queue." ArrayDeque is, and it is faster at both ends with contiguous memory.
• "Arrays.asList gives me an ArrayList." It gives a fixed-size list over the array. add throws; set writes through to the array.

#Going deeper

• ArrayList.grow and LinkedList.Node source: the growth arithmetic and the 24-byte node.
• Ulrich Drepper, "What Every Programmer Should Know About Memory", sections 3 and 6, for cache lines and prefetching.
• JMH's CollectionsBenchmark samples, and any JMH run you do yourself, since the numbers above are indicative and your CPU's are the ones that count.
• jol on an ArrayList and a LinkedList of ten elements, for the exact bytes.
• Joshua Bloch and Neal Gafter, Java Puzzlers, puzzle 22, for remove(int) versus remove(Object).