На этой неделе во время учебы я хотел повторить то, о чем мне недавно напомнили: связанные списки.
Связанные списки являются одной из наиболее распространенных структур данных, которые вы увидите, и представляют собой жизнеспособный вопрос на собеседовании, который может возникнуть, поскольку другие типы данных, такие как стеки и очереди, могут быть построены с использованием связанных списков. Есть несколько вариантов, сегодня я рассмотрю односвязный список.
Проще говоря, это похоже на цепочку:
Одно звено цепочки связано с другим, которое связано с другим и т. Д. Теперь давайте посмотрим на реальный пример связанного списка:
Давайте разберем этот список. Обратите внимание, что он состоит из 4 элементов, эти элементы обозначаются как nodes. Каждый node будет иметь data / info и pointer. Как вы можете догадаться, data - это информация, которую хранит node; pointer будет ссылаться на следующий node.
Обратите внимание, что в этом односвязном списке есть только однонаправленная ссылка. В начале связанного списка стоит head, а в конце - tail. Узел tail не имеет следующей ссылки, а будет ссылаться на null.
nodes вставляются в головку, а остальные nodes «толкаются» вниз. Было бы легче понять это с помощью визуализации, чем просто чтения. Итак, давайте взглянем на другую (красноречиво нарисованную) диаграмму:
Затем, если мы захотим добавить к нему:
Обратите внимание, что новый head будет указывать на старый head. Предыдущий head по-прежнему указывает на ноль. Чтобы довести дело до конца, давайте добавим еще один узел.
Вот как создаются односвязные списки и как происходит их вставка.
К настоящему времени вы должны понимать, что связанные списки - это всего лишь nodes ссылки на следующий за ним. Давайте теперь посмотрим, как построить node с помощью конструкторов классов ES6.
class Node {
constructor(data, next = null) {
//notice that next defaults to null
//this is primarily used for us to set up our first node
this.data = data;
this.next = next;
}
}
Теперь, чтобы собрать наш связанный список:
class LinkedList {
constructor(){
this.head = null
// this way we start off with an empty linked list
}
}
В этом посте я хочу рассказать, как вставить в заголовок и как удалить список. Это основы работы со связанным списком, и на следующей неделе мы рассмотрим другие методы. Теперь давайте проверим код для добавления нового node в head.
//Inside the class LinkedList
insertAtHead(data){
this.head = new Node(data, this.head)
}
Обратите внимание: поскольку мы инициализировали наш LinkedList класс с this.head = null, ссылка на next первого узла будет null. Впоследствии новый heads будет ссылаться на node, который был создан до него.
К этому моменту вы могли понять, как очистить список:
clearList(){
this.head = null
}
Просто как тот! Без ссылки на что-либо, для всех предполагаемых целей, этот список теперь «пропал». Всего два класса:
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
}
}
На следующей неделе я рассмотрю некоторые методы работы со связанными списками.
Ресурсы:
