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

Question

Я понимаю определение связанного списка, но как его можно представить и связать с общей концепцией или элементом?

Например, композиция (EDIT: первоначально говорилось «наследование») в ООП может быть связана с автомобилями. Все (большинство) автомобилей в реальной жизни - одно и то же; У автомобиля есть Двигатель, вы можете запустить () его, вы можете запустить автомобиль (), остановить () и так далее. Автомобиль, как правило, имеет максимальную вместимость пассажиров, но он будет отличаться между автобусом и спортивным автомобилем, которые оба являются автомобилями.

Есть ли какой-нибудь реальный, интуитивно понятный пример простого однолинейного связанного списка, который мы имеем в наследовании? Типичный пример Linked List из учебника показывает узел с целым числом и указателем на следующий, и он просто не кажется очень полезным.

Ваш вклад приветствуется.

Answer 1

Если вы подумаете об этом, «Ссылка» - это просто способ определения отношения «Далее», «Предыдущий», «Дочерний» или «Родительский» среди данных экземпляров. Таким образом, среди реальных Мир приложений вы найдете широкий спектр приложений. Представьте себе простой список (например, список покупок) для основных связанных списков. Но рассмотрим также использование, для которого мы можем разместить Графики (построение расстояний между городами на карте, взаимодействия между видами в биологии) или Деревья (иерархии в организации или данные в индексе базы данных для двух очень разнообразных примеров).

Answer 2

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

Примеры из реальной жизни:

• группа людей, ожидающих в очереди то или другое - особый вид LL называется "очередь".

• Стек посуды в вашем фарфоре шкаф - особый вид ЛЛ, называемый «стек».

• Строки "взять число" (где цифры должны начинаться заново в «1» в какой-то момент) - особый вид LL называется "круговая очередь".

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

Мой личный фаворит: Bogosort = играть в пикап с 52 картами, пока ваша колода не отсортирована. : -)

Answer 3

Человеческий мозг может быть хорошим примером по отдельности связного списка. На начальных этапах изучения чего-либо наизусть естественным процессом является соединение одного элемента с другим. Это подсознательный акт. Давайте возьмем пример ограбления до 8 строк Одиночного жнеца Вордсворта :

Behold her, single in the field,
Yon solitary Highland Lass!
Reaping and singing by herself;
Stop here, or gently pass!
Alone she cuts and binds the grain,
And sings a melancholy strain;
O listen! for the Vale profound
Is overflowing with the sound.

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

В то же время, если вы дадите ему указатель, он пойдет вперед. Хорошо, начните с Reaping and singing by herself; ?. Теперь стало легче. Еще проще, если бы вы дали ему две строчки, Alone she cuts and binds the grain, And sings a melancholy strain;, потому что он улучшил поток. Точно так же, , если вы вообще ничего ему не дадите, ему придется начать с самого начала, чтобы получить строки . Это классический связанный список.

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

Answer 4

Моей первой реакцией на этот вопрос было: «Посмотри вокруг! Это везде!» Но немного подумав, я не мог придумать ни одного примера, который не был придуман.

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

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

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

Answer 5

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

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

Answer 6

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

• Есть неизвестное или изменяемое количество предметов
• Предметы в порядке, как список
• Элементы могут быть переставлены, добавлены в средний список, удалены в средний список и т. Д.

Перестановка простого массива - это боль, добавление элемента где-то посередине, при этом убедитесь, что массив имеет достаточно памяти и т.д., это боль. Со связанным списком эти операции просты. Скажем, вы хотите переместить элемент № 10, чтобы он находился между элементом № 2 и № 3. С бумагами вы можете просто взять и переместить. С массивом вам нужно будет переместить элементы с 3 по 9 через слот, а затем вставить его. Со связанным списком вы сделаете следующее: скажите 9, что один за ним 11, скажите 2, один за ним 10, скажите 10 после того, как это 3.

Я использую несколько из них прямо сейчас, из-за того, как легко добавлять элементы, и программно сказать «выполнить это действие для каждого элемента в списке». Одним из них является список записей, как в электронной таблице. Другой, я делаю, просматривая этот первый список и добавляя ссылку на каждый элемент, который имеет определенное значение, чтобы я мог выполнять пакетные операции с ними. Возможность извлекать элементы из середины или добавлять их в середину, и не нужно беспокоиться о длине массива. Это основные преимущества моего опыта.

Answer 7

Телефонная сеть реализована непосредственно в виде связанного списка. Вот как это работает:

1. Организатор группы собирает номера телефонов всех участников.

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

3. Когда необходимо отправить сообщение, организатор вызывает руководителя списка и доставляет сообщение.

4. Руководитель звонит по номеру, который был им назначен, и доставляет сообщение.

5. Шаг 4 повторяется, пока все не услышат сообщение.

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

Answer 8

Посмотрите на связанный список:

[A] => [B] => [C] => [D] =>

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

Answer 9

Предоставление направлений движения. Каждый шаг в направлениях является узлом, а инструкция перемещения между каждым узлом является ссылкой.

Пример:

Узел 1: Начало дома

Ссылка: пройти 3 квартала на юг до дома Боба

Узел 2: дом Боба

Ссылка: Пройдите 2 квартала к северу от дома Алисы.

Узел 3: дом Алисы

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

Answer 10

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

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

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

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