Comparing the speed of the ArrayList and LinkedList in practice

Greetings!

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

I recommend to pre-read the extended posts about the work:
ArrayList - habrahabr.ru/post/128269
LinkedList - habrahabr.ru/en/post/127864

Why decided to measure? Because after studying the information there are gaps, where and what is still faster . Especially inspired by the read comment on the article about LinkedList:

So, there is a feeling that LinkedList remains in the JDK only to ask the candidates for an interview about its effectiveness to ask questions.

')
Let's start. How did you measure?
Perhaps someone will have doubts about the correctness of the measurement, but the results were in some situations very similar to the theory.
An example of code with which one of the types of measurements was made:

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 - in all measurements different, because somewhere to get the result you need 3 million operations, and somewhere 10 thousand is enough, because with 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 =================

findings

Summarizing the data, we have the following: In most cases, LinkedList loses to ArrayList, but in the remaining minority it is out of competition.

When to use LinkedList:
1. It is necessary 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
one. . get
2.. set ( beginning and middle )
3. .add
4. remove ( except the beginning of the list )

Comments are required to review:
H. denonlink

Adding / removing LinkedList elements using an iterator is much faster than Arraylist habrahabr.ru/post/233797/#comment_7883135

H. sekrasoft

habrahabr.ru/post/233797/#comment_7882579

Write in the comments comments / suggestions - I will adjust until we find the truth.