Обращение связанного списка в JavaScript

Добро пожаловать на мою четвертую задачу по программированию, и я должен сказать, что она будет немного отличаться от предыдущих. Во-первых, я использую более информативный заголовок! Кроме того, я собираюсь использовать JavaScript! Я готовился к техническому собеседованию по JavaScript и хочу оставаться в курсе. Я все еще объясню логику, чтобы те, кто более знаком с Python или другим языком программирования, все равно могли понять, что происходит.

Переворачивание связного списка может показаться произвольным, но это частый вопрос собеседований, поэтому его стоит понять и потренироваться.

Хорошо, готовы? Это вызов, состоящий из двух частей. Сначала нам нужно определить, что такое связанный список, а затем мы займемся его реверсированием.

Что такое связанный список?

Связанный список - это структура данных, которая является просто причудливым способом сказать «способ организации информации». Например: группа людей может быть организована в виде списка (порядок имеет значение), пакета именных тегов (без порядка), генеалогического дерева (разветвленный порядок) и т. Д. Существует много способов организации данных, но список можно довольно интуитивно понятный и отличный вариант для начала, если вы не знакомы со структурами данных.

Итак, как работает связанный список? Приведем аналогию: представьте, что вы стоите в очереди за билетами в кино - назовем вас A мой. Очередь проходит в очень узком коридоре, и вы можете видеть только человека перед собой, B арри - вы даже не можете обернуться! Эта строка напоминает связанный список. Каждый человек или узел имеет собственное значение (например, имя) и ссылку на следующий узел (человека перед вами). Вот и все! Эта простая структура данных допускает некоторые интересные нюансы.

Хорошо, хватит разговоров, давайте писать код!

То, как я предпочитаю реализовать LinkedList, - это работать снизу вверх, начиная с создания класса Node.

Объект Node начинается очень просто с инициализации значением и ссылкой на другой узел через свойство .next.

const Amy     = new Node("Amy");
const Barry   = new Node("Barry");
const Cameron = new Node("Cameron");
Amy.next   = Barry;
Barry.next = Cameron;
Amy.next;     // Node {val:"Barry", next: Cameron}
Barry.next;   // Node {val:"Cameron", next:null}
Cameron.next; // null

В приведенном выше коде мы устанавливаем 3 узла: A my, B arry и C ameron. Думайте об этих узлах как об отдельных бусинах, не связанных друг с другом. Затем мы соединяем их, устанавливая Amy.next как Барри, а Barry.next как Кэмерон (мы ничего не делаем с Cameron.next). Теперь три узла соединены - почти как бусины!

Давайте представим, что начинаем с A my и задаемся вопросом, есть ли где-нибудь в ссылке C ameron. Алгоритм обхода списка довольно прост:

Проверьте, имеет ли корень (Эми) желаемое значение, если нет, перейдите на узел .next.
Повторяйте до тех пор, пока значение не будет найдено или не будет достигнут конец (null)

В этом случае мы будем двигаться мимо Эми и Барри, пока, наконец, не найдем Кэмерон и не вернемся true. Если бы мы попытались найти Дженни, то попали бы в конец списка (Cameron.next) и вернули бы false. Посмотрим, как будет выглядеть этот обход:

Вы также можете поиграть с этим кодом на Repl.it - LinkedList в JavaScript.

Функция listContains принимает заданный корневой узел (начало списка) и значение. Он будет продолжать перебирать каждый узел .next, пока либо не будет найдено правильное значение (вернув истину и завершив цикл), либо .next в конечном итоге установит узел curr на null, завершив цикл и вернув ложь.

Последний шаг пути - осознать, что все эти взаимодействия со списком узлов станут очень утомительными и очень быстро. Хороший программист абстрагируется от ответственности за взаимодействие со сборкой узлов, похожей на бусинки, и создает другой класс. Итак ... давайте создадим класс LinkedList, который отвечает за простые взаимодействия со списком, такие как проверка значения, вставка значения в определенной точке, удаление узла, поиск с k-го до последнего элемента, реверсирование списка (😉) , и т.д.

Это простая реализация, но вы можете видеть, что наша LinkedList начинается с… почти ничего - даже с корневого узла! Итак, как нам добавить новый узел? Отличный вопрос! Интересно, кто или что должен нести ответственность за добавление новых узлов в список.

Технически мы МОЖЕМ добавить узел вручную, но при этом упускается смысл наличия класса LinkedList. Давайте добавим append метод к LinkedList.

Метод append должен учитывать 2 возможные ситуации. A) Если корень не существует (это null), мы просто устанавливаем свойство .root для вновь созданного узла с заданным значением. B) Если корень действительно существует, метод будет продолжать перебирать узлы до тех пор, пока последний (без .next) не будет найден и его свойство .next не будет установлено на вновь созданный узел.

Вы не поверите, но мы закончили работу с основными функциями связанного списка! Мы могли бы включить другие методы, такие как удаление узла на основе его значения, но я оставлю это в качестве упражнения для читателя 😄 (подумайте, что произойдет, тогда корень - это узел, который нужно удалить).

Переворачивание связанного списка

Имейте в виду, что единственная ссылка, с которой мы должны начать, - это корневой узел. Итак, как нам перевернуть список, когда все, что у нас есть, - это корневой узел? Что ж, все дело в замене ссылки .next на предыдущий узел с сохранением ссылки .next на будущее. Вот логика:

Начните с корневого узла и сохраните ссылку .next в переменной. Назовем эту переменную «savedRef».
Установите .next корневого узла на null, поскольку он станет последним узлом, у которого .next = null.
Сохраним ссылку на корневой узел, так как нам нужно будет установить его как .next дочерний узел для следующего узла в списке. Назовем эту переменную узлом «prev» для предыдущего.
Теперь мы настроили следующий узел в списке, который был сохранен в переменной «savedRef».
Мы повторяем те же шаги, что и раньше… мы сохраняем .next узла в переменной «savedRef». Мы устанавливаем .next как узел «prev» (раньше мы использовали null, но теперь у нас фактически есть .next цель). Затем мы настраиваем следующий узел в списке и повторяем, пока не дойдем до конца.
В конце мы устанавливаем последний узел как новый корневой узел.

Вот как выглядит код:

let prev = null;
let curr = root;
let savedRef;
while(curr){
    savedRef = curr.next; // storing reference to next
    curr.next = prev;     // reversing
    // setting up for next iteration
    prev = curr;
    curr = savedRef; // the last node will set this to null
}
root = prev; // prev was the last node

Вот небольшая анимация, которая поможет визуализировать процесс.

Вот полная реализация в классе LinkedList - играйте с ней весело!

В целом, некоторые из самых сложных частей - это хорошее понимание ООП и отслеживание ссылок на узлы. Существует ТОННА связанных понятий, к которым вы можете перейти отсюда, например, очереди и стеки, не говоря уже о дополнительных возможностях повышения эффективности, таких как длина списка или сохранение ссылки на последний узел.

Вас просили перевернуть связанный список на техническом собеседовании? Есть ли другие способы разворота?

Я все еще обсуждаю свою следующую статью, но я хотел попробовать что-то другое, так что мы посмотрим, что я придумаю! До скорого!

Обращение связанного списка в JavaScript