Comments 15
Вывод: беготня по указателям и "промахи кэша" могут убить производительность. Этому влиянию подвержены любые структуры данных, основанные на ссылках: связные списки, префиксные деревья, бинарные деревья, красно-черные деревья, списки с пропусками, и в меньшей степени — хеш-карты.
Структура данных и абстрактный тип данных - это таки разные вещи. Например, бинарное дерево можно сделать на основе связного списка, а можно на основе массива.
Бинарные деревья на основе массива - это немного другие структуры данных (с другой сложностью операций даже). Самое близкое - это б-деревья - но это тоже другая структура данных.
Ну и бинарные деревья на основе массива не то чтобы быстрее бинарных деревьев на основе ссылок: на верхних уровнях ветвления всё равно будет случайное блуждание и кешмиссы; только на нижних 5-6 уровнях станет полегче.
В линкед хэш сетах он используется отлично
Я помогу сократить статью: используйте arrayList.
Всё супер, но очереди же. Если у вас много маленьких очередей, или очереди, которые могут менять глубину в сотни раз. Или очереди, Кирове всегда растут, достают до приличного размера и потом уничтожаются. А это очень частые задачи (для которых связный список т был подписан). То в этих случаях нужно использовать LinkedList.
Промахи кэшей у них... А ничего, что ArrayList в случае растущего списка десяток раз реалоцируется? Вот там такой performance hit получается, что промахи кэша и рядом не валялись. Куда катится IT... В 2025 году оказалось, что связаные списки имебт недостатки по сравнению с массивами. Шок контент! Таки темпами к 2030 году выяснится, что массивы тоже имеют недостатки по сравнению со связными списками! И они должны использоваться для разных задач. Это же вообще будет уму не постижимо будет!
Или очереди, ... То в этих случаях нужно использовать LinkedList.
Сейчас не времена Java 1.0 и для очередей давно уже есть java.util.Queue / java.util.Deque.
А ничего, что ArrayList в случае растущего списка десяток раз реалоцируется? Вот там такой performance hit получается, что промахи кэша и рядом не валялись.
Возьмите JMH, сравните ArrayList с LinkedList, расскажите нам. Без замеров ваши слова это просто слова.
Так Queue и Deque - это интерфейсы. LinkedList - одна из имплементации этих интерфейсов.
Сейчас не времена Java 1.0 и для очередей давно уже есть
java.util.Queue/java.util.Deque
Это только интерфейсы. А в качестве реализации Вы предлагаете использовать что?
Вы разобрали очевидные минусы и плюсы.
Из ключевых, огромный минус LinkedList это объем памяти. А еще один - это то, что каждый элемент является экземпляром и при вставке элементов мы вынуждены создавать инстансы объектов, что довольно медленно. Попрбуйте сделать тест на копирование данных из массива в 1 млн элементов в обе коллекции (в конец) и вы увидите разницу. Только arrayList нужно создать сразу с нужным капасити.
Кстати отличной заменой LinjedList для очередей служит класс ArrayDequeu который лишен недостатков LinkedList и работает в среднем в 1.5 раза быстрее
Рекомендации Oracle по выбору между ArrayList и LinkedList