ArrayList vs LinkedList in Java

In this post, we will discuss the differences between ArrayList and LinkedList in Java.


 

1. Underlying Data Structure

Both ArrayList and LinkedList are two different implementations of the List interface. ArrayList is a resizable-array implementation whereas LinkedList is a Doubly-linked list implementation of the List interface.

 

2. Capacity

The capacity of an ArrayList at least as large as the list size and it grows automatically as more elements are added to it. Its default capacity is just 10 elements. Since resizing degrades performance, it is always better to specify the initial capacity of the ArrayList during initialization itself.

On the other hand, the capacity of an LinkedList is exactly equal to the list size and we cannot specify the capacity during the list initialization.

 

3. Memory Overhead

LinkedList comes up with memory overhead since every element is a node object which stores pointers to the next and previous elements. But since the memory needed for each node might not be contiguous, LinkedList won’t result in any major performance issues.

ArrayList, however, needs a contiguous block of memory in heap for allocating the dynamic array. This might be space efficient but sometimes costs performance issues when the Garbage Collector ends up doing some work to free up a necessary contiguous block of memory in heap.

 

4. Caching

Traversing through the elements of an ArrayList is always faster than a LinkedList. This is because of Sequential locality or locality of reference where hardware will cache contiguous blocks of memory for faster read access.

 

5. Performance
5.1. Insertion at the end

add(E element)

The add operation for an ArrayList runs in amortized O(1) time, but is O(n) in the worst case. The worst case happens when maximum capacity of ArrayList is reached and elements from the old array is copied to the new array, which is double the size of the old array.

For a LinkedList, add is a O(1) time operation since the specified element is appended to the end of the list and pointer to the last node is maintained by LinkedList class.

 

5.2. Insertion at the specified index

add(int index, E element)

The add operation at specified index is O(n) time operation for an ArrayList as it requires shifting of all elements past the insertion point for accommodating the new element.

For a LinkedList, insertion at the specified index costs O(n) as it has to traverse the list from the beginning or the end, to get to the specified index.

 

5.3. Deletion

remove(int index)

For both ArrayList and LinkedList, remove operation takes O(n) time. For an ArrayList, it requires shifting of all latter elements and for the LinkedList, it has to traverse the list from the beginning or the end, whichever is closer to the specified index.

 

5.4. Read

get(int index)

An ArrayList allows fast random read access, so get operation takes only O(1) time.

For a LinkedList, get operation takes O(n) time since it has to traverse the list from the beginning or the end, whichever is closer.
 

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz