jd five

Lists

Learning goals

By the end of this chapter you should be able to:

  • Choose between ArrayList and LinkedList for a workload — not by habit, by access pattern
  • Use core List operations: indexed access, iterator edits, sublist views, bulk ops
  • Apply List.of / List.copyOf for immutable snapshots and know when ArrayList must grow
  • Recognize fail-fast iteration and SequencedCollection end APIs (Java 21+)

From arrays to growable lists

You already know arrays: fixed length, int[], fast index access, no built-in insert/remove in the middle.

A List is the growable, interface-driven evolution:

List<String> names = new ArrayList<>();
names.add("Ana");
names.add("Bo");
names.set(0, "Alice");
names.remove(1);

Same indexed mental model as an array, but size() changes and the compiler enforces generics (List<String> not raw List).

When to reach for a list instead of an array:

  • Size unknown at compile time or changes at runtime
  • You need List API integration (streams, sort, subList, collections utilities)
  • You want to program to an interface and swap implementations

Default choice for a mutable List: ArrayList. Reach for LinkedList only when iterator-heavy middle inserts or Deque dual use justify the extra per-node cost — details below.

A List is an ordered sequence: each element has an index from 0 to size()-1. ArrayList and LinkedList are not safe for concurrent writes without external synchronization—use Collections.synchronizedList, a java.util.concurrent queue/map design, or explicit locks when threads share a mutable list.

Under each implementation: Why / vs alternatives explains what problem it solves compared to the others.

ArrayList — not concurrent

Stores elements in a resizable array. When the array is full, a larger array is allocated and elements are copied over. Index access is direct: get(i) and set(i, v) are very fast. Inserting in the middle may require shifting many elements, so it is O(n) in the worst case. Appending at the end is usually amortized O(1) (occasional copy when growing).

Initialize: List<T> list = new ArrayList<>(); — optional capacity: new ArrayList<>(expectedSize).

Sharing across threads: wrap for mutual exclusion on every method (single lock—simple but can bottleneck):

List<String> list = Collections.synchronizedList(new ArrayList<>());

Heavy concurrent writes → often CopyOnWriteArrayList or java.util.concurrent queues instead; compare ConcurrentHashMap vs Collections.synchronizedMap in Maps.

Why / vs alternatives: Default mutable list: fast random index and cache-friendly contiguous storage. LinkedList wins when you mostly insert/remove at a ListIterator cursor or need List + Deque in one type—not for beating ArrayList on get(i) random access.

  • add(e) — appends at the end; may grow the array.
  • add(i, e) — inserts at index i, shifts following elements right.
  • get(i) — returns the element at index i.
  • set(i, e) — replaces the element at i, returns the old value.
  • remove(i) — removes the element at i, shifts following elements left.
  • remove(Object) — removes the first occurrence equal to the argument (uses equals).
  • size() — number of elements.
  • isEmpty() — whether size() is zero.
  • clear() — removes all elements.
  • contains(o) — whether some element equals the argument.
  • indexOf(o) / lastIndexOf(o) — first or last index of a match, or -1.
  • iterator() — forward iteration; fail-fast if the list is structurally modified while iterating (except through the iterator’s own remove).
  • listIterator() / listIterator(i) — bidirectional iterator; can insert and remove at cursor.
  • subList(from, to) — view of the range [from, to); changes show up in the original list and vice versa.
  • toArray() — copies elements into an array.

Java 21+: List extends SequencedCollection. End operations have standard names: getFirst() / getLast() (instead of get(0) / get(size() - 1)), addFirst() / addLast(), removeFirst() / removeLast() — same spelling Deque uses for two-ended access on ArrayList and LinkedList.

LinkedList — not concurrent

A doubly linked list: each node has prev and next pointers. No random access from index in O(1)—get(i) walks from an end, O(n). Insert/remove at the iterator cursor is O(1) per step. Also implements Deque (queue/stack at both ends).

Initialize: List<T> list = new LinkedList<>(); — or new LinkedList<>(anotherCollection).

Sharing across threads: pick one synchronized wrapper for one backing list (do not stack wrappers):

List<String> list = Collections.synchronizedList(new LinkedList<>());
// or: Deque<String> dq = Collections.synchronizedDeque(new LinkedList<>());

Why / vs alternatives: Solves O(1) structural edits at a moving iterator and two-ended queue/stack while still being a List. ArrayList shifts elements on middle insert; LinkedList avoids that when you already have the iterator. For queue/stack only on one thread, ArrayDeque is usually faster (no per-element nodes).

Implements the same List methods as ArrayList (with different performance). Especially useful:

  • listIterator() — walk the list and add / remove in O(1) per step at the iterator position.
  • addFirst / addLast / removeFirst / removeLast — Deque API (also on LinkedList).

List operations (all implementations) — varies

These are defined on the List interface; behavior is the same name everywhere, cost differs by implementation.

Initialize (immutable): List<T> list = List.of(a, b, c); — or List.copyOf(collection).

Why / vs alternatives: Fixed content published to callers without giving them a mutable ArrayList. List.of for small literal lists; List.copyOf from any collection. No add/remove—use ArrayList when the collection must grow.

  • addAll(c) — appends every element of collection c.
  • removeAll(c) / retainAll(c) — remove elements that are / are not in c.
  • removeIf(predicate) — removes each element matching the predicate (Java 8+).
  • replaceAll(operator) — replaces each element with operator.apply(element).
  • sort(comparator) — stable sort in place.
  • forEach(action) — runs action on each element in order.
  • stream() / parallelStream() — stream pipeline from this list.

Factories: List.of(a, b, ...) builds a fixed-size, immutable list. List.copyOf(collection) copies into an immutable list.

Next: Sets

Practice checkpoint

  1. You need fast random access by index and mostly append at the end — ArrayList or LinkedList? Answer: ArrayList — O(1) indexed get; append amortized O(1).

  2. What happens if you modify a list structurally while iterating with enhanced for-loop (not via iterator)? Answer: ConcurrentModificationException (fail-fast) on the next iteration step.

  3. List.of("a", "b").add("c") — compile or runtime issue? Answer: runtime — List.of returns immutable list; add throws UnsupportedOperationException.

  4. When is subList(from, to) dangerous? Answer: it is a view backed by the original; structural changes to either can invalidate the other or throw unexpectedly.

Interview angles

  • ArrayList growth: new larger array + copy when capacity exceeded; pre-size with constructor when you know N.
  • LinkedList vs ArrayList: LinkedList wins at iterator cursor inserts; loses on get(i) random access.
  • SynchronizedList vs CopyOnWriteArrayList: former locks whole list; latter copies array on write — read-heavy workloads.
  • SequencedCollection (21+): getFirst/getLast unify end access across List, Deque, ordered sets/maps.

Next: /java/learn/collections/sets/