Если вы из тех людей, которые даже немного не пугаются, когда слышат слово “Структура данных” , то вы либо сумасшедший, либо инженер.
Так было, когда я впервые окунул палец в огромный мир “Структуры данных и алгоритмы” . О, как моя голова крутилась вокруг себя, пытаясь понять все жаргоны, рассказанные моим учителем в классе; Сложность времени, Деревья, Карты, Графики и так далее. В начале курса все казалось спокойным, управляемым, даже когда мы слышали слова, к которым привыкли, такие как “Стопка” и “Очередь”. Нам даже казалось, что мы начинаем разбираться в коде, пока в один прекрасный день наш учитель не обронил в классе термин, которого мы никогда раньше не слышали, “Связанный список”. Мы подумали про себя: “Звучит достаточно просто, список, который каким-то образом связан”. О, как мы ошибались.
Видите ли, мы никогда раньше не работали с такими вещами, как узлы, структуры данных, к которым мы привыкли, были очень простыми, непрерывный ряд данных, которые состояли из более мелких фрагментов данных, инкапсулирующих единственное значение, которое можно было перемещать, увеличивая или уменьшая соответствующее значение индекса. Звучит достаточно просто? Просто представьте себе определенный набор шариков, вы кладете палец на первый, затем последовательно проводите пальцем мимо каждого из них и добавляете шарик в конец. Сделано!
Но со Связанными списками,
у вас есть значительное преимущество перед другими структурами данных, теперь вы можете динамически распределять данные в любую часть вашего списка. Это возможно благодаря структуре узлов Связанного списка, которая инкапсулирует 2 части данных на узел, а не 1. Один, в котором хранятся фактические данные, а другой, в котором хранится адрес следующего узла. Вы больше не играете с шариками, а тренируетесь.
Если вы хоть чем-то похожи на меня, вы бы сделали то же, что и я, а именно побежали прямо к коду из чистого любопытства, чтобы узнать, с чем мы имеем дело, и если вы хоть чем-то похожи на меня, скорее всего, вы довольно напуганы. Но не волнуйтесь, мы справимся с этим! Чтобы понять код, мы должны сначала иметь четкое представление о том, что на самом деле представляют собой связанные списки. Вместо того чтобы зачитывать синтаксис и надеяться, что наш мозг создаст для нас картинку, лучше сначала начать воображать. Это первое, что бросилось мне в глаза в связанных списках. Я обнаружил, что чем больше я на самом деле начинал представлять, с чем работаю, тем быстрее код материализовывался в моей голове.
Подумайте о связанном списке, как о поезде.
Головка – это двигатель . То есть узел в начале каждого связанного списка и последующие узлы в качестве вагонов. Каждый отдельный вагон и двигатель имеют 2 слота для данных, как упоминалось ранее, данные и адрес, указывающий на следующий узел.
Node(int t){
next=null;
data=t;
}
После того, как мы инициализируем конструктор Узел , мы передаем число, которое мы хотим сохранить, из основной функции, то есть переменной ‘t’. Адресное пространство равно null потому что тогда будет легче направить его на другие узлы. Кроме того, начальный узел всегда будет указывать на ноль, потому что мы строим список в обратном порядке и меняем положение головки, чтобы компенсировать это. Мы делаем это, потому что, если мы переместим голову вперед, у нас не будет возможности добраться до элементов сзади из-за невозможности вернуться назад в односвязном списке.
Вот код:
void insert(int data) {
Node2 t=new Node2(data);
if(head==null) {
head=t;
}
else {
t.next=head;
head=t;
}
}
Тот факт, что мы просто передаем значение функции и узлу с такой специфичной структурой, как эта, создается, сам по себе кажется волшебством. Ах, кто бы мог подумать, что абстракция и инкапсуляция могут быть такими прекрасными! Но подождите, нам еще предстоит погрузиться в самые пикантные места.
Хорошо, у нас есть основа для нашего связанного списка, но что, если бы мы хотели больше использовать возможности связанного списка. Давайте попробуем вставить значение между головкой и следующим узлом. Как я уже сказал, сначала давайте представим двигатель, то есть головку и вагон, то есть следующий узел. Соединение будет происходить следующим образом:
Если это еще не было видно из иллюстрации, не беспокойтесь. Это либо мои ужасные навыки рисования, либо мы просто лучше относимся к практическим примерам.
Итак, что здесь происходит, так это,
появляется новый железнодорожный вагон, и его необходимо соединить между двигателем и другим железнодорожным вагоном. Поэтому, помня об этом образе, для того, чтобы произошло сцепление, двигатель должен будет уступить место новому железнодорожному вагону. Но код немного отличается от реальности. На самом деле, новый вагон мог бы так же легко соединиться с другим вагоном без помощи двигателя, но в коде, если бы мы отсоединили головку (т. е. двигатель) , , другой вагон и все соответствующие вагоны будут потеряны, потому что мы не сохранили адрес. Поэтому, чтобы убедиться в подключении (т. е. адрес следующего узла) никогда не теряется, мы присваиваем адрес нового узла следующему узлу (В этом случае head.next – это адрес следующего узла) сначала адрес, прежде чем мы отсоединим движок (то есть голова). Теперь, когда мы убедились, что связь с другими вагонами всегда присутствует, мы можем безопасно отсоединить двигатель. Теперь, когда установлено соединение между новым узлом и последующим узлом, все, что нам нужно сделать, это подключить головку к новому узлу
Node inbtw(int data) {
Node t=new Node(data);
if(head==null) {
head=t;
}
else if(head.next==null) {
head.next=t;
}
else {
t.next=head.next;
head.next=t;
}
return head;
}
Мы создали эту сложную систему всего с несколькими строками кода внутри функции. Дает нам небольшое представление о прекрасной, но сложной природе простых вещей.
Теперь, когда у нас есть основы, давайте быстро перейдем к
как удалить узел из вашего связанного списка.
Теперь у вас есть поезд с двигателем и 2 вагонами, но может наступить время, когда вам нужно будет отпустить один из них. Так как же вы это делаете? Это просто! Когда дело доходит до подключения узлов, ваш адрес (т.е. “следующий” объект) является ключом. Точно так же, как вы назначили адрес своего нового узла узлу, который в настоящее время находится в вашем списке, когда вы хотели его подключить, все, что вам нужно сделать, это изменить адрес узла, предшествующего узлу, который вы хотите удалить, на узел, который присутствует после узла, который вы хотите удалить. Взяв пример с железнодорожным вагоном, вы изменяете соединение одного вагона с вагоном, который следует за ним 2 шага спустя, фактически делая вид, что вагона между ними никогда не существовало. Принимая во внимание код,
void delete() {
if(head==null) {
System.out.println("The list is empty");
return;
}
if(head.next==null) {
System.out.println("The list doesn't have a second element");
return;
}
if(head.next.next==null) {
head.next=null;
return;
}
head.next=head.next.next;
}
В этом коде мы удаляем второй элемент в списке, то есть узел между head и head.next.next. Обратите внимание, что после разрешения всех нулевых случаев адрес следующего узла из головы назначается узлу, который следует за этим узлом (т. е. узел, который занимает 2-е место после головы) , тем самым делая вид, что узел (т. е. Первый узел после головы) никогда там не был.
На рисунке пунктирная линия означает, что между 2 узлами раньше присутствовала связь. Вы можете видеть, что мы сместили адрес head.next, который указывал на head.next.рядом с заголовком, в этом случае вам может быть интересно, будет ли узел между ними все еще находиться в памяти. Ответ – да, но поскольку у нас нет адреса, указывающего на этот узел из нашего списка, он считается “удаленным” .
Наконец, давайте завершим основные функции нашего связанного списка функцией отображения, которая отображает все элементы. Относительно простой код, который не нуждается в объяснении, если вы зашли так далеко.
Node display(Node s) {
if(s==null||s.next==null) {
System.out.println(s.data);
return head;
}
Node e=display(s.next);
s.next.next=e;
s.next=null;
System.out.println(s.data);
return e;
}
На этом мы завершаем наш краткий обзор мира связанных списков. Ну, и как это было?
Если вы чувствуете себя еще более сбитым с толку, чем когда-либо, я сначала хотел бы извиниться, если я сделал так, чтобы это казалось сложнее, чем было на самом деле, и хотел бы сказать вам, чтобы вы не сдавались. Когда я только начинал, я тоже был по-настоящему сбит с толку, как и многие другие, но благодаря настойчивости и практике, медленно, но верно мы освоились, и вы тоже.
С другой стороны, если вы считаете, что эта статья каким-то образом помогла вам, я рад, что мы смогли поделиться этим опытом вместе. Просто помните, что это всего лишь взгляд в огромный мир Структур данных. Вы когда-нибудь пробовали перевернуть односвязный список? Звучит просто, не так ли? Что ж, попробуйте сделать это с помощью рекурсии для хорошей задачи. Если вы хотите больше практиковаться, проверьте эта проблема на ХакеррАнке . Говоря о связанных списках, мы обсудили только одну модель. Другие модели, такие как Двойные и Круговые связанные списки, только и ждут, чтобы вы их изучили.
Чтобы закончить это мыслью,
Я люблю связанные списки не только потому, что это была первая структура данных, которую я использовал в совершенно иной парадигме, чем остальные, не потому, что я потратил недели, чтобы понять ее, и не из-за ее широкого использования инкапсуляции и абстракции. Но главным образом потому, что это дало мне новый взгляд на кодирование в целом. Не поймите меня неправильно, я не мастер связанных списков и, конечно, не мастер структур данных. Ни в малейшей степени. Но это нормально, и тебе не следует. Это нормально, если вам понадобятся недели, чтобы понять 10 строк кода, это нормально чувствовать разочарование, выпить стакан воды и сделать перерыв, чтобы почитать книгу, когда вы чувствуете себя подавленным проблемой. В конце концов, важно то, чему вас научила эта проблема и как вы себя почувствовали в конце всего этого.
Вы изначально ненавидели эту проблему, но в конце концов обнаружили, что наслаждаетесь приливом адреналина, оглядываясь назад? Вам понравилось чувство замешательства и осознания того, что вы еще не закончили? Ну что ж, тогда ты программист, мой друг! В конце концов, это те эмоции, которые вызвали у меня связанные списки, и почему я до сих пор пишу код по сей день, надеясь и ожидая, когда следующая проблема проявит себя и проверит мои навыки.
Оригинал: “https://dev.to/sourabhsooraj/why-i-love-linked-lists-2oed”