Сравнение скорости работы ArrayList и LinkedList на практике

Приветствую Вас!

ArrayList и LinkedList — знают все. В каких ситуациях работает быстро, а в какой ситуации работает медленной тот или другой список — знают тоже все, кто в теории, а кто на практике. Данный пост подходит для тех, кто только начинает изучать Java, или кто слышал, о том «что быстрее», но не видел на практике.

Рекомендую предварительно прочитать расширенные посты про работу:
ArrayList — habrahabr.ru/post/128269
LinkedList — habrahabr.ru/post/127864

Почему решил измерять? Потому, что после изучения информации остались пробелы, где и что всё-таки быстрее. Особенно сподвиг прочтенный комментарий к статье про LinkedList:

Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.

Начнем. Как замерял?
Возможно, у кого-то возникнут сомнения по-поводу корректности замера, но результаты оказались в некоторых ситуациях очень схожи с теорией.
Пример кода, с помощью которого делал один из типов замеров:

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 — во всех замерах разное, т.к. где-то для получения результата нужно 3 миллиона операций, а где-то 10 тысяч достаточно, т.к. при 3 миллионах необходимо ждать не одну минуту.

Выходные данные

==============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=================

Выводы

Подытоживая полученные данные, имеем следующее: LinkedList в подавляющем большинстве случаев проигрывает ArrayList, но в оставшемся меньшинстве он вне конкуренции.

Когда использовать LinkedList:
1. Необходимо много данных добавлять в начало списка
2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.
3. .set в конце списка

Когда использовать ArrayList
1. .get
2. .set (начало и середина)
3. .add
4. remove ( кроме начала списка )

Комментарии обязательные к ознакомлению:
Ув. denonlink

Добавление/удаление элементов LinkedList с помощью итератора гораздо быстрее, чем Arraylist habrahabr.ru/post/233797/#comment_7883135

Ув. sekrasoft

habrahabr.ru/post/233797/#comment_7882579

Пишите в комментарии замечания/предложения — буду корректировать, пока не найдём истину.