Реализация связанных списков в JavaScript

Связный список — это структура данных, очень похожая на массив, за исключением того факта, что данные не хранятся в одной ячейке памяти. В JavaScript каждый элемент (узел) связанного списка — это объект, который указывает на следующий элемент (узел), который также указывает на следующий элемент связанного списка, пока последний элемент не указывает ни на что (конец связанного списка). .

Точка входа в связанный список называется головой. Голова — это ссылка на первый узел в связанном списке. Последний узел в списке указывает на ноль. Если список пуст, заголовок является нулевой ссылкой.

Наглядно лучше всего просматривать связанные списки следующим образом;

Это также можно рассматривать как;

// Skeletal View of a Linked List

const list = {
  head: {
    data: 12,
    next: {
      data: 99,
      next: {
        data: 37,
        next: null
      }
    }
  }
}

//  Joshua Ajagbe

1. Музыкальный проигрыватель — песни в музыкальном проигрывателе связаны с предыдущей и следующей песнями. Таким образом, вы можете воспроизводить песни с начала или с конца списка.
2. Средство просмотра изображений — Предыдущее и следующее изображения связаны между собой, и к ним можно получить доступ с помощью кнопок «Далее» и «Предыдущее».
3. Предыдущая и следующая страница в веб-браузере. Мы можем получить доступ к предыдущему и следующему URL-адресу, найденному в веб-браузере, нажав кнопки «Назад» и «Далее», поскольку они связаны в виде связанного списка.

Существует три основных типа связанных списков: односвязный список, двусвязный список и циклический связанный список. Для целей этого обучения мы будем реализовывать односвязный список.

Как было сказано ранее, связанный список — это просто комбинация элементов (узлов), которые указывают друг на друга. Основной единицей связанного списка является узел. Узел содержит данные и указатель на следующий узел, реализованный следующим образом;

// A Singly Linked List Node
function SinglyLinkedListNode(data) {
  this.data = data;
  this.next = null; // the pointer to the next node...
}

//  Joshua Ajagbe

function SinglyLinkedList() {
  this.head = null;
  this.size = 0; // this helps keep track of the size of the linked list.
}

SinglyLinkedList.prototype.insert = function (data) {
  // checking if linked list is empty
  if(this.head === null){
    this.head = new SinglyLinkedListNode(data);
  } else {
    let temp = this.head;
    this.head = new SinglyLinkedListNode(data);
    this.head.next = temp;
  }
  this.size++; // updating the linked list size.
}

// Let's add method to check if the linked list is empty here. Bonus 
SinglyLinkedList.prototype.isEmpty = function () {
  return this.size === 0;
}

//  Joshua Ajagbe

Удаление узла из связанного списка осуществляется удалением его указателя. Это означает, что предыдущий узел, указывающий на узел (подлежащий удалению), будет вынужден пропустить узел (подлежащий удалению), следовательно, будет указывать на следующий узел.

SinglyLinkedList.prototype.remove = function (data) {
  let currentHead = this.head;
  if(currentHead.data === data) {
    this.head = currentHead.next;
    this.size--;
  } else {
    let prev = currentHead;
    while(currentHead.next) {
      if(currentHead.data === data){
        prev.next = currentHead.next;
        prev = currentHead;
        currentHead = currentHead.next
        this.size--;
        break;
      }
      prev = currentHead;
      currentHead = currentHead.next;
    }
  }
}


//  Joshua Ajagbe

Я надеюсь, что это помогло вам понять связанный список и его реализацию.

На всякий случай, если вам нужны дополнительные пояснения, вы можете связаться со мной в LinkedIn:https://www.linkedin.com/in/joshua-ajagbe/или напишите мне по адресу [email protected].

Приятного обучения