When would you use LinkedList instead of ArrayList?

The Answer

Say this in the room. 45 seconds.

• ArrayList is a resizable array: O(1) indexed access, contiguous memory, one object for the whole list.
• LinkedList is a doubly-linked list: O(1) insert once you already hold the node, O(n) to find the position, and one node object per element.
• That "once you already hold the node" is the whole answer. list.add(i, x) has to walk to index i first, so the theoretical advantage never materialises.
• Measured on JDK 21: inserting mid-list is about 23x slower on LinkedList than on ArrayList, because a memory move of contiguous bytes beats pointer-chasing.
• LinkedList genuinely wins at the head and tail. But if that's your access pattern you want ArrayDeque, which is faster still and allocates no nodes.
• So: default to ArrayList. Reach for ArrayDeque for queue and stack work. LinkedList is a legacy answer.

Understand It

Two shapes in memory

ArrayList holds one Object[]. Element i is at a known offset, so get(i) is one bounds check and one array read. The elements sit next to each other, so walking the list pulls whole cache lines of useful data.

LinkedList holds a chain of Node objects, each with an item reference and two pointers. Every element costs an extra object — on a 64-bit JVM with compressed oops, roughly 24 bytes of node overhead per element, against 4 bytes of array slot. And the nodes are wherever the allocator put them, so traversal is a pointer chase with a cache miss waiting at each hop.

That second difference is the one that decides real benchmarks, and it does not appear in the Big-O table at all.

The table everyone memorises

Look at the middle-insertion row. Both are O(n) — this is where people misremember. LinkedList is O(1) at a node you already hold, which is what ListIterator.add() gives you. It is O(n) at an index, because add(i, e) calls an internal node(i) that walks from whichever end is closer.

So the constant factors decide it. Measure them.

The benchmark, on this machine

int n = 50_000;
int inserts = 10_000;
int[] idx = randomIndexes(5_000, n);

// One untimed pass each, so the JIT has compiled the loops before we measure.
bench(new ArrayList<>(), n, idx, inserts);
bench(new LinkedList<>(), n, idx, inserts);

long[] al = bench(new ArrayList<>(), n, idx, inserts);
long[] ll = bench(new LinkedList<>(), n, idx, inserts);

String[] labels = {
    "random get(i) x5000",
    "iterate all 50000",
    "insert at middle x10000",
    "insert at head x10000",
};
for (int i = 0; i < labels.length; i++) {
    System.out.printf("%-26s ArrayList %dms, LinkedList %dms%n", labels[i], al[i], ll[i]);
}

random get(i) x5000        ArrayList 0ms, LinkedList 229ms
iterate all 50000          ArrayList 8ms, LinkedList 3ms
insert at middle x10000    ArrayList 54ms, LinkedList 1240ms
insert at head x10000      ArrayList 90ms, LinkedList 1ms

Four results, and three of them surprise people.

Random access is the expected blowout. LinkedList.get(i) walks; there is no cheaper way to reach index i.

Iteration is a draw. Both are O(n) and the for-each loop uses an iterator, so LinkedList never calls get(i). Anyone who tells you LinkedList iteration is slow is thinking of index-based loops — which on a LinkedList are O(n²) and are a genuine bug, not a benchmark result.

Mid-list insertion goes to ArrayList, by more than an order of magnitude. This is the myth this entry exists to kill. ArrayList.add(i, e) does a bounds check and then System.arraycopy — a bulk memory move that the CPU does at memory bandwidth. LinkedList.add(i, e) walks 25,000 nodes on average, taking a cache miss most hops, and then does its O(1) splice. Walking dominates the splice by orders of magnitude.

Insertion at the head goes to LinkedList, decisively. No walk needed — it's the one case where the pointer update is the entire operation. This is a real win, and it is the only one.

Caveat, stated plainly: this is a crude benchmark. One JVM, no forks, a single warm-up pass, no statistics. Do not quote these millisecond figures as universal. The 1000x and 23x directions are stable and reproducible; the exact numbers are not, which is why this block is marked as varying between runs.

So use it for queues, right?

That is the usual retreat, and it's also wrong. If head and tail operations are your pattern, ArrayDeque beats LinkedList at them:

Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> linked = new LinkedList<>();

long dq = ms(() -> { for (int i = 0; i < 500_000; i++) deque.addFirst(i); });
long lk = ms(() -> { for (int i = 0; i < 500_000; i++) linked.addFirst(i); });

System.out.println("ArrayDeque and LinkedList both implement Deque: "
    + (deque instanceof Deque && linked instanceof Deque));
System.out.println("500000 addFirst — ArrayDeque faster or equal: " + (dq <= lk));

ArrayDeque and LinkedList both implement Deque: true
500000 addFirst — ArrayDeque faster or equal: true

ArrayDeque is a circular array. Adding at either end is an index update into contiguous memory, with no node allocation and no pointer chasing. It has been in the JDK since Java 6, and its own Javadoc says it is "likely to be faster than LinkedList when used as a queue".

