Four Access Patterns: Choose a List and Say What It Costs

Four workloads. For each, choose a list and say what the alternative would have cost. Write all four down before opening the reveal.

The four workloads
	The workload
1	Read a million rows from a file, appending each, then walk them once
2	Keep the fifty most recent events, adding at the front and dropping from the end
3	A lookup table of ten thousand rows, read by index inside a tight loop
4	Build a list of a hundred thousand, then remove every third element by index

The four choices, and what the other option would have cost

Each workload, the choice, and the alternative's cost
	Choose	Because	The alternative costs
1	`ArrayList`, sized ahead	Append and walk are both its best case	`LinkedList` adds two pointers per element for no gain
2	`ArrayDeque`	Constant at both ends, with no per-element pointers	`LinkedList` also works; `ArrayList` shifts fifty elements per add
3	`ArrayList`	Positional reads are arithmetic	`LinkedList` turns each read into a walk, so the loop goes quadratic
4	`ArrayList` with `removeIf`	One pass, each element moved at most once	Removing by index in a loop shifts the tail each time

The fourth is the one worth pausing on, because the answer is not a different class. Removing by index in a loop is quadratic on an array list and quadratic on a linked one — removeIf is what makes it linear on either.