При каких обстоятельствах полезны связанные списки?

Question

В большинстве случаев я вижу, как люди пытаются использовать связанные списки, мне кажется, что это плохой (или очень плохой) выбор. Возможно, было бы полезно изучить обстоятельства, при которых связанный список является или не является хорошим выбором структуры данных.

В идеале ответы должны быть изложены на критериях, которые следует использовать при выборе структуры данных, и какие структуры данных могут работать лучше при определенных обстоятельствах.

Редактировать: Должен сказать, я впечатлен не только количеством, но и качеством ответов. Я могу принять только один, но есть еще два или три, которые, я бы сказал, стоило бы принять, если бы чего-то лучшего не было. Только пара (особенно та, которую я принимал) указали на ситуации, когда связанный список давал реальное преимущество. Я думаю, что Стив Джессоп заслуживает какого-то почетного упоминания за то, что он придумал не один, а три разных ответа, и я нашел их весьма впечатляющими. Конечно, несмотря на то, что он был опубликован только как комментарий, а не как ответ, я думаю, что запись в блоге Нила также стоит прочитать - не только информативную, но и довольно интересную.

Answer 1

Связанные списки очень полезны, когда вам нужно сделать много вставок и удалений, но не слишком много искать в списке произвольной (неизвестной во время компиляции) длины.

Разделение и объединение (двунаправленно) списков очень эффективно.

Вы также можете комбинировать связанные списки - например, древовидные структуры могут быть реализованы в виде «вертикальных» связанных списков (родительские / дочерние отношения), соединяющих вместе горизонтальные связанные списки (родные элементы).

Использование списка на основе массива для этих целей имеет серьезные ограничения:

• Добавление нового элемента означает, что массив должен быть перераспределен (или вы должны выделить больше места, чем необходимо для будущего роста и уменьшить количество перераспределений)
• Удаление элементов оставляет пустое пространство или требует перераспределения
• вставка элементов в любое место, кроме конца, включает (возможно, перераспределение и) копирование большого количества данных на одну позицию

Answer 2

Они могут быть полезны для параллельных структур данных. (Ниже приведен пример одновременного использования в реальном мире, которого не было бы, если бы @ Neil не упомянул FORTRAN. ;-)

Например, ConcurrentDictionary<TKey, TValue> в .NET 4.0 RC использует связанные списки для объединения элементов, которые хэшируются в один и тот же сегмент.

Базовая структура данных для ConcurrentStack<T> также является связанным списком.

ConcurrentStack<T> является одной из структур данных, которые служат основой для нового пула потоков (с локальными «очередями», реализованными, по сути, в виде стеков). (Другая основная опорная конструкция ConcurrentQueue<T>.)

Новый пул потоков, в свою очередь, обеспечивает основу для планирования работы нового Task Parallel Library .

Так что они, безусловно, могут быть полезны - связанный список в настоящее время служит одной из основных структур поддержки, по крайней мере, одной замечательной новой технологии.

(Одиночно-связанный список делает убедительный без блокировки - но не без ожидания - выбор в этих случаях, потому что основные операции могут быть выполнены с помощью одного CAS (+ повторные попытки). В современной среде GC-d, такой как Java и .NET, проблемы ABA можно легко избежать. Просто оберните элементы, которые вы добавляете в только что созданные узлы, и не используйте эти узлы повторно - пусть GC сделает свою работу. На странице, посвященной проблеме ABA, также представлена ​​реализация стека без блокировки, который фактически работает в .Net (& Java) с узлом (GC-ed), содержащим элементы.)

Редактировать : @Neil: на самом деле то, что вы упомянули о Фортране, напомнило мне, что аналогичные виды связанных списков можно найти, вероятно, в наиболее используемой и злоупотребляемой структуре данных в .NET: простой .NET универсальный Dictionary<TKey, TValue>.

Не один, а много связанных списков хранятся в массиве.

• Это позволяет избежать множества небольших (де) выделений при вставке / удалении.
• Первоначальная загрузка хеш-таблицы происходит довольно быстро, поскольку массив заполняется последовательно (очень хорошо работает с кешем ЦП).
• Не говоря уже о том, что цепочка хеш-таблиц является дорогой с точки зрения памяти - и этот "трюк" сокращает "размеры указателя" пополам на x64.

По сути, многие связанные списки хранятся в массиве. (по одному на каждое использованное ведро.) Свободный список многократно используемых узлов «переплетается» между ними (если они были удалены). Массив выделяется при запуске / перефразировке, и в нем сохраняются узлы цепочек. Также имеется указатель free - индекс в массиве - который следует за удалением. ;-) Так что - хотите верьте, хотите нет - техника FORTRAN все еще живет. (... и нигде больше, чем в одной из наиболее часто используемых структур данных .NET; -).

Answer 3

Связанные списки очень гибкие: с изменением одного указателя вы можете внести существенное изменение, когда та же операция будет очень неэффективной в списке массивов.

Answer 4

Массивы - это структуры данных, с которыми обычно сравниваются связанные списки.

Обычно связанные списки полезны, когда вам нужно внести много изменений в сам список, в то время как массивы работают лучше, чем списки при прямом доступе к элементу.

Вот список операций, которые можно выполнять над списками и массивами, по сравнению с относительной стоимостью операции (n = длина списка / массива):

