Недавно я потратил некоторое время, чтобы начать изучать различные структуры данных. Первый, на который я посмотрел, — это связанный список. Я собираюсь рассказать, как настроить класс связанного списка в Javascript и как реализовать несколько основных методов в списке.
В отличие от массивов, которые хранят значения в доступных индексах, связанные списки не имеют индексов. Вместо этого списки состоят из узлов, которые содержат как значение, так и ссылку или ссылку на следующий узел. Поэтому со связанными списками мы не можем получить доступ к значению в середине списка, не просматривая каждый элемент, пока не доберемся туда. Однако вставить или удалить значение из списка становится намного проще, потому что нам нужно только изменить/обновить ссылки. С массивом вставка включает изменение индекса каждого элемента после. Так что, если вам не нужен доступ к случайным элементам, если вы не знаете размер или вам нужно постоянное время для вставки/удаления, то вам подойдет связанный список!
Чтобы настроить связанный список, мы создаем два класса. Первый — это наш класс Node, который будет содержать значение и ссылку на следующий узел. Второй — это наш класс LinkedList, который устанавливает заголовок (первый элемент в списке), хвост (последний элемент в списке) и длину.
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
}
let list = new SinglyLinkedList()
//prints SinglyLinkedList {length: 0, head: null, tail: null, push: ƒ, pop: ƒ}
let node = new Node("hello")
//prints Node {val: "hello", next: null}
Теперь, когда мы настроили базовую структуру наших двух классов, мы можем работать над несколькими методами, которые помогают обрабатывать наш список, включая push, pop, shift и unshift.
push(val)
С помощью нашего метода push мы хотим добавить значение в конец нашего связанного списка. Нам нужно создать новый узел со значением, сохранить текущий хвост в переменной, сбросить хвост и обновить ссылки. Это может показаться запутанным, но это довольно просто. Если в списке нет элементов, то вы устанавливаете голову и хвост для вновь созданного узла, добавляете 1 к длине и возвращаете список. Если есть элементы, то вы указываете текущий хвост рядом с вновь созданным узлом и сбрасываете хвост.
push = (val) => {
let node = new Node(val)
if (!this.head) {
this.head = node
this.tail = this.head
} else {
this.tail.next = node
this.tail = node
}
this.length += 1
return this
}
поп()
Метод pop() должен удалить последний элемент в списке и вернуть этот элемент. Сначала нам нужно учесть, пуст ли список и вернуть undefined. Теперь нам нужно перебрать все наши элементы, чтобы получить доступ к тому, что находится прямо перед хвостом. Этот элемент станет новым хвостом. Таким образом, мы создаем цикл, пока нашему текущему узлу назначен следующий узел. Как только мы доберемся до последнего элемента, цикл прервется (поскольку для следующего элемента хвоста установлено значение «null»). Теперь это дает нам новый хвост, поэтому мы сбрасываем хвост на это значение и устанавливаем этот новый хвост рядом с «нулевым». Наконец, мы уменьшаем длину. Если удаление элемента сделало список пустым, то мы можем установить начало и конец в «ноль», поскольку они больше не существуют.
pop() => {
if (!this.head) return undefined;
let current = this.head
let newTail = current;
while (current.next) {
newTail = current
current = current.next
}
this.tail = newTail;
this.tail.next = null
this.length--
if (this.length === 0) {
this.head = null
this.tail = null
}
return current
}
сдвиг()
Shift удаляет первый элемент в нашем списке и возвращает его. Довольно просто. Во-первых, если головы не существует, мы возвращаем значение undefined, поскольку удалять нечего. Затем мы создаем переменную для хранения текущей головки. Мы сбрасываем заголовок списка, чтобы он равнялся следующему узлу старого заголовка. Затем уменьшите длину (и если она теперь равна 0, мы установим хвост в «ноль». Наконец, верните удаленную голову!
shift(){
if (!this.head) return undefined
let head = this.head
this.head = head.next
this.length--
if (this.length === 0) this.tail = null
return head
}
сдвинуть(val)
Наконец, unshift принимает значение, которое мы хотим добавить в начало списка. Мы создаем узел, используя это значение. Далее проверяем, есть ли уже головка. Если нет, мы устанавливаем голову и хвост для созданного нами узла, поскольку это единственный элемент в списке. В противном случае, если заголовок существует, мы устанавливаем наш вновь созданный узел next равным текущему заголовку и сбрасываем заголовок списка на наш вновь созданный узел. Увеличьте длину и верните список.
unshift(val) {
let node = new Node(val)
if (!this.head) {
this.head = node
this.tail = this.head
} else {
node.next = this.head
this.head = node
}
this.length++
return this
}
Существует множество других методов, которые вы можете реализовать для улучшения односвязных списков: get (извлекает узел по определенному индексу), set (изменяет значение по определенному индексу), remove (удаляет узел по определенному индексу) и т. д. Было интересно узнать о другом способе хранения данных, который в определенных ситуациях даже лучше, чем использование массивов! Двусвязные списки очень похожи, за исключением того, что каждый узел также имеет ссылку, указывающую на предыдущий узел, поэтому вы можете перемещаться по списку в любом направлении. Забавный материал!
