ArrayList vs. LinkedList — Which one is better?
ArrayList implements the RandomAccess interface, and LinkedList does not. Note thatCollections.binarySearch does take advantage of the RandomAccess property, to optimize searches. A LinkedList does not support efficient random access
An ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method. The get method is implemented forLinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. (see What is the advantage of using an Iterator compared to the get(index) method?)
An ArrayList is much faster than LinkedList doing a binary search on the large list of sorted element.
A LinkedList are more efficient speed wise than ArrayList when inserting and removing at random places in the list multiple times. If you’re just adding to the end of the list, anArrayList is what you want.
A LinkedList is faster than an ArrayList when elements are only added to the beginning of the list.
A LinkedList has a simple growth pattern of just adding and removing nodes when it needs to, but the ArrayList has a growth algorithm of (n*3)/2+1, meaning that each time the buffer is too small it will create a new one of size (n*3)/2+1 where n is the number of elements of the current buffer and there will be a significant amount of space wasted at the end.
The reversing a LinkedList using Collections.reverse. The internal algorithm does this, and gets reasonable performance, by using forward and backward iterators.

Advertisements