Каковы реальные примеры использования связанных списков?

Question

Другой программист упомянул, что они не нашли варианта использования для использования структуры данных связанного списка ни в одном профессиональном программном обеспечении в его карьере. Я не мог придумать ни одного хорошего примера с моей головы. Он в основном разработчик C # и Java

Кто-нибудь может привести несколько примеров, когда это была правильная структура данных для решения конкретной проблемы реального мира?

Связанный: Что является практическим, реальным примером связанного списка?

Answer 1

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

1. Доза LinkedLists не требует смежных блоков памяти и, следовательно, может помочь уменьшить фрагментацию памяти
2. LinkedLists поддерживают эффективное удаление элементов (динамические массивы обычно вызывают сдвиг во всех элементах).
3. LinkedLists поддерживают эффективное добавление элементов (динамические массивы могут вызывать перераспределение + копирование, если конкретное добавление превышает текущую емкость)

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

Answer 2

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

Answer 3

Связанные списки ( в сочетании с хеш-таблицей ) действительно полезны для LRU-кэшей .

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

Answer 4

Навязчивые связанные списки - интересные звери для разработки игр. Например, довольно распространенной практикой является наличие навязчивого одно- или двусвязного списка «рендеринга»:

class Renderable /* or class Object, whatever */
{
  // ...
  Renderable * m_pNext;
  Renderable * m_pPrev; // or not, if singly-linked
  // ...
}

Когда Renderables появляются и исчезают, они могут зарегистрироваться в этом списке - без выделения памяти. Если их глубина рендеринга или приоритет изменены, они могут удалить и заново установить себя и т. Д.

Когда приходит время рендеринга, все, что вам нужно сделать, это найти заголовок списка и пролистать, вызывая соответствующий метод!

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

Answer 5

Они происходят постоянно, везде, где у объекта есть свойство, которое указывает на другой объект того же типа. В CLR исключения образуют связанный список из-за свойства InnerException.

Answer 6

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

DOM хранит узлы в виде связанных списков. Простой пример JavaScript, который действительно одинаков на любом языке:

for (var node = parent.firstChild; node != null; node = node.nextSibling) {
    // ..
}

Я бы предположил, что разработчик Java сталкивался с XML в какой-то момент.

Деревья являются еще одним хорошим примером связанных списков, хотя они не являются простыми одномерными. Кто-то, кто много занимался Java-разработкой, наверняка сталкивался с TreeMaps и TreeSets.

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

Answer 7

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

Answer 8

В качестве, пожалуй, лучшего реального примера в .Net рассмотрим MultiCastDelegate .

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

Answer 9

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

Для очереди на основе массива потребуется:

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

Таким образом, связанные списки являются хорошим способом реализации произвольно длинной очереди «первым пришел - первым вышел».

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

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

Answer 10

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