The difference between ArrayList and LinkedList is that ArrayList is implemented using re-sizable array while LinkedList is implemented using doubly LinkedList.
There is much difference between ArrayList and LinkedList. Let’s see the below-mentioned differences between ArrayList and LinkedList-
ArrayList search operation is pretty fast compared to the LinkedList search operation. ArrayList gives the performance of O(1) while LinkedList performance is O(n) because ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side, LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.
In removal operation, LinkedList is much faster than ArrayList. LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing the first element) and O(1) in best case (While removing the last element) because LinkedList’s each element maintains two pointers (addresses) which point to the both neighbor elements in the list. Hence, removal only requires a 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.
Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array and copying content to a new array if array gets full which makes adding into ArrayList of O(n) in a worst case while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of the array.
LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds an actual object (data) but in the case of LinkedList, each node holds both data and address of the next and previous node.
When to use LinkedList and ArrayList in Java
- ArrayList is important if your application can live without Random access because ArrayList search complexity is O(1) while it’s O(n) in LinkedList.
- As explained above 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 an application then LinkedList is the best choice.
Similarities between ArrayList and LinkedList
- Both ArrayList and LinkedList are the implementations 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 Collections.synchronizedList method.
- The iterator and listIterator returned by these classes are fail-fast (if the 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).
If you liked this video, then please subscribe to our YouTube Channel for more video tutorials.