Comparison of the speed of ArrayList and LinkedList in practice

Greetings!

ArrayList and LinkedList - everyone knows. In which situations it works quickly, and in which situation this or that list is slow, everyone who knows in theory and who in practice also knows. This post is suitable for those who are just starting to learn Java, or who have heard about “which is faster,” but have not seen in practice.

I recommend preliminarily reading extended posts about work:
ArrayList - habrahabr.ru/post/128269
LinkedList - habrahabr.ru/post/127864

Why did I decide to measure? Because after studying the information, there were gaps, where and what is still faster . A particularly helpful comment on a LinkedList article is:
So there is a feeling that LinkedList remains in the JDK only to ask candidates for interviews about its effectiveness to ask questions.


Let's get started. How did you measure it?
Perhaps someone will have doubts about the correctness of the measurement, but the results were in some situations very similar to the theory.
Example code with which one of the types of measurements was done:

Date startLinked = new Date();
        for(int i = 0; i < k; i++) {
            //операция .add .insert. remove. get .set с начала середины, и конца списка
            //k - кол-во операций
        }
        Date finishLinked = new Date();
        long linkedTime = finishLinked.getTime() - startLinked.getTime();


k - different in all measurements, because somewhere to get the result you need 3 million operations, but somewhere 10 thousand is enough, because at 3 million you need to wait more than one minute.

Output
=============== Add =====================
--- Add elements (6kk)
LinkedList: 2264 ms
ArrayList: 493 ms
ArrayList is faster

============== Insert =================
--- Insert elements to begin (100k)
LinkedList: 132 ms
ArrayList: 2742 ms
LinkedList is faster

--- Insert elements to middle (60k)
LinkedList: 4110 ms
ArrayList: 494 ms
ArrayList is faster

============== Remove ======= ==========
--- Remove elements from begin (100k)
LinkedList: 2 ms
ArrayList: 3220 ms
LinkedList is faster

--- Remove elements from middle (100k)
LinkedList: 7519 ms
ArrayList: 1544 ms
ArrayList is faster

--- Remove elements from end (1kk)
LinkedList: 37 ms
ArrayList: 8 ms
ArrayList is faster

============= Get =========== =========
--- Get elements from begin (4kk)
LinkedList: 25 ms
ArrayList: 7 ms
ArrayList is faster

--- Get elements from middle (40k)
LinkedList: 2320 ms
ArrayList: 0 ms
ArrayList is faster

--- Get elements from end (3kk)
LinkedList: 23 ms
ArrayList: 5 ms
ArrayList is faster

============== Set ============= =======
--- Set elements at begin (1kk)
LinkedList: 342 ms
ArrayList: 12 ms
ArrayList is faster

--- Set elements at middle (50k)
LinkedList: 3734 ms
ArrayList: 1 ms
ArrayList is faster

--- Set elements at end (3kk)
LinkedList: 40 ms
ArrayList: 267 ms
LinkedList faster

========= ===== Finish ==================








Conclusions

Summarizing the data obtained, we have the following: LinkedList in the vast majority of cases loses ArrayList, but in the remaining minority it is out of competition.

When to use LinkedList:
1. You need to add a lot of data to the top of the list
2. Delete from the beginning (index = 0) of the list, i.e. Items that were added first.
3. .set at the end of the list

When to use ArrayList
1.. get
2.. set ( beginning and middle )
3. .add
4. remove (except the beginning of the list )

Comments are obligatory for familiarization:
Uv. denonlink
Adding / removing LinkedList elements using an iterator is much faster than Arraylist habrahabr.ru/post/233797/#comment_7883135


SW sekrasoft
habrahabr.ru/post/233797/#comment_7882579

Write comments / suggestions in the commentary - I will correct it until we find the truth.

Also popular now: