Другой программист упомянул, что они не нашли примера использования для использования структуры связанных списков в любом профессиональном программном обеспечении в своей карьере. Я не мог придумать никаких хороших примеров с головы. Он в основном разработчик С# и Java
Может ли кто-нибудь привести примеры, когда это была правильная структура данных для решения конкретной проблемы реального мира?
Связанный: Что такое практический пример реального мира связанного списка?
Реальным примером может служить очередь FIFO. Простой список на основе массивов для этого довольно плохой, потому что вам нужно добавить на одном конце и удалить с другого конца, и одна из этих операций будет O (n) с массивом (если вы не добавите дополнительную логику для работа с индексом начала и конца), в то время как оба являются O (1) со связанным списком без дополнительных усилий.
Связанные списки предлагают несколько преимуществ перед сопоставимыми структурами данных, такими как статические или динамически расширяющиеся массивы.
Любое место, где эти преимущества были бы существенно ценны для программы (и недостатки LinkedList были незначительными), было бы местом использования LinkedList.
Связанные списки (в паре с хеш-таблицей) действительно полезны для Lache Cache.
Каждый элемент Get должен помечать node в начале списка, операцию, которая действительно дешева со связанными списками.
Интрузивные связанные списки - интересные звери для разработки игр. Например, довольно распространенная практика иметь навязчивый одно- или двусвязный список "render":
class Renderable /* or class Object, whatever */
{
// ...
Renderable * m_pNext;
Renderable * m_pPrev; // or not, if singly-linked
// ...
}
Поскольку Renderables вступают и выходят из жизни, они могут зарегистрироваться в этом списке - без какого-либо выделения памяти. Если изменить глубину или приоритет их рендеринга, они могут удалить и снова вставить их и т.д.
Когда придет время для рендеринга, все, что вам нужно сделать, это найти главу списка и пропустить почтовый ящик, вызвав соответствующий метод!
(Конечно, есть много вариаций на эту тему, с несколькими отдельными списками и т.д. И вам не нужно иметь навязчивый список, чтобы сделать эту работу, я просто нахожу интересные навязчивые.)
Стеки и очереди - очень четкие примеры связанных списков, но, как уже упоминалось ранее, я хотел бы добавить несколько других примеров:
DOM хранит узлы как связанные списки. Простой пример javascript, который на самом деле одинаковый на любом языке:
for (var node = parent.firstChild; node != null; node = node.nextSibling) {
// ..
}
Я бы предположил, что разработчик java в какой-то момент столкнулся с XML.
Деревья - еще один хороший пример связанных списков, хотя они не простые одномерные. Кто-то, кто сделал много развития Java, вероятно, встретил TreeMaps и TreeSets.
Вся дискуссия кажется мне немного глупой. Связанные списки - это фундаментальная структура данных, которая используется повсюду. Единственная причина, по которой можно подумать, что он/она не сталкивался с ними, заключается в том, что вам не нужно беспокоиться о внедрении структур данных на сегодняшних языках высокого уровня, но, конечно, они все еще существуют.
Они происходят все время, где-либо объект имеет свойство, указывающее на другой объект того же типа. В CLR исключения образуют связанный список из-за свойства InnerException.
Неизменяемый связанный список - очень ценная структура, поскольку вы можете "совместно использовать структуру" с другими списками с одним и тем же хвостом. Большинство функциональных языков включают неизменный тип связанного списка как одну из их фундаментальных структур данных, и эти типы используются повсеместно.
Как лучший пример реального мира в .Net рассмотрим MultiCastDelegate.
Связанные списки, реализованные таким образом, где аспект привязки списка поддерживается непосредственно в тип, а не как отдельный контейнер, может быть чрезвычайно эффективным и эффективным. Однако у них есть множество компромиссов.
Одним из очевидных является дублирование кода, вы должны испечь эту логику в каждом типе. Такие методы, как расширение базового класса, предоставляющего указатель, беспорядочны (вы теряете сильную типизацию без дженериков) и часто неприемлемы с точки зрения производительности.
Другое дело, что вы ограничены одной реализацией для каждого типа. Вы не можете превратить односвязную структуру в двусвязную, не вставляя лишнее поле в каждом экземпляре и обновляя все соответствующие коды.
Как уже говорилось, уже связанные списки очень полезны, когда вам нужно вставлять и удалять элементы.
Например, чтобы помочь отлаживать управление памятью в моем коде, я недавно реализовал список ссылок между всеми моими подсчитанными объектами, чтобы в конце программы (когда все рефренсы достигли нуля и удалили объекты), я мог видеть точно то, что осталось, по существу, что привело к тому, что я смог найти один объект в корне проблемы.
CPython реализует нечто похожее с массивным связанным списком между почти каждым, когда он построен с отладкой.
Отвечая на тег "Структуры данных", на низком уровне, таком как сборка, связанные списки являются идеальным способом хранения списков переменной длины других структур данных. Для поддержания длины или конца списка нет накладных расходов, и нет необходимости в элементах списка фиксированного размера. Последняя причина также относится к языкам более высокого уровня.
Я написал расширение BIOS (в основном, драйвер устройства для BIOS, написанный на сборке) для хост-контроллера USB. - Внедрение абстрактной структуры данных на высоком уровне, такой как связанный список в сборке, не так сложно, как кажется. - Контроллер обслуживает запросы ввода-вывода для клавиатуры и диска, используя связанный список пакетов в основной памяти. Я поддерживал пул бесплатных пакетов в другом связанном списке. Выполнение ввода-вывода в основном связано с захватом бесплатного пакета с начала бесплатного списка, настройкой пакета, добавлением пакета в список устройств и повторным добавлением пакета в начало свободного пула при завершении ввода-вывода. Связанные списки являются молниеносными для перемещения вокруг таких объектов, особенно когда объекты большие, так как объекты фактически не должны перемещаться. Только их указатели необходимо обновить.
Очередь на основе массива потребовала бы:
Таким образом, связанные списки - прекрасный способ реализовать произвольно длинную очередь в порядке очереди с большими объектами.
Еще одна вещь, о которой нужно помнить, - это то, что для небольших объектов или где вы выделяете объекты из обычной кучи вместо настраиваемого бесплатного пула, массивы могут быть быстрее, потому что копирование на самом деле не так медленно, если это не так часто, и повторное выделение из кучи, которое связанный список требовал бы каждый раз, когда добавлялся новый элемент, медленный.
Конечно, вам может понадобиться смоделировать и измерить ваш конкретный сценарий с помощью некоторого тестового кода для поиска ответа. Мне нравится запускать циклы несколько миллионов раз со связанными списками и массивами с небольшими и большими объектами и временем, которое каждый занимает в реальном времени. Иногда вы будете удивлены.
Как указывает daustin777, все связанные ссылки связаны, и вы можете даже не знать об этом. Но практичность заключается в том, что они позволяют выполнять довольно простые операции с относительной легкостью и гибкостью. Например, чтобы не сортировать, просто поменяйте указатели. Нужно вставлять или удалять в произвольных местах? Вставьте или удалите указатели в списке. Необходимо перебирать вперед и назад... связанный список. Хотя это не совсем бизнес-пример, я надеюсь, что это прояснит его достаточно, чтобы вы применили его к своему собственному бизнесу в реальном мире.
Связанный список - это важная структура данных для Dancing Links, которая используется для эффективного использования Алгоритм X, который является алгоритмом обратного отслеживания, чтобы найти все решения для NP-полного точное покрытие проблема, к которой многие трудные проблемы естественно сводятся к.
Если я могу ответить на этот вопрос несколько иначе, чем другие, в последнее время я использую связанные списки для организации музыкальных списков. Списки обеспечивают отличный способ хранения и сортировки музыки по исполнителям, песне, альбому, даже рейтингам или длине песни. Mine - это список с двойной связью, но я видел, что он применим и к одному связанному списку. Списки покупок тоже подойдут, и если вы OCD, как моя мама, вы можете легко организовать его пробой и замороженные продукты в последний раз!
Если мы включаем стеки и очереди, очевидным для очередей является очередь печати или музыкальный плейлист (списки в любом смысле хороши, очевидно).
Пример одного связанного списка.
Некоторый пример двойного связанного списка.
Стеки и очереди представляют собой примеры связанных списков.
Для проблем, где число максимальных узлов ограничено до 100 или ниже или около того, связанные списки являются разумным решением. То же самое можно сказать о вещах, таких как сортировка пузырьков и другие вещи, которые считаются субоптимальными.
Связанные списки профи:
Связанный список минусов:
Из моей головы я бы выполнил стеки, очереди и сообщения с помощью связанных списков. Я бы также использовал datatree, используя связанные ссылки с несколькими ссылками для быстрой вставки/удаления.