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

Связанный список похож на массив

Связанный список - это структура данных, в которой хранятся данные, аналогичные массиву в том смысле, что это структура, представляющая список. В массиве каждый элемент индексируется, например, начиная с 0 и доходит до длины массива-1. Таким образом, если в массиве 9 объектов, первый индекс в массиве начинается с 0, а последний индекс заканчивается на 8. Однако связанный список состоит из элементов. Индекса нет. Это означает, что порядок не определяется индексированным значением, как массив.

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

Связанный список состоит из элементов. Каждый элемент - это узел. Узел имеет значение и указатель на другой узел или ноль. Значения в каждом узле представляют данные (строки, числа, массивы и т. Д.) В нашем списке, а указатели в каждом узле определяют порядок связанного списка; он ссылается на следующий узел или, если он находится в самом конце, конца нет, поэтому он ссылается на null. Свойства связанного списка: начало (начало), хвост (конец) и длина (длина списка). Головной элемент - это первый элемент. Он имеет значение и указатель на узел следующего элемента. При использовании связанного списка мы не можем получить доступ к пятому элементу в списке, не пройдя через первые четыре элемента в связанном списке, в отличие от массива, где мы можем использовать array [4] для доступа к пятому элементу.

Односвязный список

Односвязный список - это список узлов, которые указывают на другие узлы и перемещаются только в одном направлении, от начальной точки к концу, а не наоборот. Двусвязный список также имеет соединение, указывающее на предыдущий узел. И в отличие от массивов, здесь не разрешен произвольный доступ, а это означает, что для перехода по списку к определенному узлу мы должны пройти через все предыдущие узлы.

Узлы

Узел - это часть данных, которая содержит значение и ссылку на следующий узел. Давайте создадим узел. Для начала нам нужно создать класс узла. Я рассмотрел синтаксис классов JavaScript в своем предыдущем сообщении в блоге: Понимание структур данных: синтаксис классов в JavaScript, ссылка на который приведена здесь в качестве справки.

class Node{
   constructor(value){
     this.value = value;
     this.next = null;
   }
}
let first = new Node("pikachu")
first.next = new Node("caterpie") 
first.next.next = new Node("mankey") 
// pikachu => caterpie => mankey

Если мы запустим first в нашем терминале после создания вышеуказанного кода, мы увидим связанный список.

Однако вместо того, чтобы объявлять узел таким образом и использовать .next снова и снова, мы создадим класс LinkedList, который будет содержать заголовок со значением null, хвост со значением null и длину 0 для начала, например так:

class SinglyLinkedList{
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

В нашем связанном списке есть несколько методов, которые мы можем создать для вставки, удаления и обхода связанного списка. Однако в этом посте мы сосредоточимся только на одном из основных моментов; метод push, который добавляет новый узел в конец нашего связанного списка. Наш метод push принимает значение и создает новый узел из значения, переданного в функцию. Если головы нет, мы устанавливаем голову и хвост в качестве нового узла. Если есть голова, мы устанавливаем следующее свойство хвоста как новый узел, а затем мы устанавливаем хвост как новый узел. В конце функции мы увеличиваем длину класса связанного списка на единицу.

push(value) { 
 //declare the new node with the passed in value
  let node = new Node(value)
 //condition if there is no head
  if(!this.head){
    this.head = node
    this.tail = this.head
 //set passed in value to be tail.next and set tail to latest value
  } else {
    this.tail.next = node
    this.tail = node
  }
 //increment the length of the list
  this.length++
  return this
}

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

class Node{
   constructor(value){
     this.value = value;
     this.next = null;
   }
}
class SinglyLinkedList{
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  } 
  push(value) {
    let node = new Node(value)
    if(!this.head){
      this.head = node
      this.tail = this.head
    } else {
      this.tail.next = node
      this.tail = node
    }
    this.length++
    return this
  }
}
//Sample
let shoppingList = new SinglyLinkedList()
shoppingList.push("Oat Milk")
shoppingList.push("Tofu")
shoppingList.push("Beans")
shoppingList
   //Oat Milk => Tofu => Beans