Some thoughts on using LinkedList in Java

This is going to be a different article as my assumption after testing some on my machine turned out to be slightly wrong. Here's what I found.

TL;DR
Use ArrayList in most standard cases where you simply add to the list and later on iterate over it. It will save you both time and memory.

Note that this article does not discuss the complexities of some of their operations where we know one or the other would perform substantially better (e.g. adding elements in the beginning of the list or random access). The use case discussed here is simply appending items in order to iterate over it at some later point.

My hypothesis was that LinkedList would perform better compared to ArrayList when simply adding elements to the end of the list in all cases. And I would then recommend that we should turn away from by default typing

List<Object> list = new ArrayList<>();

and instead, write

List<Object> list = new LinkedList<>();

Why?

Because ArrayList has to perform resizing operations once the inner container fills up while the LinkedList simply has to append a new node (the same operation regardless the size).

The test

So I set up a little test of adding 10M elements to each type of list, see below.

This is a dummy example but similar setups are not unlikely to be seen in production. My results were that they performed very similarly.

The test was run with the following VM options to remove any issues with adaptive heap sizing or GC.

-Xms5G -Xmx5G -XX:+UnlockExperimentalVMOptions -XX:+AlwaysPreTouch -XX:+UseEpsilonGC

First test result with epsilon GC.

Now obviously this is pretty far from reality so I decided to modify the test with just specifying the G1 garbage collector.

-XX:+UseG1GC

See below for the new test.

The difference here is that I’ve averaged the times which introduces some extra warmup so the compiler has a bit more time to optimize and we achieve a more realistic result.

More realistic results.

What happened?

It’s difficult to say if the difference between ArrayList and LinkedList in the final example is due to compiler optimizations being more effective for the ArrayList, effects of GC or as a result of the LinkedList requiring more memory. To figure that out one would have to dig into the compiler & GC logs.

But for now, we can conclude that due to either of those effects ArrayList seems to perform substantially better than LinkedList using a more realistic setup with an actual GC running.

Finally some memory considerations

I performed the following test and noted the memory differences.

Memory test for 100 elements.

Following table illustrates the results in a retained heap when doing the aforementioned test with 100 and 1000 Integer elements (which takes 16B since int takes 4 bytes and header info takes 12 [1]) each as reported by MAT [2].

+--------------+----------------+-----------------+----------------+
|     Type     |  100 elements  |  1000 elements  |  Overhead (*)  |
+--------------+----------------+-----------------+----------------+
|  LinkedList  |     4032B      |      40032B     |      24B       |
|  ArrayList   |     2040B      |      20040B     |       4B       |
+--------------+----------------+-----------------+----------------+

Overhead here is simply the retained heap per item minus 16B as provided by MAT less some header info of the actual list. As expected the LinkedList takes up roughly double memory compared to the ArrayList. However, this is given a small element, with bigger elements the overhead will be negligible.

Takeaways

My takeaway from this is to prefer ArrayList over LinkedList in most standard cases where the use case is to simply add to the end and iterate over the list.

References

[1] How to calculate the memory usage of Java objects
https://www.javamex.com/tutorials/memory/object_memory_usage.shtml

[2] Memory Analyzer (MAT)
https://www.eclipse.org/mat/