LinkedList
is almost always a (performance) bug:
- It uses lots of small memory objects, and therefore impacts performance across the process.
- Lots of small objects are bad for cache-locality.
- Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if
ArrayList
was used. - Getting good performance is tricky.
- Even when big-O performance is the same as
ArrayList
, it is probably going to be significantly slower anyway. - It’s jarring to see
LinkedList
in source because it is probably the wrong choice.