That leaves LinkedList with a genuinely empty niche. The honest remaining answers are: you need a List that is also a Deque and you are stuck with an API that demands List; or you are removing through a ListIterator while traversing, where the O(1) splice is real because you already hold the node.

What Java 21 changed about all this

SequencedCollection closed one of the last practical gaps. getFirst() and getLast() used to exist on LinkedList and not on ArrayList, which pushed people toward LinkedList for readability:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));

System.out.println("getFirst  = " + list.getFirst());
System.out.println("getLast   = " + list.getLast());
System.out.println("reversed  = " + list.reversed());
list.addFirst("z");
System.out.println("addFirst  = " + list);
System.out.println("original unchanged by reversed()? " + list.contains("z"));

getFirst  = a
getLast   = c
reversed  = [c, b, a]
addFirst  = [z, a, b, c]
original unchanged by reversed()? true

reversed() returns a view, not a copy — writes through it affect the underlying list. And addFirst on an ArrayList is still O(n); the API got nicer, the complexity did not change.

The immutable-list trap, since we're here

Arrays.asList and List.of look interchangeable and behave differently in three ways:

Integer[] backing = { 1, 2, 3 };
List<Integer> asList = Arrays.asList(backing);
List<Integer> of = List.of(1, 2, 3);

asList.set(0, 99);
System.out.println("Arrays.asList writes through: backing[0] = " + backing[0]);

try {
    of.set(0, 99);
} catch (UnsupportedOperationException e) {
    System.out.println("List.of set()  -> " + e.getClass().getSimpleName());
}
try {
    asList.add(4);
} catch (UnsupportedOperationException e) {
    System.out.println("asList add()   -> " + e.getClass().getSimpleName());
}
try {
    List.of(1, null, 3);
} catch (NullPointerException e) {
    System.out.println("List.of(null)  -> " + e.getClass().getSimpleName());
}

Arrays.asList writes through: backing[0] = 99
List.of set()  -> UnsupportedOperationException
asList add()   -> UnsupportedOperationException
List.of(null)  -> NullPointerException

Arrays.asList is a fixed-size view over your array: set works and mutates the array you passed in, add throws. List.of is genuinely immutable and rejects null outright. Neither is "the immutable one" in the way people assume.

Interviewer's Next Move

The question after the question. This is what the round is actually testing.

1. "LinkedList is better for insertions in the middle — agreed?" No, and it's measurable. Both are O(n) at an index, because add(i, e) must walk to i first. On JDK 21 ArrayList is roughly 23x faster at it: System.arraycopy moves contiguous bytes at memory bandwidth, while LinkedList takes a cache miss per hop for 25,000 hops. LinkedList is only O(1) at a node you already hold, which means through a ListIterator.

2. "Then when does LinkedList actually win?" At the head, and at the tail. addFirst is a pointer update with no walk. That is the only category where it wins, and if that is your access pattern the right answer is ArrayDeque — circular array, no node allocation, faster at both ends, in the JDK since Java 6.

3. "Is iterating a LinkedList slow?" No, it's competitive with ArrayList — for-each uses an iterator, so there's no per-element walk. What is catastrophically slow is an index loop, for (int i = 0; i < list.size(); i++) list.get(i), which is O(n²). That's a bug, not a property of iteration.

4. "Which uses more memory?" LinkedList, substantially. Every element gets a Node holding the item plus two pointers — around 24 bytes of overhead each, against roughly 4 bytes per array slot. ArrayList also over-allocates its array by up to 50% after a growth, so it wastes capacity; that is still far less than a node per element.

5. "Does ArrayList ever shrink?" No, not on its own. Growth is amortised by copying into an array around 1.5x larger; removal never gives capacity back. trimToSize() is the only way, and it isn't on the List interface — you need the concrete ArrayList type to call it.

6. "Difference between Arrays.asList and List.of?" Arrays.asList is a fixed-size view over the array you passed: set works and writes through to that array, add throws. List.of is immutable, rejects every mutator, and rejects null elements with an NPE at construction. Different tools, and neither is the safe default people assume.

7. "What did Java 21 change here?" SequencedCollection (JEP 431) added getFirst, getLast, addFirst, addLast and reversed() to List, so ArrayList finally has the ergonomics LinkedList had. reversed() returns a view, not a copy, and the complexities are unchanged — addFirst on an ArrayList is still O(n).

Code traps

Trap A — predict before you run:

List<Integer> list = new LinkedList<>();
for (int i = 0; i < 100_000; i++) list.add(i);
long sum = 0;
for (int i = 0; i < list.size(); i++) sum += list.get(i);
System.out.println(sum);

Trap B:

List<String> list = new ArrayList<>(List.of("a", "b", "c", "d"));
for (String s : list) {
    if (s.equals("b")) list.remove(s);
}
System.out.println(list);

Common wrong answers

Check Yourself

Q1. Both ArrayList.add(i, e) and LinkedList.add(i, e) are O(n). Why is one dramatically faster in practice?

Q2. You need to add and remove at both ends, thousands of times a second. What do you use, and why not LinkedList?

Q3. When is LinkedList's O(1) insertion genuinely available to you?

Practice