# When to use LinkedList over ArrayList in Java?

## 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?

### Accepted Answer

**Summary** `ArrayList`

with `ArrayDeque`

are preferable in *many* more use-cases than `LinkedList`

. If you're not sure — just start with `ArrayList`

.

`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 re-sizing 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)*when`index = 0`

or`index = list.size() - 1`

(in this case, you can also use`getFirst()`

and`getLast()`

).**One of the main benefits of**`LinkedList<E>`

`add(int index, E element)`

is*O(n)*(with*n/4*steps on average), but*O(1)*when`index = 0`

or`index = list.size() - 1`

(in this case, you can also use`addFirst()`

and`addLast()`

/`add()`

).**One of the main benefits of**`LinkedList<E>`

`remove(int index)`

is*O(n)*(with*n/4*steps on average), but*O(1)*when`index = 0`

or`index = list.size() - 1`

(in this case, you can also use`removeFirst()`

and`removeLast()`

).**One of the main benefits of**`LinkedList<E>`

`Iterator.remove()`

is*O(1)*.**One of the main benefits of**`LinkedList<E>`

`ListIterator.add(E element)`

is*O(1)*.**One of the main benefits of**`LinkedList<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 of**`ArrayList<E>`

`add(E element)`

is*O(1)*amortized, but*O(n)*worst-case since the array must be resized and copied`add(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 constant-time 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 performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a `LinkedList`

arise when you re-use 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`

arise 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.

Read more… Read less…

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 64-bit machines will basically match their 32-bit 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)`

`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 cache-locality.
- 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 big-O 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.

As someone who has been doing operational performance engineering on very large scale SOA web services for about a decade, I would prefer the behavior of LinkedList over ArrayList. While the steady-state throughput of LinkedList is worse and therefore might lead to buying more hardware -- the behavior of ArrayList under pressure could lead to apps in a cluster expanding their arrays in near synchronicity and for large array sizes could lead to lack of responsiveness in the app and an outage, while under pressure, which is catastrophic behavior.

Similarly, you can get better throughput in an app from the default throughput tenured garbage collector, but once you get java apps with 10GB heaps you can wind up locking up the app for 25 seconds during a Full GCs which causes timeouts and failures in SOA apps and blows your SLAs if it occurs too often. Even though the CMS collector takes more resources and does not achieve the same raw throughput, it is a much better choice because it has more predictable and smaller latency.

ArrayList is only a better choice for performance if all you mean by performance is throughput and you can ignore latency. In my experience at my job I cannot ignore worst-case latency.

```
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
```

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

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)