Card 05/ 08
All 8 cards
ComparisonDifficulty: Intermediate1 min
Which List Your Access Pattern Asks For
Both lists are correct for every workload. The choice is about which operations are in the hot part of your code, so the question to answer first is what that code actually does.
| 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, via the iterator | 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 middle, often, on a long list. Reading by position is common and appending is common, and ArrayList is better or equal at both.
When the reason does turn up, check ArrayDeque before LinkedList. It is constant at both ends, stores elements side by side like an array list, and carries none of the per-element pointer overhead.
- Java
- Java Collections
- Performance