Practice: Choosing a List or Deque for Four Access Patterns

Appending, working at both ends, reading by index and removing in bulk: pick a class and name the cost.

The right list depends on the operation done most: positional reads and appends favour ArrayList, work at both ends favours ArrayDeque. For each workload below, choose a class, a list or a deque (a queue you can use from both ends), and say what the alternative would have cost, all four before you open the answer.

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 orders, then remove every cancelled one

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 becomes quadratic
4	`ArrayList` with `removeIf`	One pass, each element moved at most once	Removing one at a time in a loop shifts the tail every time

The fourth is the one to pause on, because the answer is not a different class. Removing matches one at a time in a loop is quadratic on both lists; removeIf makes it linear on either.

← → move through sections and cards