ComparisonDifficulty: Intermediate1 min

Choosing Between ArrayList, LinkedList and ArrayDeque

Both lists are correct for every workload; the operation in your hot loop decides which is fast.

ArrayList and LinkedList give correct results for every workload, so the choice is only about speed and memory: which operations are in the frequently run part of your code. The table compares the common operations, and ArrayDeque, a double-ended queue backed by an array, belongs in the decision too.

The common operations, on each list
Operation	`ArrayList`	`LinkedList`	Which wins
Append at the end	Constant, averaged	Constant	A tie; in practice `ArrayList`
Read by position	Constant	Walks to it	`ArrayList`, by a lot
Insert or remove at the front	Shifts everything	Constant	`LinkedList`
Insert in the middle, while iterating	Shifts the rest	Constant, through the iterator (the object walking the list)	`LinkedList`
Walk from start to end	Constant per element	Constant per element	A tie

The decision rule. Use ArrayList unless you have a specific reason not to, and the reason has to be inserting or removing at the front or in the middle, often, on a long list. Reading by position and appending are both common, and ArrayList is better or equal at both.

When that reason turns up, check ArrayDeque before LinkedList. It is constant at both ends, stores its elements side by side like an array list, and carries none of the per-element pointer overhead.

← → move through sections and cards