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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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