Я начал изучать связанные списки, чтобы завершить алгоритм. В инструкциях поясняется, что этот алгоритм имеет два аргумента: связанный список и целое число. Цель состоит в том, чтобы вернуть значение узла, которое является (целым) числом узлов с конца или хвоста списка. Мои первоначальные мысли были такими: почему бы не использовать массив? Почему в связанных списках нет методов, облегчающих такую проблему? Почему я? и т. д.
В любом случае, связанные списки требуют некоторого привыкания, и, как и большинство концепций веб-разработки, их стоит изучить, попрактиковаться и написать об этом в блоге. Мне довольно удобно реверсировать и перемещаться по связанному списку, и я надеюсь, что после прочтения этого вы будете тоже.
Прежде чем продолжить, подумайте о том, чтобы изучить это руководство для начинающих о связанных списках от freeCodeCamp.
Давайте рассмотрим, что такое связанный список: линейная структура данных, состоящая из последовательности узлов, где каждый узел содержит данные и ссылку (или ссылку) на следующий узел в последовательности. Они занимают меньше памяти, чем массив, и поэтому они полезны. Для целей этого блога мы будем думать о связном списке как о поезде. Каждый вагон в поезде является узлом в списке. Связь между автомобилями является свойством узла, который ссылается на свой следующий узел. Свойство данных в узле — это содержимое каждого автомобиля.
Наиболее важной концепцией здесь является то, что для того, чтобы попасть из head связанного списка или first node (первый вагон поезда) в tail связанного списка или last node (последний вагон поезда), нужно пройти через каждый узел или вагон до тех пор, пока достигается последний узел или любой другой необходимый узел. Связанные списки обычно проходятся с помощью циклов, когда список проверяется по одному узлу за раз, и каждый узел используется или обрабатывается в каждой итерации цикла. Вместо использования цикла while или for есть другой вариант — рекурсия, которая столь же эффективна, но может быть не лучшим инструментом при первом изучении связанных списков.
Давайте посмотрим на картинку выше, мы видим, что глава списка идентифицируется вагоном-кондуктором, а стрелка, указывающая на следующий вагон, имеет тот же цвет, что и вагон-кондуктор. Стрелку можно считать nextсвойством узла. Каждый узел имеет как минимум два свойства: свойство next, которое также можно считать указателем, и свойство data. Свойство data содержит данные в списке.
Для наших целей данные узла будут числом, в других случаях это может содержать информацию для файловых систем, музыку в списке воспроизведения и т. д. Слово data может быть value или любым термином языка, который вы используете. предоставляет, он также может быть изменен на любой термин, который вы хотите, в зависимости от ваших требований. Красный указатель после последнего узла или хвоста будет указывать на null, указывая на конец списка.
Прежде чем мы приступим к обходу и обращению связанного списка, давайте определим еще одну точку зрения, которая может помочь визуализировать связанные списки. Вероятно, вам достаточно комфортно с объектами или, по крайней мере, с тем, как они выглядят. Связанный список не похож на объект, но объект в JavaScript может использоваться для реализации связанного списка. Давайте посмотрим на код ниже, мы видим, что головной узел — это объект с двумя свойствами:
следующий: указатель на другой объект
data: число, которое содержит этот узел
Node {
next: Node { next: Node { next: Node { next: [Node], data: 4 }, data: 3 }, data: 2 },
data: 1
}
// OR
Node {
next: Node {
next: Node {
next: Node {
next: [Node],
data: 4 },
data: 3 },
data: 2 },
data: 1
}
//The [Node] in brackets identifies many other nodes not listed here but can contain hunrdeds and thousands more nodes
Итак, первый шаг в нашей проблеме — определить, что мы пытаемся сделать, мы хотим получить список и вернуть его перевернутую версию, где последний элемент в списке станет первым, а второй — вторым. -последний элемент станет вторым элементом и т. д. и т. д. по всей длине списка. Мы не знаем, какова будет длина, поэтому наша временная сложность будет линейной или O(n), потому что мы будем запускать цикл по каждому узлу вплоть до длины. Наша пространственная сложность будет постоянной или O (1), потому что мы будем работать с одними и теми же переменными, хранящими одну и ту же информацию, независимо от размера списка.
Выше мы видим, что при реверсировании связанного списка нам просто нужно изменить указатель или изменить узел, который находится в пределах свойства next текущего узла. Каждый узел в перевернутом списке не изменился. Его цвет тот же, его данные такие же, единственная разница в том, что указатель теперь указывает на предыдущий узел в списке. Это означает, что каждый узел теперь указывает на узел, который был до него, а не на узел, который идет после него.
Изменение, которое мы вносим, заключается в том, что мы сообщаем узлам, что следующее свойство указывает на предыдущий узел.
Наша цель — переназначить значение current.next предыдущему узлу.
Отбросив эту концепцию, давайте приступим к кодированию функции, которая обратит наш связанный список. Есть несколько переменных, которые нам нужно настроить, чтобы получить этот новый перевернутый список. Нам также нужно перебирать каждый узел до тех пор, пока в списке не закончатся узлы. Начнем с этого.
function reverseList (linkedList) {
let current = linkedList;
while (current !== null) {
//perform our reversals here
};
};
Мы создали функцию под названием reverseList, которая позволит нам ввести linkedList.. Мы создали переменную для хранения нашего linkedList, названную current.. Список current будет обрабатываться снова и снова внутри цикла while, постоянно обновляясь, чтобы указать на обратный список. Вскоре нам понадобятся некоторые другие переменные, чтобы справиться с этим. Мы также установили цикл while, который будет выполняться до тех пор, пока текущий не равен нулю.
Давайте добавим переменную для хранения нашего обратного списка и другую для хранения оставшихся узлов из нашего списка после того, как мы изменим текущий указатель, чтобы он указывал на предыдущий узел.
function reverseList(linkedList) {
// reverse is initially set to null as it will be set to follow our
// current node
let reverse = null;
let current = linkedList;
while ( current !== null ) {
// forward is set to equal current.next which is all the nodes
// following the current node
let forward = current.next;
};
};
Давайте посмотрим на изображение ниже, чтобы понять, зачем они нам нужны.
reverse изначально имеет значение null, потому что нам нужно что-то предоставить current.next. При дальнейших итерациях reverse будет содержать каждый узел, который мы ему передаем. По сути, мы говорим, что первое значение, которое должно быть reverse, является последним значением списка, с которого мы начали.
current установлен в список, с которого мы начинаем, он оценивается как первый узел или вагон кондуктора и включает указатель на следующий узел в списке, синий узел со значением 2.
forward устанавливается на current.next, потому что как только мы изменим узел, на который указывает current, мы потеряем соединение или указатель, показанный ниже фиолетовой стрелкой. Мы скажем указателю смотреть на реверс, который изначально равен нулю. Мы захотим установить current в forward, как только мы закончим с циклом, чтобы мы могли продолжить процесс на следующей итерации.
Теперь, когда мы сохранили current.next под переменной forward, мы хотим сообщить current, что он указывает на что-то другое. Мы добьемся этого, установив current.next равным reverse, в нашем случае это будет равно нулю.
function reverseList(linkedList) {
let reverse = null;
let current = linkedList;
while ( current !== null ) {
let forward = current.next;
// the next property of current will now point to reverse
current.next = reverse;
};
};
Указатель был переназначен, но теперь у нас есть исходный узел current, и мы должны сохранить его как головной узел в reverse. Мы добьемся этого, установив или перезаписав reverse равным current. Наш текущий узел — фиолетовый вагон поезда, и у него есть два свойства: data, которое оценивается как 1, и next, которое оценивается как null. Это значение, которое мы хотим присвоить reverse.
function reverseList(linkedList) {
let reverse = null;
let current = linkedList;
while ( current !== null ) {
let forward = current.next;
current.next = reverse;
// now that current is pointing to the previous value of reverse AND
// forward is storing the original current.next THEN
// we can tell reverse that it evaluates to current WHICH
// in this loop is our reversed list with a single node
reverse = current;
};
};
Теперь, когда наша переменная reverse хранит наш перевернутый список, а forward сохраняет оставшиеся узлы из исходного списка current, нам нужно установить current в forward. Таким образом, наш цикл снова будет работать на протяжении всей длины linkedList, предоставленной нашей функции reverseList.
function reverseList(linkedList) {
let reverse = null;
let current = linkedList;
while ( current !== null ) {
let forward = current.next;
current.next = reverse;
reverse = current;
// since we've manipulated current for our purposes, it is empty
// we need to store forward as current for the next iteration of the loop
current = forward;
};
};
Давайте посмотрим, как будут выглядеть наши значения, когда мы войдем в следующую итерацию цикла.
reverse теперь равен исходному первому узлу из current в нашей предыдущей итерации.
current теперь равно узлу 2 вместе с его указателем, который указывает на остальную часть связанного списка, который мы еще не инвертировали.
forward устанавливается на current.next, что во время этой итерации представляет собой весь список после узла 2.
Давайте еще раз применим тот же код из нашего цикла и визуализируем, что происходит.
while ( current !== null ) {
let forward = current.next;
current.next = reverse;
reverse = current;
current = forward;
};
Мы укажем current.next на значение reverse, изменив указатель на обратный список.
Мы перезапишем reverse значением current, которое будет представлять собой узел 2, указывающий на узел 1, указывающий на ноль.
Затем мы установим current в forward, что является частью исходного списка current, с которым мы будем продолжать работать, пока выполняется цикл, пока не достигнет null..
Цикл while перестанет выполняться, когда внутри current больше не будет узлов и его оценка будет равна null. Это означает, что мы хотим вернуть reverse, который будет оцениваться как перевернутая версия нашего списка.
function reverseList(linkedList) {
let reverse = null;
let current = linkedList;
while ( current !== null ) {
let forward = current.next;
current.next = reverse;
reverse = current;
current = forward;
};
return reverse;
};
Что будет выглядеть так:
И вот так, если вы войдете в свою IDE:
Node {
next: Node { next: Node { next: Node { next: Node { next: Node { next: null, data: 1}, data: 2 }, data: 3 }, data: 4 }, data: 5 },
data: 6
}
// OR
Node {
next: Node {
next: Node {
next: Node {
next: Node {
next: Node {
next: null,
data: 1},
data: 2 },
data: 3 },
data: 4 },
data: 5 },
data: 6
}
Надеюсь, эта визуализация поможет вам понять, как перевернуть список, перебирая его в цикле! Удачного кодирования!
