Comments 18
Вывод: беготня по указателям и "промахи кэша" могут убить производительность. Этому влиянию подвержены любые структуры данных, основанные на ссылках: связные списки, префиксные деревья, бинарные деревья, красно-черные деревья, списки с пропусками, и в меньшей степени — хеш-карты.
Структура данных и абстрактный тип данных - это таки разные вещи. Например, бинарное дерево можно сделать на основе связного списка, а можно на основе массива.
Бинарные деревья на основе массива - это немного другие структуры данных (с другой сложностью операций даже). Самое близкое - это б-деревья - но это тоже другая структура данных.
Ну и бинарные деревья на основе массива не то чтобы быстрее бинарных деревьев на основе ссылок: на верхних уровнях ветвления всё равно будет случайное блуждание и кешмиссы; только на нижних 5-6 уровнях станет полегче.
Структуры данных - это то как данные хранятся в памяти. И их всего две - массив и связный список. И на основе этих структур можно реализовывать абстрактные типы данных - списки, очереди, стеки, деревья, etc.
Структуры данных - это то как данные хранятся в памяти. И их всего две - массив и связный список.
Странное определение. "Как данные хранятся в памяти" - это что значит?
Например, можно взять модель машины указателей - там любая структура данных описывается при помощи набора записей; в каждой записи есть набор свойств (их количество ограничено глобально для структуры данных) - каждое из них хранит либо примитив, либо указатель, либо ничего не хранит. Но в такой модели есть гораздо больше структур данных, чем две (даже если забыть про инварианты).
Но вообще говоря, структура данных определяется набором операций (с их реализациями).
При том, на практике, все "интересные" структуры данных - интрузивны. То есть у нас нет отдельных деревьев, или списков - у нас каждый узел одновременно принадлежит нескольким деревьям, спискам, и пр. Поэтому утверждение что есть только "связанные списки и массивы" - странное.
И на основе этих структур можно реализовывать абстрактные типы данных - списки, очереди, стеки, деревья, etc.
Расскажите, как Вы реализуете, например, дерево поверх связного списка? Разумеется, чтобы операции были эффективными.
В линкед хэш сетах он используется отлично
Я помогу сократить статью: используйте 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
Это только интерфейсы. А в качестве реализации Вы предлагаете использовать что?
Список стандартных реализаций можно посмотреть прямо в JavaDoc. ArrayDeque и вперёд. Смысла использовать связный список тогда, когда нужна очередь не вижу.
В результате реализаций ровно две - массив и список. А поверх них можно что угодно крутить. У каждой из этих двух реализаций есть свои достоинства и недостатки. И ещё недавно это было азами программирования. А теперь 10050 патернов, зато вместо базы открытие за открытием.
Смысла использовать связный список тогда, когда нужна очередь не вижу.
На самом деле если запотеть то можно найти, типа у нас рилтайм и нужна гарантированная латенси, но при этом мы не хотим всю память заранее выделять. Можно сделать гибрид - LL из страничек, но фундаментально это всё таки будет LL)
А ничего, что ArrayList в случае растущего списка десяток раз реалоцируется? Вот там такой performance hit получается, что промахи кэша и рядом не валялись.
Попробуйте посчитать асимптотику этого расширения (тогда не придется даже бенч писать)
Вы разобрали очевидные минусы и плюсы.
Из ключевых, огромный минус LinkedList это объем памяти. А еще один - это то, что каждый элемент является экземпляром и при вставке элементов мы вынуждены создавать инстансы объектов, что довольно медленно. Попрбуйте сделать тест на копирование данных из массива в 1 млн элементов в обе коллекции (в конец) и вы увидите разницу. Только arrayList нужно создать сразу с нужным капасити.
Кстати отличной заменой LinjedList для очередей служит класс ArrayDequeu который лишен недостатков LinkedList и работает в среднем в 1.5 раза быстрее
Рекомендации Oracle по выбору между ArrayList и LinkedList