​Списки, часть 2: что и когда использовать

В большинстве статей пишут, что 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%.

❗️Результаты на разных железках могут отличаться ❗️