Difference between ArrayList and LinkedList

1619
Mar 20, 2016

LinkedList and ArrayList both are ordered collections and implements List interface. These two Arraylist and linkedlist implementation has their own advantage and disadvantages and should be used based on the need. Here is a comparison and difference between these two implementations.

#PointLinkedListArrayList
1NatureLinkedList is Sequential AccessArrayList is Random Access
2Internal ImplementationLinkedList is implemented by Doubly-linked listArrayList is implemented by Array
3get(index) complexityLinkedList is of O(n), needs to iterate over elementsArrayList is of O(1), direct access
4add(element) complexityLinkedList is O(1), always has pointer to last element, just add a new nodeArrayList is O(1)
* O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied
5add(index,element) complexityLinkedList is of O(n), need to iterate till nth elementArrayList is of O(n-index), (n-index) element needs to be shifted
* O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied
6ListIterator.add(element) complexityLinkedList is of O(1), only pointers needs to be adjustedArrayList is of O(n-index), (n-index) element needs to be shifted
* O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied
7remove(index) complexityO(n), need to iterate to reach nth elementO(n-index), (n-index) element needs to be shifted
8ListIterator.remove(element) complexityO(1), only pointers needs to be adjustedO(n-index), (n-index) element needs to be shifted
* O(n) in worst-case if array capacity reached to modCount and array needs to be resized and copied
9Memory usagesMore, previous and next pointers to be maintainedLess


In summary if most of the operations are insertion/deletion at beginning or end of list then linked-list is most useful (for example implementation of Queues) otherwise ArrayList has more advantages over LinkedList.

comments powered by Disqus

© Copyright 2017