Что является практическим, реальным примером связанного списка?
Я понимаю определение связанного списка, но как его можно представить и связать с общей концепцией или элементом?
Например, композиция (EDIT: первоначально говорилось "наследование") в ООП может быть связана с автомобилями. Все (большинство) автомобилей в реальной жизни - одно и то же; У автомобиля есть Двигатель, вы можете запустить () его, вы можете заставить автомобиль двигаться (), остановиться () и так далее. Автомобиль, как правило, имеет максимальную вместимость пассажиров, но он будет отличаться между автобусом и спортивным автомобилем, которые оба являются автомобилями.
Есть ли какой-нибудь реальный, интуитивно понятный пример простого простого списка, как у нас с наследованием? Типичный пример Linked List из учебника показывает узел с целым числом и указателем на следующий, и он просто не кажется очень полезным.
Ваш вклад приветствуется.
35 ответов
Связанный список похож на линию конга. Каждый держит бедра человека перед собой, и его бедра по очереди удерживаются человеком сзади, исключая только те, которые находятся спереди и сзади. Единственный способ добавить людей в линию - найти правильное место и отделить это соединение, а затем вставить нового человека или людей.
Я предполагаю, что вы хотите более метафорическое объяснение, чем определение книги, вместо примеров того, как вы могли бы использовать связанный список.
Связанный список - это что-то вроде охоты на мусор. У вас есть подсказка, и у этой подсказки есть указатель, чтобы найти следующую подсказку. Итак, вы идете в следующее место и получаете еще один фрагмент данных и другой указатель. Чтобы получить что-то посередине или в конце, единственный способ добраться до него - это следовать этому списку с самого начала (или обманывать;))
Что является практическим, реальным примером связанного списка?
Самым простым и понятным является поезд.
Вагоны связаны в определенном порядке, чтобы их можно было загружать, выгружать, перевозить, высаживать и подбирать наиболее эффективным способом.
Например, завод Jiffy Mix нуждается в сахаре, муке, кукурузной муке и т. Д. В непосредственной близости может быть завод по переработке бумаги, который нуждается в хлоре, серной кислоте и водороде.
Теперь мы можем остановить поезд, разгрузить каждый вагон с его содержимым, затем позволить поезду продолжаться, но тогда все остальное в поезде должно сидеть, пока мука высасывается из кессона, затем сахар и т. Д.
Вместо этого вагоны загружаются в поезд таким образом, чтобы можно было отсоединить весь его кусок, а остальная часть поезда движется дальше.
Конец поезда легче отсоединить, чем часть в середине, и гораздо проще, чем отсоединить несколько вагонов в одном месте и несколько вагонов в другом месте.
Однако при необходимости вы можете вставлять и удалять предметы в любой точке поезда.
Очень похоже на связанный список.
-Адам
Первое, что нужно понять, это то, что связанный список концептуально совпадает с массивом.
Разница лишь в эффективности различных операций. Самое главное:
- Вставка в середине: O(1) для списка, O(n) для массива.
- Прямой доступ к элементу посередине: O(n) для списка, O(1) для массива.
Таким образом, любая аналогия, которую можно использовать для массива (все двигатели самолета, все элементы в списке покупок...), также применима к связанному списку, но из соображений эффективности может быть целесообразно провести другую аналогию:
Массив будет коробками в книжном шкафу. Когда вы убираете ящик из n-го ряда, все ящики с n+1 вверх нужно переместить на одну полку вниз (чтобы у вас не было проблемной пустой полки).
Связанный список, наоборот, был бы ожерельем. Когда вы обнаружите, что вам больше не нравится этот синий драгоценный камень, выньте его из последовательности и свяжите получающиеся два конца вместе. Не нужно проходить через каждую жемчужину и смещать ее только для того, чтобы вы могли починить свое ожерелье.
Очередь ожидания у кассира и т. Д.
Серия заказов, которые должны быть выполнены по порядку.
Любая структура FIFO может быть реализована в виде связанного списка.
Пример из реальной жизни для:
** 1) односвязный список **
- Человеческий мозг ребенка (чтобы вспомнить что-то, например, стихотворение, он должен связать это, если вы спросите его последнюю строку, которую он должен будет прочитать из первой строки)
- доставка сообщений по сети (сообщение разбивается на пакеты, и каждый пакет имеет ключ следующего, чтобы на стороне получателя их было легко объединить)
2) Дважды связанный список
- Молекулы ДНК
- Кеш браузера, который позволяет использовать кнопку НАЗАД.
- Поезда тренеров связаны со следующими и предыдущими.
- Роликовая цепь велосипеда (двойной круговой связанный список)
3) Круговой связанный список
- эскалатор
- Проблема разделения времени, используемая планировщиком во время планирования процессов в операционной системе.
- Многопользовательская настольная игра
Я помню, много лет назад, на одном из моих первых занятий в колледже, мне было интересно, где я буду когда-либо использовать связанный список. Сегодня я не думаю, что есть какой-то один проект, над которым я бы работал, и во многих местах. Это невероятно фундаментальная структура данных, и, поверьте мне, она активно используется в реальном мире.
Например:
- Список изображений, которые необходимо записать на компакт-диск в приложении медицинской визуализации
- Список пользователей веб-сайта, которым нужно отправить уведомление по электронной почте
- Список объектов в 3D-игре, которые необходимо отобразить на экране
Сейчас это может показаться немного бесполезным, но через несколько лет задайте себе тот же вопрос, и вы удивитесь, что когда-нибудь задумывались, где он будет использоваться.
Изменить: я заметил в одном из ваших комментариев вы спросили о том, почему указатель имеет значение. Кто-то правильно ответил, что указатель не имеет значения для пользователя связанного списка. Пользователь просто хочет список, который содержит, ну, список вещей. То, как этот список "содержит" этот список вещей, на самом деле не имеет значения для пользователя. Указатель является частью этого "как". Представьте себе линию, проведенную на полу, которая ведет к кассиру. Люди должны стоять на этой линии, чтобы иметь возможность добраться до кассира. Эта строка является (и я признаю, это немного натянутой) аналогией с указателем, используемым связанным списком. Первый человек, у кассира, на линии, является главой списка. Человек непосредственно за ними на линии - следующий в списке. И, наконец, последний человек в строке, на очереди, является хвостом списка.
Способ, которым Blame перемещается вокруг группы инженеров-программистов, работающих над различными модулями в проекте.
Во-первых, парня из GUI обвиняют в том, что продукт не работает. Он проверяет свой код и видит, что это не его вина: API облажался. Парень из API проверяет свой код: это не его вина, это проблема модуля логгера. Парень из модуля логгера теперь обвиняет парня в базе данных, который обвиняет парня-установщика, который обвиняет...
Цепь:
Особенно роликовая цепь:
Каждый элемент цепочки связан со своим преемником и предшественником.
Если подумать, "Ссылка" - это просто способ идентификации отношений "Далее", "Предыдущий", "Дочерний" или "Родительский" между экземплярами данных . Итак, среди реальных приложений вы найдете широкий спектр приложений. Подумайте о простом списке (например, список покупок) для основных связанных списков. Но рассмотрим также использование, для которого мы можем разместить Графики (построение диаграмм расстояний между городами на карте, взаимодействия между видами в биологии) или Деревья (иерархии в организации или данные в индексе базы данных для двух очень разных примеров).
Связанный список может быть использован для реализации очереди. Каноническим примером из реальной жизни будет линия для кассира.
Связанный список также может быть использован для реализации стека. Коническим реальным примером может служить один из тех диспенсеров для тарелок в ресторане-буфете, где вытаскивают верхнюю тарелку из верхней части стопки.
Некоторые примеры одного связанного списка.
- Кнопка отмены любого приложения, такого как Microsoft Word, Paint и т. Д. Связанный список состояний.
- GPS-навигация: связанный список картографических данных. Путешествие из пункта отправления в пункт назначения является примером прохождения через все узлы. Изменение маршрута с помощью GPS является примером операций добавления и удаления данных карты.
Некоторый пример двойного связанного списка.
- Кнопка "Следующий" и "Предыдущий" в браузере: связанный список URL
- Кнопка "Далее" и "Предыдущая" в Microsoft Image Viewer: связанный список изображений
- Кнопка отмены и возврата в Photoshop, связанный список состояний.
Человеческий мозг может быть хорошим примером односвязного списка. На начальных этапах изучения чего-либо наизусть естественным процессом является соединение одного предмета с другим. Это подсознательный акт. Давайте возьмем пример кражи 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), где вы сможете выбирать строки из любого места.
В общем случае связанные списки - одна из самых дьявольски полезных вещей, с которыми вы можете столкнуться.
Примеры из реального мира:
Группа людей, ожидающих чего-то в очереди - особый вид LL, называемый "очередью".
Стопка посуды в вашем китайском шкафу - особый вид ЛЛ, называемый "стопкой".
Строки "взять число" (где числа должны начинаться заново с "1" в некоторой точке) - особый вид LL, называемый "круговой очередью".
Вообще метафора, которую я люблю использовать почти для всех связанных структур данных, - это колода карт. Почти все, что вы можете сделать со связанными списками, вы можете использовать колоду карт для визуализации. Это особенно удобно, чтобы показать себе, что происходит в некоторых из более эзотерических алгоритмов сортировки.
Мой личный фаворит: Bogosort = играйте в 52 карты, пока ваша колода не отсортирована.:-)
Моей первой реакцией на этот вопрос было: "Посмотри вокруг! Это везде!" Но подумав немного, я не смог придумать ни одного примера, который не был придуман.
Концепция связанного списка - это сложное понятие, двуединство. У вас есть понятие списка, что не проблема. Список покупок, например. Тогда вы попадаете на ссылку часть. Один продуктовый предмет не знает о следующем продуктовом предмете, поэтому модель ломается.
Я думаю, что причина, по которой у вас возникают проблемы с поиском примера из реального мира, заключается в том, что часть ссылки - это программный артефакт, деталь реализации. Есть много способов реализовать списки программно, и один хороший способ - это знать каждый элемент списка о своих соседях. Другой способ - создать объект List, который отслеживает элементы и их порядок. Так работает большинство списков в реальной жизни. В приведенном выше примере объектом List для списка покупок будет бумага (или что-то еще), на которой она написана.
Возможно, более полезно думать о списках в целом и рассматривать связанные списки как просто конкретную реализацию списка.
Лучший и прямой пример двусвязного списка - Train!
Здесь каждый тренер связан со своим предыдущим и следующим тренером (кроме первого и последнего)
В терминах программирования тело тренера рассматривается как узел данных (значений), а соединитель - как эталонный узел.
Телефонная сеть реализована непосредственно в виде связанного списка. Вот как это работает:
Организатор группы собирает номера телефонов всех участников.
Организатор назначает каждому участнику номер другого участника для вызова. (Иногда они назначают свой номер, чтобы знать, что сообщение получено, но это необязательно.)
Когда необходимо отправить сообщение, организатор вызывает заголовок списка и доставляет сообщение.
Руководитель звонит по номеру, который им был назначен, и доставляет сообщение.
Шаг 4 повторяется, пока все не услышат сообщение.
Очевидно, что необходимо настроить список на шаге 2 так, чтобы все были связаны. Кроме того, список, как правило, общедоступен, поэтому, если кто-то получает автоответчик или сигнал "занято", он может набрать следующий номер и продолжить цепочку.
В.NET BCL, класс System.Exception имеет свойство под названием InnerException, который указывает на другое исключение или еще null, Это формирует связанный список.
В System.Type, BaseType свойство указывает на другой тип таким же образом.
Указание направлений движения. Каждый шаг в направлениях является узлом, а инструкция перемещения между каждым узлом является ссылкой.
Пример:
Узел 1: Начните с дома
Ссылка: пройти 3 квартала на юг до дома Боба
Узел 2: дом Боба
Линк: Пройдите 2 квартала на север до дома Алисы.
Узел 3: дом Алисы
Если вы хотите перейти от одного места к другому, вы должны следовать ссылкам (инструкциям) с каждого промежуточного места (узла), вы не можете просто перейти от дома к Алисе.
Внутри make В программе вы часто обнаружите, что списки зависимостей для конкретного файла, который необходимо построить, определяются как связанные списки указателей на другие файлы, которые также должны быть построены и, в свою очередь, имеют зависимости в связанных списках.
Связанный список очень похож на стопку бумаг, на каждой из которых есть один элемент. (В отличие от массивов, которые похожи на pegboards.) Обычно он используется для решения проблемы с этими характеристиками:
- Есть неизвестное или изменяемое количество предметов
- Элементы в порядке, как список
- Элементы могут быть переставлены, добавлены в средний список, удалены в средний список и т. Д.
Перестановка простого массива - это боль, добавление элемента где-то посередине, в то время как уверенность в том, что массив имеет достаточно памяти и т.д., это боль. Со связанным списком эти операции просты. Скажем, вы хотите переместить элемент № 10, чтобы он находился между элементом № 2 и элементом № 3. С бумагами, вы можете просто взять и переместить. С массивом вам нужно будет переместить элементы с 3 по 9 через слот, а затем вставить его. Со связанным списком вы сделаете следующее: скажите 9, что один за ним 11, скажите 2, один за ним 10, скажите 10 один после 3.
Я использую несколько из них прямо сейчас, из-за того, как легко добавлять элементы, и программно сказать "выполнить это действие для каждого элемента в списке". Одним из них является список записей, как в электронной таблице. Другой, я делаю, просматривая этот первый список и добавляя ссылку на каждый элемент, который имеет определенное значение, чтобы я мог выполнять пакетные операции с ними. Возможность извлекать элементы из середины или добавлять их в середину, и не нужно беспокоиться о длине массива. Это основные преимущества моего опыта.
Я не думаю, что есть хорошая аналогия, которая могла бы выделить две важные характеристики, а не массив: 1. эффективно вставлять после текущего элемента и 2. неэффективно находить конкретный элемент по индексу.
Ничего подобного нет, потому что обычно люди не имеют дело с очень большим количеством предметов, в которые нужно вставить или найти определенные предметы. Например, если у вас есть мешок с песком, это будут сотни миллионов зерен, но вам не нужно искать конкретное зерно, и порядок зерен не важен.
Когда вы работаете с небольшими коллекциями, вы можете найти нужный элемент визуально, или, в случае книг в библиотеке, у вас будет организация, подобная диктатуре.
Ближайшая аналогия - слепой человек, который просматривает связанные предметы, такие как звенья цепи, бусы на ожерелье, вагоны поезда и т. Д. Он может искать конкретный предмет или ему нужно вставить предмет после текущего. Было бы хорошо добавить, что слепой может проходить их очень быстро, например, один миллион бус в секунду, но может чувствовать только одну связь за раз и не может видеть всю цепь или ее часть.
Обратите внимание, что эта аналогия похожа на список с двумя связями, я не могу представить аналогию с однозначным списком, потому что наличие физической связи подразумевает возможность возврата.
Он попросил практический пример; так что я попробую
Допустим, вы пишете брандмауэр; в этом брандмауэре у вас есть белый список IP-адресов и черный список IP-адресов.
Вы знаете, что ваш IP, ваш IP-адрес рабочих мест и некоторые IP-адреса тестирования должны быть в белом списке. Итак, вы добавляете все IP-адреса в белый список.
Теперь у вас также есть список известных IP-адресов, которые должны быть заблокированы. Итак, вы добавляете эти IP-адреса в черный список.
Зачем использовать LinkedList для этого?
- Операция быстрая для добавления / удаления элемента из списка.
- Вы не знаете, сколько IP-адресов будет заблокировано / занесено в белый список. Таким образом, раскрывается одно из основных преимуществ LinkedList (его можно изменять).
В операционных системах... можно использовать связанный список, чтобы отслеживать, какие процессы запущены и какие процессы спят... процесс, который работает и хочет спать... удаляется из LinkedList, который отслеживает выполнение процессы и по истечении времени ожидания добавляет его обратно в активный процесс LinkedList
Возможно, в более новых ОС используются какие-то необычные структуры данных... там можно использовать связанные списки
Хорошим примером этого, я думаю, является иерархическое дерево вашей семьи, потому что вы связаны со своими бабушкой и дедушкой, а также со своими прабабушкой и дедушкой. Вот как я понимаю связанный список, хотя в основном это мое собственное мнение.
Посмотрите на связанный список:
[A] => [B] => [C] => [D] =>
Это... Поезд! Каждый вагон содержит что-то и прикреплен к другому вагону (или ничего к последнему). Вы можете добавить железнодорожный вагон только в конце, и если вы хотите избавиться от одного, вы должны прикрепить предыдущий к следующему.
Хорошо, если учитель взял своих учеников в мультипликационный фильм, но она не смогла собрать места вместе, она попросила бы учеников запомнить адрес (номер места) следующего ученика и так далее... чтобы у нее не было столкнуться с проблемой при возвращении!!!
Мне нравится думать о круговом связанном списке, похожем на жемчужное ожерелье, где каждая жемчужина содержит немного данных. Вы просто следуете за строкой до следующей жемчужины данных, и в конечном итоге вы снова окажетесь в начале.
Примером реального мира для LinkedList будет переключатель в 30-х годах. распределительная коробка