Wednesday, 18 May 2016

Difference between ArrayList and LinkedList in Java

In Java collections framework ArrayList and LinkedList are two different implementations of List interface (LinkedList also implement Deque interface though).

LinkedList is implemented using a doubly linked list concept where as ArrayList internally uses an array of Objects which can be resized dynamically.

In most of the cases we do use ArrayList and it works very well but there are some use cases where using LinkedList may be a better choice.

So let's see some of the differences between ArrayList and LinkedList, it will help you in making an informed choice when to use ArrayList and when a LinkedList.

ArrayList Vs LinkedList

ArrayList class provides a constructor ArrayList(int initialCapacity) even if the default constructor ArrayList() is used an empty list is constructed with an initial capacity of ten. Where as LinkedList just provides one constructor LinkedList() which constructs an empty list. Note that in LinkedList there is no provision of initial capacity or default capacity.

What it means is that if elements are added at the last every time and capacity is not breached then ArrayList will work faster because it already has an initial capacity and just need to add that element at the index in the underlying array. Where as in LinkedList a new node has to be created and references for Next and Prev are to be adjusted to accommodate the new Node.

The above mentioned case for add is something we do most of the time while using arraylist or use get(int index) which also is faster in arraylist and that's why we normally use ArrayList, even JavaDocs advocate the same thing -
https://docs.oracle.com/javase/tutorial/collections/implementations/list.html

Let's go through some of the operations to see which implementation of list shines where -

  • Adding an element - If you are frequently adding element at the beginning of the list then LinkedList may be a better choice because in case of ArrayList adding at the beginning every time will result in shuffling all the existing elements within the underlying array by one index to create space for the new element.
    Even in the case of adding at the last ArrayList may give O(n) performance in the worst case. That will happen if you add more elements than the capacity of the underlying array, as in that case a new array (1.5 times the last size) is created, and the old array is copied to the new one.
    So for LinkedList add(e Element) is always O(1) where as for ArrayList add(e Element) operation runs in amortized constant time, that is, adding n elements requires O(n) time.
  • Retrieving an element - Retrieving an element from the list using get(int index) is faster in ArrayList than in LinkedList. Since ArrayList internally uses an array to store elements so get(int index) means going to that index directly in the array. In Linked list get(int index) will mean traversing through the linked list nodes.
    So for LinkedList get(int index) is O(n) where as for ArrayList get(int index) is O(1).
  • Removing an element - If you are removing element from a list using the remove(int index) method then for LinkedList class it will be O(n) as list has to be traversed to get to that index and then the element removed. Though the LinkedList provides methods like removeFirst() and removeLast() to remove the first or last element and in that case it will be O(1).
    In case of ArrayList getting to that index is fast but removing will mean shuffling the remaining elements to fill the gap created by the removed element with in the underlying array. It ranges from O(1) for removing the last element to O(n). Thus it can be said remove(int index) operation is O(n - index) for the arraylist.
  • Removing an element while iterating - if you are iterating the list and removing element using iterator.remove() then for LinkedList it is O(1) as the iterator is already at the element that has to be removed so removing it means just adjusting the Next and Prev references. Where as for ArrayList it is again O(n - index) because of an overhead of shuffling the remaining elements to fill the gap created by the removed elements.
  • One more difference is that LinkedList implementation provides a descendingIterator() which comes from implementing the Deque interface. descendingIterator() returns an iterator over the elements in this deque in reverse sequence.
    In ArrayList there is no such iterator.

That's all for this topic Difference between ArrayList and LinkedList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. Difference between Array and ArrayList in Java
  2. Difference between ArrayList and Vector in Java
  3. Difference between HashMap and ConcurrentHashMap in Java
  4. HashSet Vs LinkedHashSet Vs TreeSet in Java
  5. How to sort arraylist of custom objects in Java
  6. Java Collections interview questions

You may also like -

No comments:

Post a Comment