When to use LinkedList and when to use ArrayList?
- The ArrayList class extends AbstractList and implements the List interface. ArrayList supports dynamic arrays that can grow as needed.
On the other hand
- The LinkedList class extends AbstractSequentialList and implements the List interface. It provides a linked-list data structure.
So when should we use one over another?
In so many codes, I assume you are using ArrayList like the following:
List<String> names = new ArrayList<String>();
Here is the fact. When it comes to speed, you need to focus on these things more than ever.
LinkedList and ArrayList are two different implementations of the List interface. LinkedListimplements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.
- get(int index)is O(n/4) average
- add(E element)is O(1)
- add(int index, E element)is O(n/4) average
but O(1) when index = 0 <— main benefit of LinkedList<E>
- remove(int index)is O(n/4) average
- remove()is O(1) <— main benefit of LinkedList<E>
- add(E element)is O(1) <— main benefit of LinkedList<E>
Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)
- 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/2) average
- remove(int index)is O(n/2) average
- remove()is O(n/2) average
- add(E element)is O(n/2) average
Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)
- LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backward, but finding a position in the list takes time proportional to the size of the list. Javadoc says “operations that index into the list will traverse the list from the beginning or the end, whichever is closer”, so those methods are O(n/4) on average, though O(1) for index = 0.
- ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
- 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.)
The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).
1) Deletion: LinkedList remove operation gives
O(1) performance while ArrayList gives variable performance:
O(n) in worst case (while removing first element) and
O(1) in best case (While removing last element).
Conclusion: LinkedList element deletion is faster compared to ArrayList.
Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.
2) Inserts Performance: LinkedList add method gives
O(1) performance while ArrayList gives
O(n) in worst case. Reason is same as explained for remove.
- Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don’t have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.
- The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 – 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you’re going to add a lot of elements, construct the ArrayList with a higher initial capacity.
There are few similarities between these classes which are as follows:
- Both ArrayList and LinkedList are implementation of List interface.
- They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
- Both these classes are non-synchronized and can be made synchronized explicitly by using
- The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).
When to use LinkedList and when to use ArrayList?
1) The insert and remove operations give good performance –
O(1)- in LinkedList compared to ArrayList-
O(n)-). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.
2) Search operations are faster in Arraylist –
O(1)-but not in LinkedList –
O(n)- so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.