JAVA / COLLECTIONS

ArrayList vs LinkedList — which one when?

Medium

ArrayList keeps elements in one array: O(1) get(i), fast appends, compact and cache-friendly. LinkedList is a chain of nodes: cheap at the ends, but get(i) walks the chain and every node costs extra memory. Use ArrayList by default and ArrayDeque for queues.

How it works

ArrayList

Backed by an Object[]. get(i) and set(i) are a direct index: O(1).
add(e) at the end is amortized O(1). When the array is full it grows by about 1.5× and copies.
Insert or remove in the middle shifts the tail with System.arraycopy: O(n), but a fast block copy over contiguous memory.

LinkedList

A doubly linked list of Node objects (item, next, prev). Also implements Deque.
Add or remove at either end: O(1).
get(i) walks from whichever end is closer: O(n).
Inserting "in the middle" is O(1) only once you're already there with a ListIterator. Getting there is O(n).
Each element costs a separate node object (roughly 24 bytes plus the element reference), and nodes are scattered in memory, so walking the list misses the CPU cache.

In practice ArrayList wins almost every benchmark, including many middle inserts, because copying a contiguous array is faster than chasing pointers.

Example

List<Integer> linked = new LinkedList<>();
List<Integer> array = new ArrayList<>();
for (int i = 0; i < 100_000; i++) { linked.add(i); array.add(i); }

// O(n²) on LinkedList: every get(i) walks the chain
long slow = 0;
for (int i = 0; i < linked.size(); i++) slow += linked.get(i);

// O(n) on either: iterate, don't index
long fast = 0;
for (int v : linked) fast += v;

// Queue work: ArrayDeque beats LinkedList and has no node garbage
Deque<String> jobs = new ArrayDeque<>();
jobs.offerLast("resize-image");
jobs.offerLast("send-email");
String next = jobs.pollFirst();

Edge cases

LinkedList allows null elements; ArrayDeque doesn't.
Since Java 21 both are SequencedCollections with addFirst, getLast, reversed(). On ArrayList, addFirst is O(n) because it shifts everything.
new ArrayList<>(expectedSize) or ensureCapacity avoids repeated growth when you know the size.
Removing from an ArrayList while iterating front to back with indexes skips elements. Use removeIf or an iterator.

Common mistakes

Choosing LinkedList "because inserts are O(1)", while the code finds the position with indexOf or get(i) first.
Using LinkedList as a queue or stack in new code. ArrayDeque is faster.
Indexing into a List parameter in a loop without knowing which implementation the caller passes. Prefer iteration, or check for RandomAccess.

Likely follow-up

"When would you actually pick LinkedList?" Rarely: when you hold a ListIterator and do many inserts and removes right at the cursor on a large list, or you need a Deque that accepts null. Even then, measure first.

Get every deep dive in the app

Coming soon to the App StoreComing soon to Google Play