Я понимаю определение связанного списка, но как его можно представить и связать с общей концепцией или элементом?
Например, композиция (EDIT: первоначально названная "наследование" ) в ООП может быть связана с автомобилями. Все (большинство) автомобилей в реальной жизни - это, по сути, одно и то же; у автомобиля есть Двигатель, вы можете его запустить(), вы можете сделать автомобиль go(), stop() и так далее. Автомобиль обычно имел максимальную пассажирскую мощность, но он отличался бы между автобусом и SportsCar, которые оба являются автомобилями.
Есть ли какая-то реальная жизнь, интуитивный пример простого оле 'единственного Связанного списка, как у нас с наследованием? Пример типичного учебника Linked List показывает node с целым числом и указателем на следующий, и это просто не очень полезно.
Ваш ввод приветствуется.
Связанный список похож на конга line. Каждый держит бедра человека перед собой, а их бедра удерживаются в свою очередь человеком сзади, за исключением только спереди и сзади. Единственный способ добавить людей в линию - найти нужное место и отделить это соединение, а затем вставить нового человека или людей.
Я предполагаю, что вы хотите больше метафорического объяснения, чем определение книги, а не примеры того, как вы можете использовать связанный список.
Связанный список похож на охоту за мусорщиками. У вас есть ключ, и этот ключ имеет указатель на место, чтобы найти следующую подсказку. Итак, вы переходите к следующему месту и получаете еще один кусочек данных и другой указатель. Чтобы получить что-то посередине или в конце, единственный способ добраться до него - следовать этому списку с самого начала (или обмануть;))
Что такое практический пример реального мира связанного списка?
Простейшим и самым простым является поезд.
Железнодорожные вагоны соединены в определенном порядке, чтобы их можно было загружать, выгружать, переносить, выгружать и брать наиболее эффективным способом.
Например, завод Jiffy Mix нуждается в сахаре, муке, кукурузной муке и т.д. Рядом с изгибом может быть завод по переработке бумаги, который нуждается в хлоре, серной кислоте и водороде.
Теперь мы можем остановить поезд, разгрузить каждый автомобиль его содержимого, а затем продолжить поезд, но тогда все остальное в поезде должно сидеть, пока мука высасывается из кессона, затем сахара и т.д.
Вместо этого автомобили загружаются в поезд таким образом, чтобы можно было отсоединить весь кусок, а остальная часть поезда движется дальше.
Конец поезда легче отсоединяется, чем часть посередине, и намного проще, чем отсоединять несколько автомобилей в одном месте и несколько автомобилей в другом месте.
При необходимости, однако, вы можете вставлять и удалять элементы в любой точке поезда.
Как связанный список.
-Adam
Линия ожидания у кассира/кассира и т.д.
Ряд заказов, которые должны выполняться в порядке.
Любая структура FIFO может быть реализована как связанный список.
Прежде всего нужно понять, что связанный список концептуально совпадает с массивом.
Единственное различие заключается в эффективности различных операций. Самое главное:
Таким образом, любая аналогия, которая может быть использована для массива (все двигатели плоскости, все элементы в списке покупок...) также относится к связанному списку, но соображение эффективности может привести к аналогия:
Массив будет в книжном шкафу. Когда вы удаляете ящик из n-й строки, все ячейки из n + 1 вверх нужно перемещать на одну полку вниз (так что у вас нет хлопотной пустой полки).
Связанный список, наоборот, будет ожерельем. Когда вы обнаружите, что вам больше не нравится этот синий жемчуг, выньте его из последовательности и соедините полученные два конца вместе. Не нужно проходить через каждую жемчужину и вытеснять ее, чтобы вы могли исправить свое ожерелье.
Я помню, много лет назад, в одном из моих первых классов колледжа, задаваясь вопросом, где я когда-либо, когда-либо использовал связанный список. Сегодня я не думаю, что есть один проект, над которым я работаю, где я его не использовал, и во многих местах. Это невероятно фундаментальная структура данных, и, поверьте, она сильно использовалась в реальном мире.
Например:
Теперь это может показаться вам немного бесполезным, но через несколько лет задайте себе тот же вопрос, вы удивитесь, что вы когда-нибудь задумывались, где он будет использоваться.
Edit: Я заметил, что в одном из ваших комментариев вы спросили, почему этот указатель имеет значение. Кто-то справедливо ответил, что указатель на самом деле не имеет значения для пользователя связанного списка. Пользователь просто хочет список, содержащий список нужных вещей. Как этот список "содержит" этот список вещей не имеет особого значения для пользователя. Указатель является частью этого "как". Представьте себе линию, нарисованную на полу, которая ведет к кассиру. Люди должны стоять на этой линии, чтобы добраться до кассира. Эта строка является (и я признаю, это немного растянутая) аналогия для указателя, который использует связанный список. Первый человек, у кассира, на линии, является главой списка. Лицо, прямо за ним на линии, является следующим в списке. И, наконец, последний человек в строке, на линии, является хвостом списка.
Цепочка:
Особенно цепь роликов:
Каждый элемент цепочки связан с его преемником и предшественником.
Ваши молекулы ДНК являются списками с двойной связью.
Если вы думаете об этом, "ссылка" - это просто способ идентификации отношений "Next", "Previous", "Child" или "Parent" между экземплярами данных. Таким образом, среди приложений реального мира вы найдете множество приложений. Подумайте о простом списке (например, списке продуктов) для базовых списков ссылок. Но рассмотрите также те виды использования, в которых мы можем размещать графики (построение расстояний между городами на карте, взаимодействие между видами в биологии) или деревья (иерархии в организации или данные в индексе базы данных для двух очень разных примеров).
То, как Blame перемещается вокруг группы разработчиков программного обеспечения, работающих с различными модулями в проекте.
Во-первых, парень GUI обвиняется в том, что продукт не работает. Он проверяет свой код и видит его не в своей вине: API запутывается. Парень API проверяет свой код: не его ошибка, это проблема с модулем регистратора. Парень модуля Logger теперь обвиняет парня базы данных, который обвиняет парня установщика, который обвиняет...
В общем случае связанные списки - одна из самых дьявольски полезных вещей, с которыми вы столкнетесь.
Примеры реального мира:
Куча людей, ожидающих очереди что-то особенное - особый вид из LL называется "очередь".
Стопка блюд в вашем фарфоре кабинет - особый вид LL, называемый "стек".
Строки "взять число" (где цифры должны начинаться заново "1" в какой-то момент) - особый вид LL называется "круговой очередью".
Как правило, метафора, которую я использую для почти всех связанных структур данных, является колодой карт. Почти все, что вы можете сделать со связанными списками, вы можете использовать колоду карт для визуализации. Это особенно удобно, чтобы показать, что происходит в некоторых более эзотерических алгоритмах сортировки.
Мой личный фаворит: Bogosort= играть в 52 карты, пока ваша колода не будет отсортирована.: -)
Пример реальной жизни для:
** 1) Единосвязный список **
2) Двунаправленный список
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), где вы сможете выбирать строки из любого места.
Моя первая реакция на этот вопрос: "Оглянитесь! Это везде!" Но, немного подумав об этом, я не мог придумать ни одного примера, который не надуман.
Концепция связанного списка представляет собой сложную концепцию, двухфазную. У вас есть представление о списке, что не представляет проблемы. Например, список продуктов. Затем вы попадаете в ссылку. Один пункт бакалеи не знает о следующем продукте, поэтому модель ломается.
Я думаю, что причина, по которой у вас возникают проблемы с поиском реального мира, заключается в том, что часть ссылки представляет собой артефакт программирования, деталь реализации. Существует много способов реализации списков программным образом, и один хороший способ состоит в том, чтобы каждый элемент списка знал о своих соседях. Другой способ - иметь объект List, который отслеживает элементы и их порядок. Так работает большинство списков в реальной жизни. В приведенном выше примере объектом List для списка продуктов будет документ (или любой другой), который он написал.
Может быть, более полезно подумать о списках вообще и просмотреть связанные списки как просто конкретную реализацию списка.
Связанный список может использоваться для реализации queue. Канонический пример реальной жизни - это линия для кассира.
Связанный список также можно использовать для реализации stack. Кононический реальный пример ife был бы одним из тех диспенсеров для тарелок в ресторане "шведский стол", где вытащите верхнюю пластину с верхней части стека.
Предоставление направлений движения: каждый шаг в направлениях node и инструкция перемещения между каждым node в качестве вашей ссылки.
Пример:
Node 1: Начало дома
Ссылка: Прогулка 3 квартала Юг к дому Боба
Node 2: Дом Боба
Ссылка: Пройдите 2 квартала к северу до дома Алисы.
Node 3: Дом Алисы
Если вы хотите получить одно место другому, вы должны следовать ссылкам (инструкциям) из каждого промежуточного места (node), вы не можете просто пропустить из дома в Алису.
Посмотрите на связанный список:
[A] = > [B] = > [C] = > [D] = >
Это... Поезд! Каждый вагон содержит что-то и прикрепляется к другому вагону (или ничего для последнего). Вы можете добавить только вагон в конце, и если вы хотите избавиться от него, вы должны прикрепить предыдущий к следующему.
Телефонная цепочка реализуется непосредственно как связанный список. Вот как это работает:
Организатор групп собирает номера телефонов всех участников.
Организатор назначает каждому члену номер другого участника для вызова. (Иногда они назначают свой номер, чтобы они знали, что сообщение прошло, но это необязательно.)
Когда сообщение нужно отправить, организатор вызывает головку списка и доставляет сообщение.
Голова вызывает номер, который они были назначены, и доставляет сообщение.
Шаг 4 повторяется, пока все не услышали сообщение.
Очевидно, необходимо сделать все, чтобы настроить список на шаге 2, чтобы все были связаны. Кроме того, список обычно является общедоступным, так что если кто-то получает автоответчик или занятый тон, они могут вызывать следующее число вниз и удерживать цепочку.
Связанный список очень похож на стек документов, каждый из которых содержит один элемент. (В отличие от массивов, которые похожи на плетеные.) Обычно это используется для решения проблемы с этими характеристиками:
Реорганизация простого массива - это боль, добавляя элемент где-то посередине, при этом убедитесь, что у массива достаточно памяти и т.д. боль. Со связанным списком эти операции просты. Предположим, что вы хотите переместить элемент № 10 между пунктом № 2 и пунктом №3. С бумагами вы можете просто поднять его и переместить. С массивом вам нужно будет перемещать элементы с 3 по 9 по слоту, а затем вставьте его. Со связанным списком вы выполните следующее: Скажите 9, что после 11 символов скажите 2 после 10, скажите 10, что после 3-х.
Я использую несколько из них прямо сейчас, из-за того, насколько легко добавлять элементы и программно сказать "сделайте это действие для каждого элемента в списке". Одним из них является список записей, например, в электронной таблице. Другой, я делаю, просматривая этот первый список и добавляя ссылку на каждый элемент, который имеет определенное значение, чтобы я мог выполнять пакетные операции над ними. Возможность выхватывать предметы из середины или добавлять их в середину и не беспокоиться о длине массива. Это основные преимущества моего опыта.
Хорошо, если учитель забрал своих учеников в мультфильм, но она не могла собраться вместе, она попросит учеников вспомнить адрес (номер места) следующего ученика и так далее... так, чтобы она 't придется столкнуться с проблемой, возвращаясь!!!
Он попросил практический пример; поэтому я сделаю снимок:
Предположим, вы пишете брандмауэр; в этом брандмауэре есть белый список IP и черный список IP.
Вы знаете, что ваш IP-адрес, IP-адрес вашей работы и некоторые тестовые IP-адреса должны быть включены в белый список. Таким образом, вы добавляете весь IP-адрес в белый список.
Теперь у вас также есть список известных IP-адресов, которые необходимо заблокировать. Таким образом, вы добавляете эти IP-адреса в черный список.
Зачем использовать LinkedList для этого?
Лучший и прямой пример двусвязного списка - Поезд!
Здесь каждый тренер связан с его предыдущим и следующим тренером (кроме первого и последнего)
В терминах программирования рассмотрите тело тренера как данные (значение) node и соединитель как ссылку node.
Мне нравится думать о круговом связанном списке, таком как жемчужное ожерелье, причем каждая жемчужина содержит немного данных. Вы просто следуете строке на следующую жемчужину данных, и в итоге вы снова начинаете в начале.
В .NET BCL класс System.Exception имеет свойство, называемое InnerException, которое указывает на другое исключение, а также null. Это создает связанный список.
В System.Type свойство BaseType указывает на другой тип таким же образом.
Внутри программы make вы часто обнаружите, что списки зависимостей для определенного файла, которые должны быть созданы, определяются как связанные списки указателей на другие файлы, которые также необходимо построить и, в свою очередь, иметь зависимости в связанных списки.
Посмотрите на Связанный список как структуру данных. Этот механизм представляет собой самоагрегацию в OOD. И вы можете думать об этом как о объекте реального мира (для некоторых это реальность)
В операционных системах... можно использовать связанный список, чтобы отслеживать, какие процессы запущены и какие процессы спят... процесс, который работает и хочет спать... удаляется из LinkedList, который сохраняет отслеживать запущенные процессы и как только время сна закончится, добавляет его обратно в активный процесс LinkedList
Возможно, более новая ОС использует некоторые фанковые структуры данных... там могут быть использованы связанные списки.
Хорошим примером связанного списка является ваше текстовое сообщение, в котором определенный пакет может быть разделен на несколько пакетов. Каждый пакет содержит ключ, который подключается к следующему ключу и n-му ключу, чтобы сделать все текстовое сообщение, в котором он содержит ключ и данные.
рассмотрите 2 или более ящика, которые имеют 2 или более отсеков. (в этом примере каждая коробка будет иметь 2 отсека) первое отделение будет содержать некоторую информацию. число или слово. во втором отсеке будет стрелка, указывающая на следующее поле и т.д.
обратите внимание, что каждый ящик может содержать многопрофильные ячейки, содержащие стрелки (указатели) и информацию (данные).
Я не думаю, что есть хорошая аналогия, которая могла бы выделить две важные характеристики в отличие от массива: 1. эффективно вставлять после текущего элемента и 2. неэффективно находить определенный элемент по индексу.
Нет ничего подобного, потому что обычно люди не занимаются очень большим количеством предметов, где вам нужно вставлять или находить определенные предметы. Например, если у вас есть мешок с песком, это будет сотни миллионов зерен, но вам не нужно искать конкретное зерно, а порядок зерен не важен.
Когда вы имеете дело с небольшими коллекциями, вы можете найти нужный элемент визуально или, в случае книг в библиотеке, у вас будет такая диктофонная организация.
Ближайшая аналогия имеет слепого человека, который проходит через связанные предметы, такие как звенья цепи, бусы на ожерелье, вагоны поездов и т.д. Он может искать конкретный предмет или ему нужно вставить элемент после текущего. Возможно, было бы неплохо добавить, что слепой может пройти через них очень быстро, например. один миллион шариков в секунду, но может ощущать только одну ссылку за раз и не может видеть всю цепочку или ее часть.
Обратите внимание, что эта аналогия похожа на двойной список, я не могу придумать аналогичную аналогию с односвязной, потому что наличие физического соединения подразумевает способность отступать.