Collections Framework

Lists

ArrayList is the default list: contiguous storage, O(1) index access, amortized O(1) append. LinkedList almost never wins — its theoretical O(1) insertion is buried under cache-hostile node chasing.

ArrayList: backed by a growable array; grows ~1.5× when full
Middle insertion/removal in ArrayList is O(n) — elements shift
LinkedList is O(n) to reach any position; each node is a separate allocation
Presize with new ArrayList<>(expectedSize) when the size is known
List.copyOf(c) for defensive immutable copies; subList(a, b) returns a live range view, not a copy
List.of(...) is truly immutable — null-hostile, throws UnsupportedOperationException on any mutation attempt

ArrayList vs LinkedList
Operation	`ArrayList`	`LinkedList`
`get(i)`	O(1)	O(n) — walks nodes
`add(e)` at end	O(1) amortized	O(1)
`add(i, e)` middle	O(n) shift, cache-friendly	O(n) walk + O(1) link
`Iterator.remove`	O(n)	O(1) at cursor
Memory per element	one reference slot	node object: 2 pointers + header (~24 B extra)
Cache behavior	excellent (contiguous)	poor (pointer chasing)

The performance books are blunt here: on modern hardware, memory locality dominates (Hardware Memory). An ArrayList traversal streams through cache lines; a LinkedList traversal takes a potential cache miss per element. Even for insert-heavy workloads, ArrayList or ArrayDeque usually measures faster. Choose LinkedList only for genuine cursor-based editing via ListIterator.

ListIterator: the one job LinkedList still wins

ListIterator<String> it = names.listIterator();
while (it.hasNext()) {
    String name = it.next();
    if (name.isBlank()) {
        it.remove();                // O(1) at the cursor on a LinkedList
    } else if (name.equals("TBD")) {
        it.set("Unknown");          // replace in place, no second lookup
    }
}
while (it.hasPrevious()) {
    it.previous();                  // bidirectional — plain Iterator cannot go back
}

Everyday list work

List<String> names = new ArrayList<>(1000);   // presized: no regrowth copies
names.add("Ada");
names.set(0, "Grace");
names.sort(Comparator.naturalOrder());          // in-place TimSort
List<String> top10 = List.copyOf(names.subList(0, 10)); // materialize the view