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.

- Refer post
__How ArrayList works internally in Java__to know more about internal working of ArrayList. - Refer post
__How Linked List class works internally in Java__to know more about internal working of LinkedList.

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*. Thus it can be said remove(int index) operation is O(n - index) for the arraylist.**O(1)**for removing the last element to**O(n)****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__

**You may also like - **

## No comments:

## Post a Comment