When to use LinkedList<> over ArrayList<>?

Question

I've always been one to simply use List<String> names = new ArrayList<String>();
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

It's an efficiency question. LinkedList is fast for adding and deleting elements, but slow to access a specific element. ArrayList is fast for accessing a specific element but can be slow to add to either end, and especially slow to delete in the middle.

http://www.javafaq.nu/java-article1111.html -- goes more in depth, as does http://en.wikipedia.org/wiki/Linked_list

Answer 2

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

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

Answer 3

It depends upon what operations you will be doing more on the List.

ArrayList is faster to access an indexed value. It is much worse when inserting or deleting objects.

To find out more, read any article that talks about the difference betwen arrays and linked lists.

Answer 4

When should i use LinkedList?

• When you need efficient removal in between elements or at the start.
• When you don't need random access to elements, but can live with iterating over them one by one

When should i use ArrayList?

• When you need random access to elements ("get the nth. element")
• When you don't need to remove elements from between others. It's possible but it's slower since the internal backing-up array needs to be reallocated.
• Adding elements is amortized constant time (meaning every once in a while, you pay some performance, but overall adding is instantly done)

Answer 5

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 6

LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically resizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList

• get is O(n)
• add is O(1)
• remove is O(n)
• Iterator.remove is O(1)

For ArrayList

• get is O(1)
• add is O(1) amortized, but O(n) worst-case since the array must be resized and copied
• remove is O(n)

LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.

ArrayLists, on the other hand, allow random access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 6). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

It's worth noting that Vector also implements the List interface and is almost identical to ArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.

Answer 7

ArrayList is what you want. LinkedList is almost alway a (performance) bug.

Why LinkedList sucks:

• It uses lots of small memory objects, and therefore impacts performance across the process.
• Lots of small object are bad for cache-locality.
• Any indexed operation is requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if ArrayList was used.
• Getting good performance is tricky.
• Even when big-O performance is the same as ArrayList, it is probably going to be significant slower anyway.
• It's jarring to see LinkedList in source because it is probably the wrong choice.

Answer 8

If your code has add(0) and remove(0), use a LinkedList and it's prettier addFirst() and removeFirst() methods. Otherwise, use ArrayList.

And of course, ImmutableList is your best friend.

Answer 9

Yeah, I know, this is an ancient question, but I'll throw in my two cents:

LinkedList is almost always the wrong choice, performance-wise. There are some very specific algorithms where a LinkedList is called for, but those are very, very rare and the algorithm will usually specifically depend on LinkedList's ability to insert and delete elements in the middle of the list relatively quickly, once you've navigated there with a ListIterator.

There is one common use case in which LinkedList outperforms ArrayList: that of a queue. However, if your goal is performance, instead of LinkedList you should also consider using an ArrayBlockingQueue (if you can determine an upper bound on your queue size ahead of time, and can afford to allocate all the memory up front), or this CircularArrayList implementation. (Yes, it's from 2001, so you'll need to generify it, but I got comparable performance ratios to what's quoted in the article just now in a recent JVM)

Answer 10

An important feature of a linked list (which I didn't read in another answer) is the concatenation of two lists. With an array this is O(n) (+ overhead of some reallocations) with a linked list this is only O(1) or O(2) ;-)

For the Java LinkedList this is not true. See this question.

Answer 11

Algorithm     ArrayList   LinkedList
access front     O(1)         O(1)
access back      O(1)         O(1)
access middle    O(1)         O(N)
insert at front  O(N)         O(1)
insert at back   O(1)         O(1)
insert in middle O(N)         O(1)

http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html

ArrayLists are good for write-once-read-many or appenders, but bad at add/remove from the front or middle.

Answer 12

An array list is essentially an array with methods to add items etc. (and you should use a generic list instead). It is a collection of items which can be accessed through an indexer (for example [0]). It implies a progression from one item to the next.

A linked list specifies a progression from one item to the next (Item a -> item b). You can get the same effect with an array list, but a linked list absolutely says what item is supposed to follow the previous one.

Answer 13

(note: might read a little oddly; that is because I merged a virtually identical .NET question; C# and Java are close enough that the concepts are identical)

Well, you should avoid ArrayList unless you are using .NET 1.1 (or micro-framework) - prefer typed collections like List<T> where possible.

The difference comes from the cost of traversal and manipulation. It is trivial to remove a node from the start or middle of a linked list, since you just re-link the nodes (likewise insert at any point). Removing an element from the start or middle of an array-backed list (including ArrayList and List<T>) involves copying all the elements above that point (as does inserting).

In both cases, inserting at the end is cheap (although the List<T> etc will occasionally have to resize the underlying array to make space, but it does this in a fairly sensible way).

If you just want to append, then use List<T> etc.