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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

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

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

Ответ 11

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

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

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

Ответ 12

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

Ответ 13

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

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

Ответ 14

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

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

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

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