ArrayList vs LinkedList

For this lesson, we'll focus on the comparison interviewers actually care about: Big-O, memory layout, middle inserts, queue choices, iterator removals, a benchmark shape you can trust, the playlist and FIFO scenario questions, and the legacy Vector follow-up. We'll use Java 21 behaviour, and we'll cross-link to the internals lessons when you want the deeper implementation story.

01Picture it first: apartment block vs scattered houses

ArrayList is an apartment block: one building, numbered slots, quick access by floor. LinkedList is a chain of houses spread across a city: each house has the address of the previous and next house, but to reach house 500 you follow directions step by step.

Fig. 1

ArrayList stores references in one contiguous array while LinkedList stores scattered node objects with prev and next pointers

The diagram explains most real-world results. ArrayList pays when it has to grow or shift a suffix. LinkedList pays on almost every traversal, because each step loads another node object from wherever the allocator placed it.

02The complexity table interviewers expect

Start with the table, then immediately explain its limits. Big-O is the map, not the road surface.

Many candidates answer LinkedList because "insert in middle is O(1)." In that API call, the position is an index, not a node. LinkedList first performs an O(n) walk to the middle, then does O(1) pointer rewiring. ArrayList computes the index in O(1), then shifts a contiguous suffix with System.arraycopy.

List<String> ids = new ArrayList<>();
ids.add("A");
ids.add("C");
ids.add(1, "B");          // shifts C one slot to the right

List<String> linked = new LinkedList<>(ids);
linked.add(1, "A2");      // walks to index 1, then relinks

Notice what the table does not show: allocation, branch prediction, CPU cache misses, prefetching and GC. These are why the array-backed list often wins even for operations whose asymptotic cost looks worse.

03Why ArrayList usually wins middle inserts

Let's unpack the middle insert, because this is where interviews separate memorised Big-O from engineering judgement.

For ArrayList.add(index, e), Java checks capacity, shifts the suffix right by one with System.arraycopy, writes the new reference, and increments size. System.arraycopy is a JVM intrinsic on HotSpot for common cases, so it becomes a tuned native memory move. It moves references that sit next to each other in memory.

For LinkedList.add(index, e), Java calls node(index). That walks from first or last, whichever is closer, using the check index < size >> 1. Only after it reaches the successor node can it call linkBefore(e, succ) and update a few pointers. The walk is the expensive part.

// ArrayList-style work: find slot instantly, move a block
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = item;

// LinkedList-style work: find node first, then relink
Node<E> succ = node(index);       // O(n) walk from first or last
linkBefore(item, succ);           // O(1) after succ is known

The practical rule is: if you locate positions by index, ArrayList is usually the first implementation to try. If you already have an iterator positioned at the edit point, LinkedList becomes interesting.

04Memory comparison with numbers

ArrayList has one list object plus an Object[] containing references. Under compressed oops, each reference slot is 4 bytes. A capacity of 1,000,000 slots is about 4 MB for the array payload, plus array header and padding. The elements themselves are not inside the array; the array stores references to them.

LinkedList has one list object plus one node object per element. A simplified LinkedList.Node has an object header and three references: item, next and prev.

For 1,000,000 Integer references, the list storage difference is roughly 4 MB of ArrayList slots versus 24 MB of LinkedList nodes before counting the 1,000,000 Integer objects. If the elements are large domain objects, this ratio matters less. If the elements are small wrappers, IDs or references, the node overhead is visible in heap profiles.

05When LinkedList genuinely wins

The clean win is editing at a cursor you already hold. A ListIterator over a LinkedList stores enough state to remove the last returned node or add before the next node without searching again.