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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

Пример одного связанного списка.

1. Кнопка отмены любого приложения, такого как Microsoft Word, Paint и т. Д. Связанный список состояний.
2. GPS-навигация: связанный список данных карты. Путешествие из пункта отправления в пункт назначения является примером прохождения через все узлы. перенаправление GPS - пример операций добавления и удаления данных карты.

Пример двойного связанного списка.

1. Кнопка «Следующий и предыдущий» в браузере: связанный список URL-адресов.
2. Кнопка «Вперед» и «Просмотр» в Image Viewer: связанный список изображений
3. Кнопка отмены и возврата в Photoshop, связанный список состояний.

Answer 4

Если я могу ответить на этот вопрос немного иначе, чем другие, в последнее время я использовал связанные списки для организации музыкальных списков. Списки предоставляют отличный способ хранения и сортировки музыки по исполнителю, песне, альбому, даже рейтингу или длине песни. Мой список является двусвязным, но я мог видеть, что он применим и к односвязному списку. Списки покупок тоже подойдут, и если вы, как моя мама, ОКР, вы можете легко организовать их как проход, так и замороженные продукты в последнюю очередь!

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

Answer 5

Связанный список - это необходимая структура данных для Dancing Links , которая используется для эффективной реализации Алгоритма X , который представляет собой алгоритм обратного отслеживания для поиска всех решений NP- завершить точное покрытие задача, к которой естественным образом сводятся многие сложные проблемы.

Answer 6

Стеки и очереди являются примерами связанных списков.

Answer 7

Плюсы в связанном списке:

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

Минусы связного списка:

• Медленный обход

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

Answer 8

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