When to use ArrayList vs LinkedList in Java

ArrayList and LinkedList are two popular concrete implementations of List interface from Java's popular Collection framework. Being List implementation both ArrayList and LinkedList are ordered, the index based and allows duplicate. Despite being from same type hierarchy there are a lot of differences between these two classes which makes them popular among Java interviewers. The main difference between ArrayList vs LinkedList is that former is backed by an array while later is based upon linked list data structure, which makes the performance of add(), remove(), contains() and iterator() different for both ArrayList and LinkedList.

The difference between ArrayList and LinkedList is also an important Java collection interview questions, as much popular as Vector vs ArrayList or HashMap vs HashSet in Java. Sometimes this is also asked as for when to use LinkedList and when to use ArrayList in Java. 

In this Java collection tutorial, we will compare LinkedList vs ArrayList on various parameters which will help us to decide when to use ArrayList over LinkedList in Java. 

Btw, we will not focus on the array and linked list data structure much, which is subject to data structure and algorithm, we'll only focus on the Java implementations of these data structures which are ArrayList and LinkedList. 

If you want to learn more about array and linked list data structure itself, I suggest you check Algorithms and Data Structures - Part 1 and 2 By Robert Horvick, a free course form Pluralsight. 

It explains essential data structure in Java programming language and most importantly teaches you when to use which data structure, a good refresher for those who are preparing for coding interviews too. 





When to use ArrayList vs LinkedList in Java

Before comparing differences of ArrayList and LinkedList, let's see What is common between ArrayList and LinkedList in Java :

1) Both ArrayList and LinkedList are an implementation of List interface, which means you can pass either ArrayList or LinkedList if a method accepts the java.util.List interface. 

Btw, if you are new to Java's collections framework then I suggest you to first go through Java Fundamentals: Collections by Richart Warburton. It's an online Java course on Pluralsight, which you can avail free by signing their 10-day free trial. IMHO, it's worth going through that course to learn Java collections in right way. 

When to use ArrayList vs LinkedList in Java


2) Both ArrayList and LinkedList are not synchronized, which means you can not share them between multiple threads without external synchronization. See here to know How to make ArrayList synchronized in Java.

3) ArrayList and LinkedList are ordered collection e.g. they maintain insertion order of elements i.e. the first element will be added to the first position.


4) ArrayList and LinkedList also allow duplicates and null, unlike any other List implementation e.g. Vector.

5) Iterator of both LinkedList and ArrayList are fail-fast which means they will throw ConcurrentModificationException if a collection is modified structurally once Iterator is created. They are different than CopyOnWriteArrayList whose Iterator is fail-safe.



Difference between LinkedList and ArrayList in Java

Now let's see some difference between ArrayList and LinkedList and when to use ArrayList and LinkedList in Java.


1) Underlying Data Structure

The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList. This will lead further differences in performance.


2) LinkedList implements Deque
Another difference between ArrayList and LinkedList is that apart from the List interface, LinkedList also implements Deque interface, which provides first in first out operations for add() and poll() and several other Deque functions. 

Also, LinkedList is implemented as a doubly linked list and for index-based operation, navigation can happen from either end (see Java Fundamentals: Collections).


3) Adding elements in ArrayList
Adding element in ArrayList is O(1) operation if it doesn't trigger re-size of Array, in which case it becomes O(log(n)), On the other hand appending an element in LinkedList is O(1) operation, as it doesn't require any navigation.


4) Removing element from a position
In order to remove an element from a particular index e.g. by calling remove(index), ArrayList performs a copy operation which makes it close to O(n) while LinkedList needs to traverse to that point which also makes it O(n/2), as it can traverse from either direction based upon proximity.


5) Iterating over ArrayList or LinkedList

Iteration is the O(n) operation for both LinkedList and ArrayList where n is a number of an element.


6) Retrieving element from a position
The get(index) operation is O(1) in ArrayList while its O(n/2) in LinkedList, as it needs to traverse till that entry. Though, in Big O notation O(n/2) is just O(n) because we ignore constants there. 

