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

Связный список — это линейная структура данных, в которой элементы не хранятся в смежных ячейках памяти. Элементы в связанном списке связаны с помощью указателей, как показано на рисунке ниже:

Проще говоря, связанный список состоит из узлов, где каждый узел содержит поле данных и ссылку (ссылку) на следующий узел в списке.

Преимущество связанных списков

  • Узлы можно легко удалять или добавлять из связанного списка без реорганизации всей структуры данных. Это одно из его преимуществ перед массивами.

Недостатки связанных списков

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

Типы связанных списков

Существует три типа связанных списков:

  • Односвязные списки: каждый узел содержит только один указатель на следующий узел. Это то, о чем мы говорили до сих пор.
  • Двусвязные списки. Каждый узел содержит два указателя: указатель на следующий узел и указатель на предыдущий узел.
  • Циклические связанные списки. Циклические связанные списки — это вариант связанного списка, в котором последний узел указывает на первый узел или любой другой узел перед ним, образуя таким образом петлю.

Реализация LinkedList в Javascript

class Node {

constructor(element)

{

this.element = element;

this.next = null

}

}

Как и в приведенном выше коде, мы определяем классNode, имеющий два свойства: element и next. Element содержит данные узла, а next содержит указатель на следующий узел, который инициализируется нулевым значением.

Теперь давайте посмотрим на реализацию класса Linked List:

class LinkedList {

constructor()

{

this.head = null;

this.size = 0;

}

}

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

  1. add(element) — добавляет элемент в конец списка.

add(element)
{
let node = new Node(element);

пусть ток;

if (this.head == null)
this.head = node;
else {
current = this.head;

в то время как (текущий.следующий) {
текущий = текущий.следующий;
}

current.next = node;
}
this.size++;
}

Чтобы добавить элемент в конец списка, мы учитываем следующее:

  • Если список пуст, добавьте элемент, и он будет головным.
  • Если список не пуст, выполните итерацию до конца списка и добавьте элемент в конец списка.

2. insertAt(element, index) — вставляет элемент по заданному индексу в список.

insertAt(element, index)
{
if (index ‹ 0 || index › this.size)
return console.log("Пожалуйста, введите действительный индекс.");
> else {
let node = new Node(element);
let curr, prev;

текущий = this.head;

if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
пусть = 0;

while (it ‹ index) {
it++;
prev = curr;
curr = curr.next;
}

node.next = curr;
prev.next = node;
}
this.size++;
}
}

Чтобы добавить элемент по заданному индексу списка, мы рассмотрим три условия следующим образом:

  • если индекс равен нулю, мы добавляем элемент в начало списка и делаем его головным
  • Если индекс является последней позицией списка, мы добавляем элемент в конец списка.
  • если индекс находится между 0 или size — 1, мы перебираем индекс и добавляем элемент по этому индексу