Представьте себе группу людей, стоящих в очереди спереди назад, один за другим. Каждый человек может видеть и сказать, кто находится перед ним, но не может сказать, кто позади него.
Теперь представьте, что вам нужна информация от каждого ученика — его возраст и предпочтения в еде. Но человек будет слушать вас только тогда, когда вы называете его имя. К счастью, вы знаете имя человека в самом конце очереди.
Что вы будете делать? Поскольку мы знаем, что каждый человек знает, кто перед ним, Вот план, который я могу придумать:
- Позвоните человеку сзади и узнайте его детали
- Спросите этого человека, как его зовут.
- Позвоните новому человеку, узнайте его данные и продолжайте это, пока не охватите всех.
Эта очередь студентов, которую мы только что представили, представляет собой связанный список! И наш способ получить информацию от каждого ученика — это то, как мы просматриваем связанный список. Связанный список — это, по сути, аналогичная структура данных, которую можно создать на компьютере с помощью любого языка программирования для хранения данных и управления ими. Человек в очереди называется «узлом», в котором хранятся данные, а соединение между двумя людьми — «связью». Поскольку каждый человек указывает на следующего, связь также называется указателем.
Итак, узел — это не что иное, как набор данных (возраст и предпочтения в еде в нашей аналогии), а ссылка или указатель — не что иное, как адрес следующего узла (имя человека в нашей аналогии). А связанный список — это не что иное, как набор этих узлов.
Обсуждаемый нами тип связанных списков — это односвязные списки, поскольку узлы содержат только адрес следующего узла, а не предыдущего. Связанный список, в котором узлы имеют как прямую, так и обратную ссылку, является двусвязным списком.
Реальный пример связанных списков, используемых на компьютерах, — веб-браузеры. У вас есть кнопка «Назад» для каждой страницы, которую вы посещаете. Таким образом, каждая страница представляет собой узел, который содержит некоторые данные (информацию о странице) и ссылку на предыдущую страницу. Поскольку каждая страница также содержит ссылку на следующую страницу (которую вы видите, когда возвращаетесь назад), это двусвязный список.
