Classic interview question:
"What is the complexity of ArrayList vs LinkedList?"
Usually answered with something along the lines of:
"Removing items from LinkedList is O(1) while ..."
And that's probably it, however, this doesn't reflect the actual performance of them, and it may lead to a substantial slow down in your code.
But before we get to that, let's discuss some important implementation details for ArrayList and LinkedList in Java. Keep those in mind when looking at the benchmark results.
The Implementation Details
ArrayList
- It uses primitive array underneath to store values,
- Primitive array is stored as a continuous chunk of memory.
LinkedList
- Each element holds value and reference to next and previous element,
- It holds references to both first and last element of the list,
- It optimizes get by index: if the index is less than half the size, start from the beginning, else start from the end,
- Elements are scattered around the memory.
The Benchmark
You can see the code for the benchmark in this repo. I used objects instead of usual integer just to have something looking a bit more like a real world example, and I used JMH for benchmark.
Test cases are what you would expect in a normal project:
- findByReference
- getByKnownIndex
- iterateOver
- removeByKnownIndex
- removeByReference
- addFirst
- addInTheMiddle
- addLast
- removeFirst
- removeInTheMiddle
- removeLast
The benchmark creates 2 Lists with 1 million objects each, LinkedList and ArrayList, we also store reference to one of the objects in each List, from around the middle.
My laptop is IdeaPad Gaming 3 15IMH05 with Intel i7-10750H (12) @ 5.000GHz and 32GB of RAM. I run Azul Zulu 17.0.6 Java.
So, what are the results? On my laptop they came to:
Benchmark Score Error Units
arrayList_findByReference 2696499.728 ± 32202.502 ns/op
linkedList_findByReference 7028258.295 ± 411854.774 ns/op
arrayList_getByKnownIndex 1.355 ± 0.020 ns/op
linkedList_getByKnownIndex 14109357.750 ± 4523485.134 ns/op
arrayList_iterateOver 4241855.707 ± 51949.429 ns/op
linkedList_iterateOver 18701734.963 ± 153427.714 ns/op
arrayList_removeByKnownIndex 23807.499 ± 22832.530 ns/op
linkedList_removeByKnownIndex 13611894.721 ± 415849.451 ns/op
arrayList_removeByReference 5446367.115 ± 116991.612 ns/op
linkedList_removeByReference 13715672.076 ± 1153278.238 ns/op
arrayList_addFirst 3220312.800 ± 428670.631 ns/op
linkedList_addFirst 8515.000 ± 24870.360 ns/op
arrayList_addInTheMiddle 815357.800 ± 282617.391 ns/op
linkedList_addInTheMiddle 142979327.200 ± 18151974.063 ns/op
arrayList_addLast 4606.600 ± 23419.256 ns/op
linkedList_addLast 1620.400 ± 680.293 ns/op
arrayList_removeFirst 1933858.000 ± 127364.646 ns/op
linkedList_removeFirst 5216.600 ± 713.334 ns/op
arrayList_removeInTheMiddle 824331.600 ± 53493.129 ns/op
linkedList_removeInTheMiddle 143313481.400 ± 34759711.042 ns/op
arrayList_removeLast 3943.600 ± 834.749 ns/op
linkedList_removeLast 5973.800 ± 972.878 ns/op
As we can see, in only 2 of them the ArrayList was clearly slower than LinkedList, and it was only cases at the start of the List. It was similar at the end, and in all others it was at least few times faster.
You might say: "wait, but that's not what the Big O Notation says, LinkedList should be faster in deletions and inserts", and you would be right, that's exactly what it says.
So, where does the performance hit come from?
The Reason
The Big O
The O(1) for deletion doesn't count finding the element you need to delete. Yes, the operation itself is just moving around few references, but you need to find the object first. Some articles, like this one, actually take this into consideration, however, some don't.
Overall, you need to be aware that removing references is just part of the algorithm for deletion, if you include searching, then you will come to correct O(n) value for elements in the middle of the List.
As for the last element: the performance for ArrayList and LinkedList is pretty much the same, because Java implementation of LinkedList holds references to both beginning and end by default. If, for some reason, you would use LinkedList without the back reference, you would need to iterate over the entire list to get to the last element.
However, that's still not everything.
The CPU and Caches
You've probably heard that CPU has Caches - L1, L2, L3 and sometimes even L4, then there is RAM and finally disk. It looks (in great simplification) like this:
When you want to access some data in your program, like iterate over an array of elements, it is loaded into the CPU Cache for quick access. The arrows on the diagram show order in which the caches are checked for the data, if it's found in L1, great, if not go check L2 and so on, until finally it checks the disk.
What helps with loading data into caches is Cache Prefetching, but that in itself is not important for us.
The important bit of information is this: the prefetching is optimized for continuous memory access, so that it can load entire array at once, if it fits into to the cache.
Focus on the word: continuous.
Array is stored as continuous block of memory, and CPU is optimized for continuous memory access.
Here is another important piece of knowledge: accessing RAM can be 10 to 100 times slower than accessing cache.
That's the whole trick.
Since LinkedList can be randomly scattered around memory, there is no way to load it into the cache at once. You need to first get an element and check the reference of next one before you can get it. Each element has to be accessed separately, 10 to 100 times slower than the elements in ArrayList.
That is the reason for performance difference.
Is LinkedList useless then?
No. There are cases where LinkedList would be better. From the top of my head: double-ended linked list can be used as a queue with unknown number of elements, in fact a Deque is exactly that. Thanks to having references to both beginning and end, you add elements at the end, and remove at the front with the performance promised by Big O notation.
Summary
The biggest lesson here, at least for me, is to remember that the programs we write are executed by the CPU, and we should not forget that. Understanding what happens in the CPU, even generally, can be very valuable. I might not know how the prefetching works, but it's enough to know how it affects my program.
The other take from this is that ArrayList should be used pretty much everywhere by default, unless you have specific requirements that would benefit from LinkedList.
Hope you found this article useful :)
Top comments (0)