Recently, The Java Programmer published “Difference between ArrayList and LinkedList in Java“, asserting different cases of when to prefer one
List implementation over another. It’s a link full of conventional wisdom, and while it has some good information, it’s also wrong.
Here’s the channel’s factoid on
LinkedList, as of 2017/Apr/25 (prior to it having been changed to point to the page you’re reading):
LinkedList is almost always slower than ArrayList/ArrayDeque. It might be best to use ArrayList/ArrayDeque to start. But if you have an actual performance problem, you can compare the two for your specific case. Otherwise, just use ArrayDeque. (It too has O(1) performance for insert-at-beginning, and unlike LinkedList is actually fast).
The “Difference” page says that
ArrayList uses an internal array to represent stored objects, while a
LinkedList uses a doubly-linked list internally. In this, it’s correct.
The next point of comparison is entitled “Searching.” Here’s what it says about
An elements can be retrieved or accessed in O(1) time. ArrayList is faster because it uses array data structure and hence index based system is used to access elements.
An element can be accessed in O(N) time. LinkedList is slower because it uses doubly linked list and for accessing an element it iterates from start or end (whichever is closer).
First off, in the interest of honesty, the last bit of information – that it iterates from either forward or backward, depending on which is closer – was a surprise to me (although it’s perfectly logical.) It’s also accurate.
However, this isn’t searching – it’s element access. Access and searching are different things; it’s
list.contains(matchingObject). This is important;
contains() will have O(N) time for either
List implementation, whereas
ArrayList will have O(1) for
LinkedList will have O(N) for
The thing is:
LinkedList is not only O(N) for
get() but the nature of the internal implementation makes it slower than one might think, because of cache locality. In an
ArrayList, the element references are stored sequentially in memory; a
LinkedList potentially splatters the references all over the heap. (This is not entirely likely, but it’s possible.) Thus, a
LinkedList not only has O(N) performance for indexed access (where the
ArrayList has O(1)), but the O(N) is worse than one might expect.
For accessing elements, there’s no situation apart from accessing the first or last element where a
LinkedList competes with an
Note that programming hates absolutes. It’s fully possible to create situations in which that last claim is not entirely true… but they’re rare and unlikely.
Normally the insertion time is O(1). But in case array is full then array is resized by copying elements to new array, which makes insertion time O(N).
Insertion of an element in LinkedList is faster, it takes O(1) time.
Incomplete data is provided here. For one thing, the author conflates mutation with “insertion.” There are two different kinds of additive list mutations (where data is added to a
List): insertion (meaning that elements are prepended to other elements) and addition (where an element “follows” the last element in the list prior to mutation.)
Where the elements go as part of the additive mutation is really important, and it’s also important to note that the claim of
LinkedList‘s O(1) time is very much a single type of insertion.
ArrayList, a list append (i.e., calling
add(), which adds the provided element at the end of the list) has O(N) performance, but typically has O(1) performance. The O(N) complexity is because the internal array size might be exceeded by the addition of the element, in which case a new internal array is allocated, and the array references are copied over to the new internal array, and then the new element is appended. Thus, in the worst case, it is O(N), but this is misleading because:
- It’s fairly rare (the list resizes with a formula of
currentSize*1.5(the actual line is
int newCapacity = oldCapacity + (oldCapacity >> 1);, if you’re interested.)
- Java’s blits are very, very, very fast; Java uses the blit mechanism constantly, and let’s be real, modern CPUs are really good at this anyway.
So is it actually O(N), then? … given what conventional Big O notation means, yes, it is; it’s just that O(N) is a lot less expensive than one might think in this case. And typically, the
add() will be O(1) in actuality.
But what about
Insertion at the beginning or the end of the list is, in fact, O(1). This is even the common case (
linkLast(Object) by default.) However, if positional notation is used at all (i.e.,
add(int, Object) you degrade to O(N), because the LinkedList has to find the position at which the new element has to be inserted – and finding that position is O(N).
So what’s the conclusion?
ArrayList does in fact have O(N) performance for adds, but it’s close enough to O(1) in real world conditions that we can colloquially speak of it being likely as fast as
LinkedList‘s similar case… and if we add any kind of positional insertion,
ArrayList‘s degradation under the worst case is far better than
As usual, we can create situations under which this is not the case (for example, if we always insert after the first position in a
LinkedList, which will “search” one element and only that element) but these are fairly rare.
Let’s see about
Deletion of an element is slower as all the elements have to be shifted to fill the space created by deleted element.
Deletion of an element is faster in LinkedList because no elements shifting are required.
Well, um, no.
Here, the author is confusing complexity – big O notation – with speed, for
ArrayList. (He or she is wrong about
LinkedList in any event.)
ArrayList, deleting an element by index is indeed O(N) because the JVM does have to blit the elements after the removed element (it has to shift them all in the internal array.)
However, for a
LinkedList, it also has to find the elements around the element to remove – and if you recall, accessing a specific element for a
LinkedList is an O(N) complexity itself. Even though the removal is simple (it’s simply relinking the nodes before and after the removed element), actually finding those nodes is O(N), thus deletion is O(N) for LinkedList – and slower than
ArrayList, to boot.
Memory and Initial Capacity
The author says that an
ArrayList has a default internal capacity of 10. This is incorrect for Java 8. See this code.
For the rest of it, the author is correct; a
LinkedList is “empty” (there are no linked nodes internally); an
capacity references in the internal list, while a
LinkedList has a chain of objects, which will have higher memory consumption, but that’s not likely to matter unless your lists are huge.
The Comparison’s Conclusion
- As search or get operation is faster in ArrayList so it is used in the scenario where more search or get operations are required.
- As insertion or deletion of an element is faster in LinkedList so it is used in the scenario where more insertion and deletion operations are required.
The thing that the conclusion is missing is that “insertion and deletion” operations in
LinkedList typically involve searches and gets – which are terrible for
LinkedList – and therefore for even the operations that
LinkedList is potentially better,
ArrayList will typically perform better.
The factoid stands. If you need a
ArrayList first, then
ArrayDeque if your access patterns demand… use
LinkedList only after exhausting other possibilities.