When to use LinkedList over ArrayList in Java?

Question

I've always been one to simply use:

List<String> names = new ArrayList<>();

I use the interface as the type name for portability, so that when I ask questions such as these I can rework my code.

When should LinkedList be used over ArrayList and vice-versa?

Answer 1

ArrayList and LinkedList have their own pros and cons.

ArrayList uses contiguous memory address compared to LinkedList which uses pointers toward the next node. So when you want to look up an element in an ArrayList is faster than doing n iterations with LinkedList.

On the other hand, insertion and deletion in a LinkedList are much easier because you just have to change the pointers whereas an ArrayList implies the use of shift operation for any insertion or deletion.

If you have frequent retrieval operations in your app use an ArrayList. If you have frequent insertion and deletion use a LinkedList.

Answer 2

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 to 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. 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 an 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.

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.

Answer 3

ArrayList is randomly accessible, while LinkedList is really cheap to expand and remove elements from. For most cases, ArrayList is fine.

Unless you've created large lists and measured a bottleneck, you'll probably never need to worry about the difference.

Answer 4

In addition to the other good arguments above, you should notice ArrayList implements RandomAccess interface, while LinkedList implements Queue.

So, somehow they address slightly different problems, with difference of efficiency and behavior (see their list of methods).

Answer 5

I have read the responses, but there is one scenario where I always use a LinkedList over an ArrayList that I want to share to hear opinions:

Every time I had a method that returns a list of data obtained from a DB I always use a LinkedList.

My rationale was that because it is impossible to know exactly how many results am I getting, there will be not memory wasted (as in ArrayList with the difference between the capacity and actual number of elements), and there would be no time wasted trying to duplicate the capacity.

As far a ArrayList, I agree that at least you should always use the constructor with the initial capacity, to minimize the duplication of the arrays as much as possible.

Answer 6

Here is the Big-O notation in both ArrayList and LinkedList and also CopyOnWrite-ArrayList:

ArrayList

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Based on these you have to decide what to choose. :)