Why LinkedList (Java) sucks? Performance comparison with ArrayList? When to use ArrayList over LinkedList?

Collection is the most used concept in Java after String, in collection framework we are mostly rely on ArrayList and LinkedList for keeping the objects in sequential form. these two are most used implementations of List interface but LinkedList always sucks in performance although LinkedList have some advantages as well. ArrayList is what you want. LinkedList is almost always a (performance) bug.

Why LinkedList sucks:

1. It uses lots of small memory objects internally to keep connecting the objects, and therefore impacts performance across the process.
2. Lots of small objects are bad for cache-locality.
3. 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.
4. Getting good performance is tricky.
5. Even when big-O performance is the same as ArrayList, it is probably going to be significantly slower anyway.
6. It's jarring to see LinkedList in source because it is probably the wrong choice.

Performance Comparison : 

Now we are going to see the performance of the ArrayList and LinkedList in some well known operations:

Operation           ArrayList   LinkedList

seek front            O(1)         O(1)

seek back             O(1)         O(1)

seek to index         O(1)         O(N)

insert at front       O(N)         O(1)

insert at back        O(1)         O(1)

insert after an item  O(N)         O(1)

LinkedList is almost always the wrong choice, performance-wise. There are some very specific algorithms where a LinkedList is called for, but those are very, very rare and the algorithm will usually specifically depend on LinkedList's ability to insert and delete elements in the middle of the list relatively quickly, once you've navigated there with a ListIterator.

LinkedList can be iterated in reverse direction using descendingIterator() while there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.

When to use which one over another one:

Now come to the conclusion when to use which LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList<E>

• get(int index) is O(n) (with n/4 steps on average)
• add(E element) is O(1)
• add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 main benefit of LinkedList<E>
• remove(int index) is O(n) (with n/4 steps on average)
• Iterator.remove() is O(1). main benefit of LinkedList<E>
• ListIterator.add(E element) is O(1) This is one of the main benefits of LinkedList<E>
• Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)

For ArrayList<E>

• get(int index) is O(1) main benefit of ArrayList<E>
• add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• add(int index, E element) is O(n) (with n/2 steps on average)
• remove(int index) is O(n) (with n/2 steps on average)
• Iterator.remove() is O(n) (with n/2 steps on average)
• ListIterator.add(E element) is O(n) (with n/2 steps on average)
• Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this; they're both constants.)