Что такое связанный список?
Связный список — это линейная структура данных, в которой элементы не хранятся в смежных ячейках памяти. Элементы в связанном списке связаны с помощью указателей, как показано на рисунке ниже:
Проще говоря, связанный список состоит из узлов, где каждый узел содержит поле данных и ссылку (ссылку) на следующий узел в списке.
Преимущество связанных списков
- Узлы можно легко удалять или добавлять из связанного списка без реорганизации всей структуры данных. Это одно из его преимуществ перед массивами.
Недостатки связанных списков
- Операции поиска в связанных списках выполняются медленно. В отличие от массивов, произвольный доступ к элементам данных не допускается. Доступ к узлам осуществляется последовательно, начиная с первого узла.
- Он использует больше памяти, чем массивы, из-за хранения указателей.
Типы связанных списков
Существует три типа связанных списков:
- Односвязные списки: каждый узел содержит только один указатель на следующий узел. Это то, о чем мы говорили до сих пор.
- Двусвязные списки. Каждый узел содержит два указателя: указатель на следующий узел и указатель на предыдущий узел.
- Циклические связанные списки. Циклические связанные списки — это вариант связанного списка, в котором последний узел указывает на первый узел или любой другой узел перед ним, образуя таким образом петлю.
Реализация 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 указывает количество узлов в списке.
Давайте реализуем каждую из этих функций:
- 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, мы перебираем индекс и добавляем элемент по этому индексу