If you want to learn more about how to calculate time and space complexity for your algorithms using Big O notation, I recommend reading Grokking Algorithms by Aditya Bhargava, one of the most interesting books on this topic I have read ever. 

Difference between linked list and arraylist in Java



7) Memory
LinkedList uses a wrapper object, Entry, which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array. 

So memory requirement seems less in the case of ArrayList than LinkedList except for the case where Array performs the re-size operation when it copies content from one Array to another. 

If Array is large enough it may take a lot of memory at that point and trigger Garbage collection, which can slow response time.

From all the above differences between ArrayList vs LinkedList, It looks ArrayList is the better choice than LinkedList in almost all cases, except when you do a frequent add() operation than remove(), or get()

It's easier to modify a linked list than ArrayList, especially if you are adding or removing elements from start or end because linked list internally keeps references of those positions and they are accessible in O(1) time. 

In other words, you don't need to traverse through the linked list to reach the position where you want to add elements, in that case, addition becomes O(n) operation. For example, inserting or deleting an element in the middle of a linked list.  

In my opinion, use ArrayList over LinkedList for most of the practical purpose in Java.


Further Learning
Java Fundamentals: Collections

Thanks for reading this article so far, if you like this article then please share with your friends and colleagues. If you have any questions or doubts then please drop a note. 

12 comments:

  1. Nice post!

    Its also good to mention that ArrayList can be created with an initial array size so if you know how many items you're going to store in it you can speed up .add operations because re sizing the backed array won't be needed (unless adding more items than the initial capacity).

    ReplyDelete
    Replies
    1. Agree, Initializing List with initial capacity is very good practice to reduce load on Garbage collector and improve performance. On another note, I think LinkedList is a special implementation of List interface, which is only suitable for sequential access e.g. stacks and queues. When you start using LinkedList as array instead of linked list e.g. calling get(1), an index access you won't get O(1) performance like ArrayList, until it's very slow O(n). So always use LinkedList when you need sequential access and use ArrayList when you need random access.

      Delete
  2. Just to make sure I understand clearly, let's say I am building a list that is going to be an attribute of a domain object. It is going to created (add) and then most likely read through as needed. But not changed and not really direct index accessed. In that case despite the slightly larger memory size, the LinkedList would actually make more sense. Just making sure I read correctly.

    ReplyDelete
  3. Don't forget that when using an iterator you can .remove() while iterating causing an extremely efficient and fast removal.

    ReplyDelete
  4. I know ArrayList is faster than LinkedList in most of cases e.g. getting an element form beginning, middle and end, does any one knows, when LinkdList is faster than ArrayList? I can think of only adding at the beginning, because there linked list doesn't resize, it just a pointer change, while array may resize, which is copy operation. Anything other case??

    ReplyDelete
    Replies
    1. Hi Grasshoper... I think linkedlist is considered to be faster in cases where you need to frequently insert and remove elements from the list. This is because even though it might need to traverse a particular location before it can insert, once it reaches the particular location it will just point the prev's next to itself and the former prev's next to its own next. Consider this same action in array list, where you may reach the location faster using the index but when u insert in middle, you need to move all the elements following it by one, this can cause a re-size of array to. Similar is the case when u consider removal process. Hence if you know that you will be constantly modifying the internal structure it would be better to use an LinkedList.

      Thank you.

      Delete
  5. I couldnt understand that. How array resizing for arraylist willbe done in log n ? I think it should be n

    ReplyDelete
    Replies
    1. Yeah, I was about to point out the same thing. It's O(n) since you need to copy each element in the old array into the new one.

      Delete
    2. I think logn is for array get() operation in average case, inlcudin O(n) worst case when resize can happen. By the way, why does array copy needs to be O(n), isn't System.arrayCopy() can copy in blocks to include more than one element at a time?

      Delete
  6. There is no such thing as O(n/2)

    ReplyDelete
  7. One more difference you can point out is that LinkedList is also a queue but ArrayList is not, which is only true after java 6 onwards, but yes its still a difference.

    ReplyDelete