We will discuss
LinkedList performance in this article. Generally, it is a bad idea to use it in performance-critical code. But, sometimes you may need it…
LinkedList is a list implementation with each node having pointers to previous and next nodes. Such implementation allows to add/remove/update elements fast, but only if:
- Either they are first/last elements or
- You have scrolled to required element using
In all other cases list modification is O(n) complexity operation. Access to list elements (
get) is also O(n) operation (actually, list will scroll either from head or from tail, so it would take no more than
size() / 2 operations to access any
Author is aware of only two cases when you could use a
You are implementing a FIFO buffer and you don’t need to add/remove elements to the middle of the buffer (or rarely need to do it). Adding/removing from
LinkedListhead/tail is very fast. Nevertheless, consider using
java.util.ArrayDequein this case. It is also optimized for fast head/tail operations (more on this later).
- You need to add/remove elements from the middle of the list too often.