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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По моему опыту, реализация разреженных матриц и кучи Фибоначчи. Связанные списки дают вам больше контроля над общей структурой таких структур данных. Хотя я не уверен, что разреженные матрицы лучше всего реализовать с использованием связанных списков - вероятно, есть способ получше, но он действительно помог изучить тонкости разреженных матриц с использованием связанных списков в начальной стадии CS :)

Есть две дополнительные операции, которые тривиально составляют O (1) в списках и очень сложно реализовать в O (1) в других структурах данных - удаление и вставка элемента из произвольной позиции, предполагая, что вам нужно поддерживать порядок элементов.

Очевидно, что хеш-карты могут выполнять вставку и удаление в O (1), но тогда вы не можете перебирать элементы по порядку.

Учитывая приведенный выше факт, хеш-карту можно объединить со связанным списком для создания изящного LRU-кеша: карты, которая хранит фиксированное количество пар ключ-значение и отбрасывает последний доступный ключ, чтобы освободить место для новых.

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

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

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

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

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

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

В результате давайте возьмем случай, когда мы хотим сделать аналогичный эквивалент сохранения последовательности переменной длины, которая содержит миллион вложенных подпоследовательностей переменной длины. Конкретным примером является индексированная сетка, в которой хранится миллион многоугольников (несколько треугольников, несколько четырехугольников, несколько пятиугольников, несколько шестиугольников и т. Д.), А иногда многоугольники удаляются из любого места сетки, а иногда многоугольники перестраиваются, чтобы вставить вершину в существующий многоугольник или удалить один. В этом случае, если мы сохраним миллион крошечных файлов std::vectors, мы столкнемся с выделением кучи для каждого вектора, а также с потенциально взрывоопасным использованием памяти. Миллион крошечныхSmallVectors может не страдать от этой проблемы в обычных случаях, но тогда их предварительно выделенный буфер, который не выделяется отдельно в куче, может по-прежнему вызывать взрывное использование памяти.

Проблема в том, что миллион std::vector экземпляров будет пытаться сохранить миллион вещей переменной длины. Вещи переменной длины, как правило, нуждаются в распределении в куче, поскольку они не могут очень эффективно храниться непрерывно и удаляться в постоянное время (по крайней мере, простым способом без очень сложного распределителя), если они не хранили свое содержимое где-либо еще в куче.

Если вместо этого мы сделаем это:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

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

Вот еще один пример:

... где ячейки сетки используются для ускорения столкновения частиц с частицами, скажем, для 16 миллионов частиц, перемещающихся в каждом кадре. В этом примере сетки частиц, используя связанные списки, мы можем перемещать частицу из одной ячейки сетки в другую, просто изменяя 3 индекса. Стирание из одного вектора и возврат к другому может быть значительно дороже и потребовать большего выделения кучи. Связанные списки также уменьшают объем памяти ячейки до 32 бит. Вектор, в зависимости от реализации, может предварительно выделить свой динамический массив в точку, где он может занять 32 байта для пустого вектора. Если у нас есть около миллиона ячеек сетки, это большая разница.

... и именно здесь я считаю связанные списки наиболее полезными в наши дни, и я особенно нахожу полезным вариант "индексированных связанных списков", поскольку 32-разрядные индексы вдвое сокращают требования к памяти для ссылок на 64-разрядных машинах, и они подразумевают, что узлы хранятся в массиве непрерывно.

Часто я также комбинирую их с индексированными списками свободных мест, чтобы обеспечить возможность удаления и вставки в любое время в любом месте:

В этом случае nextиндекс указывает либо на следующий свободный индекс, если узел был удален, либо на следующий используемый индекс, если узел не был удален.

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

В прошлом я использовал связанные списки (даже двусвязные списки) в приложении C / C ++. Это было до .NET и даже до stl.

Я, вероятно, не стал бы сейчас использовать связанный список на языке .NET, потому что весь код обхода, который вам нужен, предоставляется вам с помощью методов расширения Linq.