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 this, I can rework my code.
When should LinkedList
be used over ArrayList
and viceversa?
3
Summary ArrayList
with ArrayDeque
are preferable in many more usecases than LinkedList
. If you’re not sure — just start with ArrayList
.
TLDR, in ArrayList
accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList
inserting an element takes O(n) time and accessing also takes O(n) time but LinkedList
uses more memory than ArrayList
.
LinkedList
and ArrayList
are two different implementations of the List interface. LinkedList
implements it with a doublylinked 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<E>
get(int index)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = list.size()  1
(in this case, you can also usegetFirst()
andgetLast()
). One of the main benefits ofLinkedList<E>
add(int index, E element)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = list.size()  1
(in this case, you can also useaddFirst()
andaddLast()
/add()
). One of the main benefits ofLinkedList<E>
remove(int index)
is O(n) (with n/4 steps on average), but O(1) whenindex = 0
orindex = list.size()  1
(in this case, you can also useremoveFirst()
andremoveLast()
). One of the main benefits ofLinkedList<E>
Iterator.remove()
is O(1). One of the main benefits ofLinkedList<E>
ListIterator.add(E element)
is O(1). One of the main benefits ofLinkedList<E>
^{Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)}
For ArrayList<E>
get(int index)
is O(1). Main benefit ofArrayList<E>
add(E element)
is O(1) amortized, but O(n) worstcase since the array must be resized and copiedadd(int index, E element)
is O(n) (with n/2 steps on average)remove(int index)
is O(n) (with n/2 steps on average)Iterator.remove()
is O(n) (with n/2 steps on average)ListIterator.add(E element)
is O(n) (with n/2 steps on average)
^{Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)}
LinkedList<E>
allows for constanttime insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says “operations that index into the list will traverse the list from the beginning or the end, whichever is closer”, so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0
.
ArrayList<E>
, on the other hand, allow fast random read 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 (1.5 times 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 performancesensitive, you shouldn’t worry about this — they’re both constants.)
The main benefits of using a LinkedList
arise when you reuse existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList
means following the links in O(n) (n/2 steps) for worst case, whereas in an ArrayList
the desired position can be computed mathematically and accessed in O(1).
Another benefit of using a LinkedList
arises when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList
. Note that ArrayDeque
may be a good alternative to LinkedList
for adding and removing from the head, but it is not a List
.
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 – 1.8). 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.
If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on…). Addition of elements takes linear time in LinkedList as stated above.
An ArrayList is a growable array. It is just like a regular array. Under the hood, when an element is added, and the ArrayList is already full to capacity, it creates another array with a size which is greater than previous size. The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.
6
 27
One thing many people forget is that ArrayList is compact in memory which means that it’s more cache friendly than LinkedList. LinkedList could be spread out all over RAM, while ArrayList is always snuggly packed together to take advantage of spacial locality. This has important real world ramifications.
– AminMMar 26, 2021 at 1:52
 3
@AminM Only the object references are compact. The objects themselves can be scattered… Until we get value types.
– swpalmerJan 22 at 19:52
 4
@swpalmer certainly. However, in a LinkedList just to FIND the item you’re looking for you’re touring your RAM layout. Whereas with the ArrayList you can scan through it with very few cache misses. Cache misses are a big deal for performance.
– AminMJan 24 at 0:23
 2
@AminM My point is that to find what you are looking for you likely still need to follow that reference and possibly suffer a cache miss. Unless all you care about is reference identity. I get that in the linked case you can suffer the cache miss just getting to the references themselves. I’m just saying Java arrays suffer from cache misses in another way as well… until Valhalla.
– swpalmerJan 24 at 0:39
 4
@swpalmer my point is that its significantly less cache misses. In the extreme. Others have posted performance comparisons here. You can be sure that you’ll get much worse performance with a LinkedList almost always.
– AminMJan 24 at 0:43
Thus far, nobody seems to have addressed the memory footprint of each of these lists besides the general consensus that a LinkedList
is “lots more” than an ArrayList
so I did some number crunching to demonstrate exactly how much both lists take up for N null references.
Since references are either 32 or 64 bits (even when null) on their relative systems, I have included 4 sets of data for 32 and 64 bit LinkedLists
and ArrayLists
.
Note: The sizes shown for the ArrayList
lines are for trimmed lists – In practice, the capacity of the backing array in an ArrayList
is generally larger than its current element count.
Note 2: (thanks BeeOnRope) As CompressedOops is default now from mid JDK6 and up, the values below for 64bit machines will basically match their 32bit counterparts, unless of course you specifically turn it off.
The result clearly shows that LinkedList
is a whole lot more than ArrayList
, especially with a very high element count. If memory is a factor, steer clear of LinkedLists
.
The formulas I used follow, let me know if I have done anything wrong and I will fix it up. ‘b’ is either 4 or 8 for 32 or 64 bit systems, and ‘n’ is the number of elements. Note the reason for the mods is because all objects in java will take up a multiple of 8 bytes space regardless of whether it is all used or not.
ArrayList:
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList:
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
1
 274
The problem with your math is that your graph greatly exaggerates the impact. You are modelling objects which each contain only an
int
, so 4 or 8 bytes of data. In the linked list, there are essentially 4 “words” of overhead. Your graph thus gives the impression that linked lists use “five times” the storage of array lists. This is wrong. The overhead is 16 or 32 bytes per object, as an additive adjustment, not a scaling factor.Sep 6, 2013 at 0:18
ArrayList
is what you want. LinkedList
is almost always a (performance) bug.
Why LinkedList
sucks:
 It uses lots of small memory objects, and therefore impacts performance across the process.
 Lots of small objects are bad for cachelocality.
 Any indexed operation 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 bigO performance is the same as
ArrayList
, it is probably going to be significantly slower anyway.  It’s jarring to see
LinkedList
in source because it is probably the wrong choice.
See also: Array versus linkedlist
Oct 12, 2016 at 3:58
Just see the quote from the author of LinkedList stackoverflow.com/a/42529652/2032701 and you’ll get a practical sense of the issue.
Dec 26, 2017 at 19:17
Bjarne Stroustrup has also discussed this extensively for C++
std::vector
(like JavaArrayList
) andstd::list
(like JavaLinkedList
).Apr 29 at 12:26
