Приветствую Вас!
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---Insert elements to end( 1kk )
LinkedList: 35 ms
ArrayList: 119 ms
LinkedList is faster==============Remove=================
---Remove elements from begin ( 100k )
LinkedList: 2 ms
ArrayList: 3220 ms
ArrayList 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
LinkedList 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
ArrayList is faster==============Finish=================
Выводы
Подытоживая полученные данные, имеем следующее: LinkedList в подавляющем большинстве случаев проигрывает ArrayList, но в оставшемся меньшинстве он вне конкуренции.
Когда использовать LinkedList:
1. Необходимо много данных добавлять в начало и конец списка
2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.
Когда использовать ArrayList
1. .get
2. .set
3. .add
4. remove ( кроме начала списка )
Интересные факт(!)
.add(linkedList.size()-1, value) — выполняется быстрее в LinkedList
.add(value) — выполняется быстрее в ArrayList
Хотя суть операции та же — добавление в конец списка
Возможно это связанно с отсутствием проверка на длину ArrayList при add(index, value), но до конца не уверен.
Пишите в комментарии замечания/предложения — буду корректировать, пока не найдём истину.
Автор: ArtemDP
