Связанные списки

На прошлой неделе у меня была возможность начать изучать связанные списки, решить пару задач на Leetcode, а также вернуться к урокам алгоритмов после выпуска, которые Flatiron School проводит на Learn.co. Хотя я скучаю по массивам, к которым привык, я понимаю, что для меня важно быть знакомым со связанными списками и проводить больше времени, работая с разными структурами данных.

Хэши и переменные

Задачи для лаборатории связанных списков на Learn.co работают с таким набором данных:

let firstNode = {name: 'susie', next: 'rkjasj'}
let secondNode = {name: 'sam', next: 'asnan'}
let newNode = {name: 'jill', next: ''}
let lastNode = {name: 'charlie', next: null}
let collection = {rkjasj: secondNode, asnan: lastNode, whana: firstNode, ajhsak: newNode}
let linkedList = 'whana'

Каждый из узлов является частью хэша «коллекции» с ключом к каждому из узлов. Разделение firstNode, secondNode и т. д. делает его более читабельным. В противном случае «коллекция» будет выглядеть так:

{rkjasj: {name: 'sam', next: 'asnan'}, asnan: {name: 'charlie', next: null}, whana: {name: 'susie', next: 'rkjasj'}, ajhsak: {name: 'jill', next: ''}}

Это немного вводит в заблуждение, когда «whana» является третьим узлом в коллекции, когда он возглавляет связанный список, но в любом случае мы получаем информацию о том, что это первый узел. Я думаю, что это либо опечатка, либо мне нужно обдумать более глубокий смысл. На самом деле, я думаю, дело в том, что у хэшей нет индексов, как у массивов.

Нам также предоставляется переменная «linkedList», которая сообщает нам, какой из узлов в хэше является головным. Другими словами, «коллекция [связанный список]» дает нам первый узел.

Функция удаления узла

В то время как лаборатория просит нас написать восемь различных функций для различных способов манипулирования узлами, я собираюсь сосредоточиться здесь на функции для удаления узла. Вот код, который я написал, который я объясню ниже.

function deleteNodeAt (index, linkedList, collection) {
let currentNode = collection[linkedList];
let currentIndex = 0;
let addressForAddingNext;
let addressToAdd;
while (currentIndex <= index){
if (currentIndex === index - 1){
addressForAddingNext = currentNode;
currentIndex +=1;
currentNode = next(currentNode, collection);
}
else if (currentIndex === index){
addressToAdd = currentNode.next;
addressForAddingNext.next = addressToAdd;
currentIndex +=1;
currentNode= next(currentNode, collection);
}
else{
index += 1;
currentNode= next(currentNode, collection);
}
}

В функцию передаются три аргумента: index, linkedList и collection. Индекс — это позиция узла, который мы должны удалить в коллекции. Две другие переменные указаны выше.

Цикл while выполняется до тех пор, пока текущий индекс меньше или равен индексу узла, который мы удаляем. В начале я установил currentIndex равным нулю. Затем, когда цикл while запущен, если позиция индекса, в которой мы находимся, на 1 меньше целевого числа, функция получает адрес этого узла, чтобы использовать его позже. Причина, по которой он нам понадобится, состоит в том, чтобы изменить адрес, на который указывает «следующий» ключ этого узла, поскольку текущий адрес — это тот, который удаляется. Мы хотим, чтобы он указывал на адрес узла, который в настоящее время следует за удаляемым. Это похоже на удаление лягушки из игры в чехарду (отказ от ответственности: я не помню, как на самом деле работает эта игра).

Пример первого прохода через цикл while

Если переданный индекс равен 1, то первое условие будет выполнено при первом проходе цикла, поскольку currentIndex изначально равен 0. Итак, addressForAddingNext = collection[linkedList], или, другими словами, addressForAddingNext = firstNode. CurrentIndex увеличивается на единицу, а затем мы используем функцию, которую мы написали ранее, чтобы перейти к следующему узлу и сбросить на него значение currentNode.

Переход к следующему узлу

Чтобы не быть слишком загадочным, функция перехода к следующему узлу такова:

function next (node, collection){
return  collection[node.next];
}

Если мы вызовем next() с firstNode (значение «whana» в «коллекции») и передать всю «коллекцию», это будет узел, с которым мы имеем дело, значение firstNode:

{name: "susie", next: "rkjasj"}

Если мы вызовем next для первого узла (firstNode.next), мы получим «rkjasj». Затем, если мы подключим это к «коллекции», вот так

collection['rkjasj']

мы получаем следующий узел, secondNode, со значением {name: «sam», next: «asnan»}. SecondNode становится текущим узлом для следующего раунда.

Что делать, когда вы достигли целевого индекса

При следующем проходе цикла в приведенном выше примере индекс будет соответствовать значению «currentIndex». Здесь мы можем получить ключ, чтобы сбросить «следующее» значение для узла по предыдущему индексу.

«CurrentNode» теперь является «secondNode», установленным в значение {name: «sam», next: «asnan»}, и если мы вызовем для него next (secondNode.next), мы получим «asnan», ключ следующий узел в связанном списке «коллекция». Мы больше не хотим, чтобы первый узел указывал на второй, потому что мы хотим удалить второй. Итак, мы можем сделать «следующее» значение первого узла «asnan», чтобы пропустить второй узел и сразу перейти к третьему.

Если бы во втором цикле мы еще не добрались до узла, который нужно удалить, то мы просто увеличили бы currentIndex, перешли бы к следующему узлу и прошли бы цикл, пока не доберемся до него.

Но разве второй узел не живет где-то в памяти компьютера? Разве его там нет, даже если он больше не является частью связанного списка, загромождая какой-то забытый угол, заваленный всем остальным, до чего я сегодня не добрался?

Учитель, у меня вопрос.

À предлагает попытаться удалить определенные вещи из нашей жизни.