[Из песочницы] Сравнение скорости работы 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 msArrayList: 493 msArrayList is faster
==============Insert=================---Insert elements to begin (100k)LinkedList: 132 msArrayList: 2742 msLinkedList is faster
---Insert elements to middle (60k)LinkedList: 4110 msArrayList: 494 msArrayList is faster
---Insert elements to end (1kk)LinkedList: 35 msArrayList: 119 msLinkedList is faster
==============Remove=================---Remove elements from begin (100k)LinkedList: 2 msArrayList: 3220 msArrayList is faster
---Remove elements from middle (100k)LinkedList: 7519 msArrayList: 1544 msArrayList is faster
---Remove elements from end (1kk)LinkedList: 37 msArrayList: 8 msArrayList is ~faster
==============Get====================---Get elements from begin (4kk)LinkedList: 25 msArrayList: 7 msLinkedList is faster
---Get elements from middle (40k)LinkedList: 2320 msArrayList: 0 msArrayList is faster
---Get elements from end (3kk)LinkedList: 23 msArrayList: 5 msArrayList is faster
==============Set====================---Set elements at begin (1kk)LinkedList: 342 msArrayList: 12 msArrayList is faster
---Set elements at middle (50k)LinkedList: 3734 msArrayList: 1 msArrayList is faster
---Set elements at end (3kk)LinkedList: 40 msArrayList: 267 msArrayList is faster
==============Finish=================
Выводы
Подытоживая полученные данные, имеем следующее: LinkedList в подавляющем большинстве случаев проигрывает ArrayList, но в оставшемся меньшинстве он вне конкуренции.
Когда использовать LinkedList:1. Необходимо много данных добавлять в начало и конец списка2. Удалять с начала (index = 0) списка, т.е. элементы, которые были добавлены первыми.
Когда использовать ArrayList1. .get2. .set3. .add4. remove (кроме начала списка)
Интересные факт (!).add (linkedList.size ()-1, value) — выполняется быстрее в LinkedList.add (value) — выполняется быстрее в ArrayListХотя суть операции та же — добавление в конец спискаВозможно это связанно с отсутствием проверка на длину ArrayList при add (index, value), но до конца не уверен.
Пишите в комментарии замечания/предложения — буду корректировать, пока не найдём истину.