• Добавление элемента:
  • в списках вам просто нужно выделить память для нового элемента и перенаправления указателей. O (1)
  • для массивов вы должны переместить массив. О (п)
• Удаление элемента
  • в списках вы просто перенаправляете указатели. O (1).
  • для массивов вы тратите O (n) времени на перемещение массива, если удаляемый элемент не является первым или последним элементом массива; в противном случае вы можете просто переместить указатель на начало массива или уменьшить длину массива
• Получение элемента в известной позиции:
  • в списках вы должны пройти список от первого элемента до элемента в определенной позиции. Худший случай: O (n)
  • в массивах вы можете сразу получить доступ к элементу. O (1) * 1 028 *

Это очень низкоуровневое сравнение этих двух популярных и базовых структур данных, и вы можете видеть, что списки работают лучше в ситуациях, когда вам приходится вносить множество изменений в сам список (удаление или добавление элементов). С другой стороны, массивы работают лучше, чем списки, когда вам нужен прямой доступ к элементам массива.

С точки зрения распределения памяти списки лучше, потому что нет необходимости располагать все элементы рядом друг с другом. С другой стороны, есть (небольшие) издержки хранения указателей на следующий (или даже на предыдущий) элемент.

Знание этих различий важно для разработчиков, чтобы выбирать между списками и массивами в своих реализациях.

Обратите внимание, что это сравнение списков и массивов. Здесь описаны хорошие решения проблем (например, SkipLists, Dynamic Arrays и т. Д.). В этом ответе я учел базовую структуру данных, о которой должен знать каждый программист.

Answer 5

Двусвязный список - хороший выбор для определения порядка хеш-карты, который также определяет порядок элементов (LinkedHashMap в Java), особенно если упорядочен по последнему доступу:

1. Больше памяти, чем у связанного вектора или deque (2 указателя вместо 1), но лучше производительность вставки / удаления.
2. Никаких накладных расходов на выделение ресурсов, так как в любом случае вам нужен узел для записи хеша.
3. Локальная привязка не является дополнительной проблемой по сравнению с вектором или декой указателей, так как каждый объект должен быть вытянут в память в любом случае.

Конечно, вы можете спорить о том, является ли кеш LRU хорошей идеей по сравнению с чем-то более сложным и настраиваемым, но если вы собираетесь его использовать, это довольно приличная реализация. Вы не хотите выполнять удаление из середины и добавление конца к вектору или deque при каждом доступе к чтению, но перемещение узла в хвост обычно нормально.

Answer 6

Односвязный список - хороший выбор для свободного списка в распределителе ячеек или пуле объектов:

1. Вам нужен только стек, поэтому достаточно односвязного списка.
2. Все уже разделено на узлы. Нет никаких накладных расходов на выделение узла списка, если ячейки достаточно велики, чтобы содержать указатель.
3. Вектор или deque будут накладывать накладные расходы на один указатель на блок. Это важно, учитывая, что когда вы впервые создаете кучу, все ячейки свободны, так что это предоплата. В худшем случае это удваивает требования к памяти на ячейку.

Answer 7

Связанные списки являются одним из естественных вариантов, когда вы не можете контролировать, где хранятся ваши данные, но вам все равно нужно каким-то образом переходить от одного объекта к другому.

Например, при реализации отслеживания памяти в C ++ (замена нового / удаления) вам либо нужна некоторая структура управляющих данных, которая отслеживает, какие указатели были освобождены, что вам необходимо полностью реализовать самостоятельно. Альтернативой является перераспределение и добавление связанного списка в начало каждого блока данных.

Поскольку вы всегда сразу знаете, где находитесь в списке при вызове удаления, вы можете легко отказаться от памяти в O (1). Также добавление нового фрагмента, который был только что размещен, находится в O (1). Ходить по списку в этом случае очень редко, поэтому стоимость O (n) здесь не проблема (в любом случае обход структуры - это O (n)).

Answer 8

Односвязные списки являются очевидной реализацией общего типа данных «список» в функциональных языках программирования:

1. Добавление в голову происходит быстро, и (append (list x) (L)) и (append (list y) (L)) могут делиться практически всеми своими данными. Нет необходимости копировать на записи на языке без записи. Функциональные программисты знают, как этим воспользоваться.
2. Добавление к хвосту, к сожалению, медленное, но то же самое можно сказать и о любой другой реализации.

Для сравнения, вектор или deque, как правило, медленно добавляются с обоих концов, что требует (по крайней мере, в моем примере двух различных добавлений), чтобы была сделана копия всего списка (вектора) или блока индекса и блок данных, добавляемый в (deque). На самом деле, может быть что-то нужно сказать о deque в больших списках, которые по какой-то причине нужно добавить в хвост, я недостаточно информирован о функциональном программировании, чтобы судить.

Answer 9

Они полезны, когда вам нужны высокоскоростные push, pop и rotate, и не обращайте внимания на O (n) индексацию.

Answer 10

Один пример хорошего использования связанного списка - это когда элементы списка очень велики, т.е. достаточно большой, чтобы в кэш-память процессора могли поместиться только один или два. На этом этапе преимущество, которое имеют смежные блочные контейнеры, такие как векторы или массивы для итерации, более или менее аннулировано, и преимущество в производительности может быть возможным, если в реальном времени происходит много вставок и удалений.