На прошлой неделе я рассмотрел, что такое (односвязные) списки, теперь давайте вернемся и посмотрим, что мы можем с ними сделать.
Напоминаем, вот диаграмма, изображающая связанный список:
А вот код, который мы использовали для его реализации:
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor(){
this.head = null
}
insertAtHead(node){
this.head = node
}
clearList(){
this.head = null
}
}
Таким образом, предпосылка заключается в том, что мы продолжаем добавлять nodes к head, и они будут ссылаться на следующие node. Следующий node будет ссылаться на node рядом с ним, и эта цепочка продолжается, пока мы не достигнем tail (который был первым вставленным node). На данный момент мы знаем, что это tail, так как он не ссылается ни на какие другие nodes.
Пока что мы реализовали метод для вставки node в head, а также метод для очистки всего списка. Но как насчет промежуточных методов?
Допустим, вместо вставки в head мы хотели вставить узел в tail. Как мы могли это сделать? Давайте работать над этим.
Сначала давайте попробуем получить правильные узлы. Легче всего получить узел head или первый узел. Мы можем использовать следующее внутри нашего класса связанного списка:
getFirstNode(){
return this.head
}
Простой не так ли? Что ж, давайте применим ту же логику захвата узлов, чтобы захватить наш последний узел. Помните, мы знаем, что у нас есть хвост, как только мы достигаем узла, который, когда мы вызываем node.next, будет nil. И в нашем списке есть только один узел, который делает это, поэтому нам просто нужно повторять, пока мы не найдем его! Давайте посмотрим, как это выглядит в виде кода:
getLastNode(){
let currentNode = this.head
//this will serve as our temporary node that is keep track
//of where we are in the list
while(currentNode.next){ //while node.next is truthy we continue
currentNode = currentNode.next //reassign the current node
}
return currentNode // our loop will break when it doesn't have a
// next node, so we always stop at the tail
}
Итак, на данный момент мы добрались от одного конца связанного списка до другого конца. Помните, как мы вставляем узел? Мы должны дать ссылку
Теперь, чтобы мы могли вставить в конце, давайте просто дадим tail ссылку на следующий узел, который мы хотим вставить!
insertAtLast(data){
const last = this.getLastNode() // DRY! Just reuse your code from before!
last.next = new Node(data)
}
На данный момент мы создали связанный список и добавили в него nodes. Если бы мы хотели проверить, вызываем ли мы просто linkedListExample.getFirstNode() или linkedListExample.get LastNode(), просто чтобы еще раз проверить, действительно ли мы вставили nodes и в правильную позицию. Мы также могли бы попытаться реализовать проверку того, что все наши nodes все еще там, создав функцию, которая проверяет размер/длину связанного списка. Логика здесь состоит в том, чтобы просто пересчитать все node в списке, пока мы не наткнемся на последний. Это очень похоже на то, что мы сделали, чтобы получить последний элемент:
getSize(){
const currentNode = this.head //we start at the head
let counter = 0 // this will keep track of how many there are
while(currentNode){ //this will break after we've counted our last node
currentNode = currentNode.next
counter++
}
return counter
}
Теперь мы знаем, какой длины список, как взять head и tail и как добавить в начало и конец. Давайте разберемся, как их удалить!
Начнем с того, что head. Теперь мы должны быть осторожны с крайним случаем, когда в связанном списке ничего нет. В противном случае мы могли бы просто переназначить head и двигаться дальше:
removeFirstNode(){
if(!this.head){
return //if there's no head, just break out of the function
} else {
this.head = this.head.next //our previous head doesn't even exist to
//us anymore
}
}
Теперь, когда мы удалили head. Давайте прыгнем в кроличью нору и удалим tail. Нам все равно нужно будет отслеживать крайний случай, когда в списке ничего нет. Но мы также должны помнить, что если есть только head, нам больше ничего не нужно делать. Что касается ядра этого метода, мы должны продолжать итерацию, пока не дойдем до точки, где node.next.next === nil. Это немного сбивает с толку, я знаю, но это просто означает, что мы достигли node, чье next существует, поскольку мы все еще можем связать с ним next, но node’s следующим будет nil; и поскольку мы знаем, что tail’s next равно nil, у нас есть предпоследний узел! Вот в виде схемы:
Теперь для кода:
removeLastNode(){
if(!this.head){
return //again, if it's empty let's just break out of the function
} else if(!this.head.next){
this.head = null
return //if we only have the head, we have nothing else to do
} else {
let currentNode = this.head //this keeps track of our current node
let nextNode = this.head.next //this is to track the next node
while(nextNode.next){ //will break when we get to the 2nd to last node
currentNode = currentNode.next
nextNode = nextNode.next
}
currentNode.next = null // we remove the reference to the old tail
}
}
Не так уж плохо, верно? Это просто вопрос обдумывания и выяснения того, какая логика должна быть применена. Я думаю, что наличие ручки и бумаги и возможность начертить эти узлы также помогают. По крайней мере, если вы не можете придумать код на месте для собеседования, по крайней мере, вы можете пройтись по логике того, как подойти к проблеме.
Надеюсь, это поможет!
Ресурсы:
