Lists

A list is an ordered, indexed sequence of elements. It is the most-used container in almost any program — the JCF interface List<E> is your default when you need to remember things in the order they arrived.

This page covers the List interface, its two main implementations (ArrayList and LinkedList), and the small handful of facts about their memory layout that explain almost every performance question you'll ever ask.

The List interface

The methods that distinguish a List from a plain Collection are all about position: get(i), add(i, x), remove(i), indexOf(x), subList(from, to). A list has seat numbers.

ArrayList: a list backed by an array

ArrayList is the workhorse. Internally it holds an Object[] and a size counter. When the array fills up, it allocates a bigger one (typically 1.5× the current capacity) and copies.

That single picture explains every ArrayList performance fact:

LinkedList: a doubly-linked node chain

LinkedList is the other side of the coin. Each element is a node holding the value plus pointers to the previous and next nodes.

So LinkedList is O(1) at the ends and O(n) in the middle. It also implements Deque<E>, which is where most of its modern use comes from.

ArrayList vs LinkedList: when each wins

The honest short answer: ArrayList wins almost every real benchmark. The reason is hardware: arrays have contiguous memory, which the CPU's cache loves. Linked-list nodes are scattered all over the heap, costing a cache miss on every step.

The cases where LinkedList still wins:

• You are doing many addFirst / removeFirst and need an equal guarantee — but ArrayDeque is almost always better for this.
• You have an explicit reference to a node and need O(1) removal — but Java's LinkedList API doesn't expose nodes.

In modern Java code, LinkedList shows up much less often than you might guess from textbooks. Reach for ArrayList by default; reach for ArrayDeque when you genuinely need queue-like access at both ends.

(Numbers depend on the JIT, but ArrayList typically beats LinkedList even for "pure append" because of cache locality and the cheaper node-less storage.)

Initial capacity: when you know the size

If you know the rough size of an ArrayList ahead of time, pass it to the constructor. Otherwise you pay for repeated grow() and Arrays.copyOf.

Sublist: a view, not a copy

subList(from, to) returns a live view of the underlying list. Changes to the sublist affect the original — and structural changes to the original invalidate the sublist.

This is enormously useful for slicing — and a frequent source of surprise for people who expect a copy.

Immutable list literals: List.of(...)

Java 9 added factory methods List.of(a, b, c) that produce immutable lists. They are cheap, type-safe, and exactly what you want for small fixed collections (especially as constants).

For collections that are computed once and never mutated, this is strictly better than constructing an ArrayList and forgetting to seal it.

Removing while iterating: the right way

We met this in the iteration chapter, but it deserves a list-specific note: do not list.remove(...) inside a for-each loop. Use the iterator's remove(), or use removeIf (Java 8+):

removeIf accepts a Predicate and does the safe iteration for you.

Practice

[a, b, c]
[b, c, d]
[c, d, e]

Test your understanding