ArrayList vs LinkedList: Internals and Growth

This is the most-asked collections question and the one with the most outdated conventional answer. The textbook comparison — "array is fast for access, linked list is fast for insertion" — was written for machines where a memory access and an arithmetic operation cost roughly the same. They have not for thirty years.

What each one is#

public class ArrayList<E> extends AbstractList<E> {
    transient Object[] elementData;   // the backing array, possibly larger than size
    private int size;                 // how many slots are actually used
}

public class LinkedList<E> extends AbstractSequentialList<E> {
    transient int size;
    transient Node<E> first;
    transient Node<E> last;
 
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

ArrayList holds one object: an array. LinkedList holds one object per element, each with three references. That structural difference is the whole story.

Growth and copying#

private int newCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);   // 1.5x
    ...
}

An empty ArrayList starts with a shared static empty array and allocates nothing until the first add, at which point it jumps to capacity 10. From there: 10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → 244 → 366 → 549 → 823 → 1234.

Each step allocates a new array and calls System.arraycopy — an intrinsic that compiles to a hardware memory move, not a Java loop. Adding a million elements from empty performs about 30 reallocations and copies roughly two million element references in total. That is why add is described as amortised O(1): most calls are a single array write, and occasionally one is expensive.

The practical consequence is that presizing is free performance:

// 30 allocations, ~2 million reference copies, ~4MB of garbage arrays
List<Order> a = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) a.add(orders[i]);
 
// One allocation, zero copies
List<Order> b = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) b.add(orders[i]);

Complexity, and why it misleads#

The two rows that matter are "add in the middle" and "memory per element". LinkedList is O(n) for middle insertion too, because finding the position requires walking the chain — and the constant factor on that walk is enormous.

Why the array wins anyway#

Modern CPUs read memory in cache lines of 64 bytes. Reading one element of an array pulls the next eight references into L1 cache for free, and the hardware prefetcher, seeing a sequential pattern, fetches the following lines before they are asked for. Iterating an array is close to memory-bandwidth-limited.

Traversing a LinkedList is a pointer chase: each node's address is only known after the previous node has been read. Nothing can be prefetched, and if the nodes were allocated at different times they are scattered across the heap. Every step risks a cache miss costing roughly 100 cycles — about the time the array version needs to process a dozen elements.

The memory arithmetic makes it worse. On a 64-bit JVM with compressed oops, a LinkedList.Node costs about 24 bytes (16-byte header plus three 4-byte references, rounded up to 32 with alignment). Storing a million Integer references costs ArrayList roughly 4MB of array and LinkedList roughly 32MB of nodes — eight times the memory, eight times the cache pressure, and eight times the GC scanning work.

This is why real benchmarks show ArrayList winning even at inserting into the middle of a 100,000-element list: the System.arraycopy of 50,000 references is a single fast memory move, while walking 50,000 nodes is 50,000 potential cache misses.

Where LinkedList is genuinely better#

Two cases survive:

Iterator-based removal while traversing. Iterator.remove() on a LinkedList is O(1) — unlink two pointers. On an ArrayList it is O(n) per removal, so removing many elements in a loop is O(n²). But removeIf on an ArrayList is O(n) total because it compacts in a single pass, so this advantage mostly evaporates in modern code.

Unbounded queue with no resize pauses. A LinkedList never reallocates, so it has no latency spike when it grows. If you need that property, ArrayDeque is still usually faster; if you need it and unbounded growth without any single large allocation, LinkedList as a Deque is defensible.

Note that LinkedList is not a good Queue for concurrent use — that is ArrayBlockingQueue, LinkedBlockingQueue or ConcurrentLinkedQueue, covered in Queues, deques and blocking queues.

The answer to give#

"ArrayList is a contiguous array, LinkedList is a chain of nodes with three references each. The textbook answer says LinkedList wins for insertion, but that is only true if you already hold the position — finding it is still O(n), and walking the chain is a pointer chase with a cache miss per step. Combined with roughly 40 bytes of overhead per element against 4 for the array, ArrayList wins almost everywhere in practice. I would use LinkedList only as a Deque, and usually reach for ArrayDeque instead."

The follow-up is normally about growth: 1.5×, lazy first allocation at 10, amortised O(1), and presize when you know the size. Volunteering trimToSize and the fact that removal never shrinks the array tends to end the question early.