В большинстве статей пишут, что LinkedList подходит для частой вставки или удаления элементов. На JavaRush также упоминают обход списка с периодической вставкой.
В теории всё так, но обычно в энтерпрайзе менее изысканные задачи:
🔸 Заполнить список
🔸 Отсортировать (встроенной функцией, конечно)
🔸 Обойти все элементы
🔸 Сделать что-нибудь с помощью Stream API
Для этих сценариев я сделала бенчмарки. У Stream API выделила 4 случая:
▫️ Простой однопоточный: stream→filter→collect
▫️ Сложный однопоточный: stream→map→filter→map→filter→collect
▫️ Простой с опцией parallel()
▫️ Сложный с опцией parallel()
Начнём с заполнения списка.
В прошлом посте выяснили, что до 100к элементов между списками почти нет разницы. ArrayList тратит много времени на копирование, а LinkedList — на создание обёрток и соединение ссылок.
Если количество элементов известно заранее, его можно указать в конструкторе:
List list = new ArrayList(25);Без лишнего копирования и переносов разница в скорости становится ошеломительной — список заполняется на 20-80% быстрее!
Также ArrayList однозначно победил в номинациях:
🔹 Сортировка
🔹 Обход через цикл for
🔹 Простые Stream API
🔹 Любые Stream API с опцией parallel()
В сложных однопоточных Stream API большая часть вычислений идёт на что-то полезное, и влияние оверхеда снижается. Ожидаемо:)
Ещё факты против LinkedList:
🔸 Большинство классов JDK используют ArrayList для внутренних задач
🔸 Joshua Bloch (автор класса и книжки Effective Java) в 2015 написал твит:
"Does anyone actually use LinkedList? I wrote it, and I never use it."Но аналоги LinkedList иногда встречаются. В Scala для неизменяемого списка за основу взят именно двусвязный. Возможно, это лучше для каких-то сценариев, но пока не знаю для каких.
На картинке часть моих бенчмарков. N — количество элементов в списке. Зелёный цвет обозначает победителя в категории. Ярко-зелёный — разница значений более 50%.
❗️Результаты на разных железках могут отличаться ❗️
