Tag Archives: iterators

java.util.LinkedList performance

by Mikhail Vorontsov

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 ListIterator

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 LinkedList node.

Author is aware of only two cases when you could use a LinkedList:

  1. 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 LinkedList head/tail is very fast. Nevertheless, consider using java.util.ArrayDeque in this case. It is also optimized for fast head/tail operations (more on this later).
  2. You need to add/remove elements from the middle of the list too often.

Continue reading