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

Question

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

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

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

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

Answer 1

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

Answer 2

Я предполагаю, что вы хотите более метафорическое объяснение, чем определение книги, вместо примеров того, как вы могли бы использовать связанный список.

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

Answer 3

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

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

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

Например, завод Jiffy Mix нуждается в сахаре, муке, кукурузной муке и т. Д. Сразу за поворотом может быть завод по переработке бумаги, который требует хлора, серной кислоты и водорода.

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

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

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

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

Очень похоже на связанный список.

-Adam

Answer 4

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

Единственная разница заключается в эффективности различных операций. Самое главное:

• Вставка в середине: O (1) для списка, O (n) для массива.
• Прямой доступ к элементу посередине: O (n) для списка, O (1) для массива.

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

Массив будет коробок в книжном шкафу . Когда вы убираете ящик из n-го ряда, все ящики с n + 1 вверх нужно переместить на одну полку вниз (чтобы у вас не было проблемной пустой полки).

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

Answer 5

Очередь ожидания у кассира и т. Д. ...

Серия заказов, которые должны быть выполнены по заказу.

Любая структура FIFO может быть реализована как связанный список.

Answer 6

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

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

Answer 7

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

Например:

• Список изображений, которые необходимо записать на компакт-диск в приложении для медицинской визуализации
• Список пользователей веб-сайта, которым необходимо отправить уведомление по электронной почте
• Список объектов в 3D-игре, которые необходимо отобразить на экране

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

Edit: Я заметил в одном из ваших комментариев, что вы спросили о том, почему указатель имеет значение. Кто-то правильно ответил, что указатель не имеет значения для пользователя связанного списка. Пользователь просто хочет список, который содержит, ну, список вещей. Как этот список «содержит» этот список вещей, на самом деле не имеет значения для пользователя. Указатель является частью этого «как». Представьте себе линию, проведенную на полу, которая ведет к кассиру. Люди должны стоять на этой линии, чтобы иметь возможность добраться до кассира. Эта строка является (и я признаю, это немного натянутой) аналогией с указателем, который использует связанный список. Первый человек, у кассира, на линии, является главой списка. Человек непосредственно за ними на линии - следующий в списке. И, наконец, последний человек в строке, в строке, является хвостом списка.

Answer 8

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

** 1) Односвязный список **

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

2) Двусвязный список

1. Молекулы ДНК
2. Кэш браузера, который позволяет использовать кнопку НАЗАД.
3. Тренерские поезда связаны со следующими и предыдущими.
4. Роликовая цепь велосипеда (двукратный связанный список)

3) Круговой связанный список

1. Эскалатор
2. Проблема разделения времени, используемая планировщиком при планировании процессов в операционной системе.
3. Настольная игра для нескольких игроков

Answer 9

Цепочка:

Особенно роликовая цепь:

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

Answer 10

Ваши молекулы ДНК представляют собой двойные списки.