Iterating over either kind of List is practically equally cheap. So depending on the operations you intend to do, you should choose the implementations accordingly. 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. 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. 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) ( n/4 steps) on average, though O(1) for index = 0.ĪrrayList, on the other hand, allow fast random read access, so you can grab any element in constant time. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. LinkedList allows for constant-time insertions or removals using iterators, but only sequential access of elements. 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) ListIterator.add(E element) is O(n) (with n/2 steps on average).Iterator.remove() is O(n) (with n/2 steps on average).remove(int index) is O(n) (with n/2 steps on average).add(int index, E element) is O(n) (with n/2 steps on average).add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied.index = 0), and n/2 steps in worst case (middle of list) Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. remove(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use removeFirst() and removeLast()).add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use addFirst() and addLast()/ add()).get(int index) is O(n) (with n/4 steps on average), but O(1) when index = 0 or index = list.size() - 1 (in this case, you can also use getFirst() and getLast()).ArrayList implements it with a dynamically re-sizing array.Īs with standard linked list and array operations, the various methods will have different algorithmic runtimes. LinkedList implements it with a doubly-linked list. LinkedList and ArrayList are two different implementations of the List interface. In LinkedList adding an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than ArrayList. TLDR, in ArrayList accessing an element takes constant time and adding an element takes O(n) time. If you're not sure - just start with ArrayList. It describes how the cost of each operation grows with the size of the list, not the speed of each operation.Summary ArrayList with ArrayDeque are preferable in many more use-cases than LinkedList. Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. long nano1 = System.nanoTime() įor(int i = 0 i arrL = new LinkedList() I mentioned size, because if I reduce the number of elements to 50000, LinkedList performs better and initial statements hold true. Is there anything I'm doing wrong, or the initial statements about LinkedList and ArrayList does not hold true for collections of size 5000000? It took less time than LinkedList for adding as well as fetching them from Collection. Now to verify my above two statements, I wrote below sample program… But I'm surprised that my above statements were proven wrong.ĪrrayList outclassed Linkedlist in both the cases. not grabbing the element in middle, still LinkedList will outclass `ArrayList. So by looking at this, I concluded that if I've to do just sequential insert in my collection for say 5000000 elements, LinkedList will outclass ArrayList.Īnd if I've to just fetch the elements from collection by iterating i.e. add is O(1) amortized, but O(n) worst-case since the array must be resized and copied.I was following a previous post on this that says: