ArrayList vs LinkedList: When Does Each Win?

ArrayList wins in almost every real case, and the reason is memory locality rather than raw operation counts. An ArrayList keeps its elements in one contiguous block of memory, so the CPU can prefetch them and the whole array fits in cache lines. A LinkedList scatters each element across the heap, with each node holding a pointer to the next, so every traversal is a chain of cache misses. That difference dwarfs the constant-factor advantages LinkedList has for a handful of operations.

Where LinkedList does have theoretical advantages is insertion and removal at a known position. Finding the position still costs O(n) because you have to walk the list, but once you are there, the actual insertion is O(1) because you just repoint two nodes. An ArrayList, by contrast, has to shift every subsequent element to make room, which is O(n).

And that advantage is theoretical in practice. To use it you need to be at the right position already, which usually means you have to search for it — and the search in a LinkedList is far slower than the search in an ArrayList because of the cache behaviour.

There is one more thing worth knowing: ArrayList amortises the cost of growth. When it runs out of capacity it allocates a bigger array — usually 1.5 times the size — and copies everything across, so the total cost of n appends is O(n) rather than O(n squared).

The standard advice: use ArrayList unless you have a specific, measured reason not to. If you need frequent insertion in the middle, prefer a different structure entirely — a gap buffer, a tree, or a deque — rather than reaching for LinkedList.

The same operations on both collections show why ArrayList is the default choice — random access is O(1) and there is no per-node object overhead:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> array = new ArrayList<>();
        List<Integer> linked = new LinkedList<>();

        for (int i = 0; i < 100_000; i++) {
            array.add(i);
            linked.add(i);
        }

        // Random access: ArrayList jumps straight to the index.
        long t0 = System.nanoTime();
        int sum = 0;
        for (int i = 0; i < 100_000; i++) {
            sum += array.get(i);
        }
        long arrayMs = (System.nanoTime() - t0) / 1_000_000;

        // LinkedList has to walk the list to reach the same index.
        t0 = System.nanoTime();
        sum = 0;
        for (int i = 0; i < 100_000; i++) {
            sum += linked.get(i);
        }
        long linkedMs = (System.nanoTime() - t0) / 1_000_000;

        System.out.println("sum: " + sum);
        System.out.println("ArrayList get loop: " + arrayMs + " ms");
        System.out.println("LinkedList get loop: " + linkedMs + " ms");
    }
}

Here are the complexities for random access, search, insertion and removal at the end and in the middle. The numbers are averages over a list of n elements.

Random access by index. ArrayList is O(1) — it computes the address directly. LinkedList is O(n) because it has to walk the node chain. This is the biggest practical difference, and it is why List.get(i) inside a loop is a disaster on a LinkedList.

Search for a value. Both are O(n), because neither is sorted. The constant differs: the ArrayList compares contiguous memory, the LinkedList dereferences a node per step, so the ArrayList is typically several times faster in practice.

Insertion and removal at the end. Both are O(1) amortised. The ArrayList occasionally copies the whole array when it grows; the LinkedList just relinks a node.

Insertion and removal in the middle. The ArrayList is O(n) because it shifts the tail. The LinkedList is also O(n) in practice, because finding the position is O(n), even though the actual relinking is O(1).

Two consequences worth stating. First, the for-each loop over a LinkedList is slow because each next() walks the node chain, while over an ArrayList it is effectively an array scan. Second, LinkedList does not implement RandomAccess, and several library methods check for that marker interface to decide whether to iterate by index or by iterator — so using a LinkedList quietly changes the performance of code you did not write.

There is also an iterator subtlety: the ListIterator of a LinkedList supports O(1) insertion once the cursor is in the right place, while the ArrayList's iterator does the same shifting work as the list itself. Both are O(n) overall from the start.