Связанный список - это линейная структура данных. Структура данных - это термин в информатике, который используется для обозначения метода хранения, организации и управления данными. Некоторые структуры данных, с которыми вы, возможно, уже знакомы в JavaScript, - это массивы и объекты. Подобно различным алгоритмам, разные структуры данных имеют уникальные сильные и слабые стороны и варианты использования. Давайте посмотрим, как реализовать связанный список с помощью классов JavaScript ES6.
Что такое связанный список?
Связанный список - это структура данных, состоящая из узлов. Каждый узел имеет как минимум 2 компонента: данные, которые он содержит, и ссылку на следующий узел в списке (называемый указателем). Первый узел в связанном списке называется заголовком, последний узел в связанном списке называется хвостом. Есть несколько видов связанных списков. Односвязные списки содержат только указатель на узел после них, двусвязные списки содержат указатель на узел до и после них, а в списках с круговой связью хвост указывает на узел ранее в списке (обычно на голову), как показано ниже. узел, который создает петлю или круг.
Массивы против связанных списков
Массив занимает непрерывное пространство в памяти. То есть каждый элемент массива находится рядом с другими элементами этого массива в физической памяти. В массиве также выделяется одинаковый объем памяти для каждого из своих элементов. Из-за этого легко выполнить случайный поиск элемента в массиве. Если мы знаем место в памяти для первого элемента массива, а каждый элемент занимает одинаковое количество места и расположен рядом с предыдущими элементами, мы можем выяснить адрес памяти для любого из элементов в массиве. С другой стороны, узлы связанного списка не находятся рядом друг с другом в памяти, и именно поэтому у нас есть ссылка, указывающая на следующий узел в связанном списке. Однако из-за этого каждый узел должен занимать только то пространство, которое требуется для хранения его данных и указателя (ов) на другой узел (ы).
Плюсы и минусы
Плюсы
- Не тратит память. Как упоминалось ранее, каждый узел в связанном списке будет занимать только ту память, которая ему нужна для хранения своих данных и указателей.
- Простая вставка новых узлов. В массиве, когда вы добавляете элемент, вы должны сдвинуть каждый элемент, следующий за ним, чтобы они все еще оставались в непрерывной памяти. В связанном списке новый узел может располагаться везде, где есть свободное место в памяти, и вам просто нужно будет изменить указатели.
- Простое удаление узлов. Подобно вставке, при удалении узла из связанного списка все, что вам нужно сделать, это указать узлу перед ним, чтобы он указывал на узел после него. Тогда ни один из узлов не будет указывать на узел, который вы хотите удалить, и он больше не будет частью связанного списка.
- Динамический размер. В некоторых языках при инициализации массива необходимо явно указать, сколько элементов он будет содержать и какого типа эти элементы. В JavaScript этого делать не нужно, однако, когда массив становится слишком большим, чтобы уместиться в непрерывном пространстве памяти, каждый элемент необходимо скопировать в новое место, в котором достаточно места. Все это происходит за кулисами, поэтому о них легко не думать. Этого никогда не произойдет со связанным списком, поэтому вы можете продолжать добавлять узлы, пока имеется достаточно памяти для хранения их индивидуальных данных и указателей.
Минусы
- Каждый узел занимает больше памяти. Потому что мы должны хранить и данные, и указатель (и).
- Нет произвольного доступа. Единственный способ найти последующие узлы в связанном списке - следовать указателям.
- Проблемы с обратным перемещением. В односвязном списке очень сложно вернуться назад, так как есть только указатель на следующий узел. В двусвязном списке это проще, но дополнительный указатель требует больше памяти.
Кодирование односвязного списка в JavaScript
Первым шагом в кодировании связанного списка является создание класса ListNode.
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
Этот простой класс делает то же, что описано выше. Он хранит наши данные (которые могут быть строками, целыми числами, объектами, массивами или даже другими узлами) и имеет ссылку на следующий узел. Отсюда, в вашем терминале, вы можете попробовать это. Сделайте пару узлов так:
let node1 = new ListNode(1); let node2 = new ListNode(2); node1.next = node2;
Тогда, если бы вы проверили node1.next, вы бы увидели, что он возвращает node2. Вы можете продолжить этот процесс и фактически создать связанный список, просто делая это. Однако было бы неплохо инкапсулировать эту и многое другое в другом классе.
Так что именно этим мы и займемся. Сделаем наш LinkedList класс.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}
Каждый связанный список должен будет отслеживать свои head и size.
С этого момента остальные методы будут внутри нашего класса LinkedList.
Следующее, что нам понадобится, это возможность добавить новый узел в наш LinkedList.
add(data) {
let newNode = new ListNode(data);
if (this.head === null) {
this.head = newNode;
} else {
let currentNode = this.head;
while (!!currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
this.size++;
}
Метод add принимает данные нашего нового узла. Оттуда он инициализирует новый экземпляр ListNode. Мы проверяем, есть ли в нашем связанном списке головной узел, в противном случае мы назначаем наш новый узел заголовком связанного списка. В противном случае мы создаем цикл while для перебора связанного списка, начиная с узла head, пока не найдем узел, у которого нет указателя next. Как только мы находим этот узел, мы знаем, что достигли конца нашего односвязного списка, поэтому мы присваиваем наш newNode значению next, добавляя его в список (новый узел теперь является хвостом связанного списка). После всего этого мы увеличиваем size в нашем связанном списке.
Теперь мы можем добавить узел, следующее, что мы можем сделать, это получить узел.
getNodeAt(index) {
if (index < 0 || index > this.size - 1) {
return undefined;
} else {
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
Наши связанные списки будут проиндексированы 0. Если кто-то передаст отрицательное число или число, которое больше количества индексов в связанном списке (на один меньше нашего size), мы вернем undefined. В противном случае нам нужно перебирать связанный список, пока мы не дойдем до узла по желаемому индексу. Поскольку мы назначаем currentNode следующему узлу в списке, мы остановимся на 1 меньше нашего индекса. Как только мы выйдем из цикла while, нам просто нужно вернуть currentNode.
Теперь мы можем добавлять и извлекать узлы, пришло время выяснить, как их удалить. Сначала удалим по индексу.
removeFrom(index) {
if (index < 0 || index > this.size - 1) {
return undefined;
} else {
let currentNode = this.head;
if (index === 0) {
this.head = currentNode.next;
} else {
let previousNode;
for (let i = 0; i < index; i++) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
this.size--;
return currentNode.data;
}
}
Поэтому мы выполняем аналогичную проверку в начале нашего removeFrom метода, чтобы убедиться, что переданный индекс действителен. После этого мы назначаем currentNode головке, если index равно 0, мы знаем, что хотим удалить головной узел. Мы можем добиться этого, просто назначив заголовок нашего связанного списка узлу после него.
В противном случае нам нужно начать цикл по нашему связанному списку, отслеживая previousNode. Для каждого цикла в нашем связанном списке мы назначим previousNode старому currentNode и переназначим currentNode узлу после него. Когда мы находимся в нашем индексе, currentNode - это узел, который мы хотим удалить. Итак, что нам нужно сделать, так это сделать так, чтобы previousNode указывала на узел после currentNode. Итак, мы говорим previousNode указать на то, на что в данный момент указывает currentNode. Теперь ни один из узлов в нашем связанном списке не указывает на currentNode! Оттуда нам просто нужно уменьшить size.
Но что, если мы не знаем индекс узла, который хотим удалить? Давайте создадим метод удаления узла на основе данных, которые он хранит.
removeNode(data) {
let currentNode = this.head;
let previousNode;
while (!!currentNode) {
if (currentNode.data === data) {
if (previousNode) {
previousNode.next = currentNode.next;
} else {
this.head = currentNode.next;
}
this.size--;
return currentNode.data;
}
previousNode = currentNode;
currentNode = currentNode.next;
}
return undefined;
}
Как и раньше, нам нужно перебрать наш связанный список, начиная с головы. Нам также все еще нужно сохранить наш предыдущий узел. Наш while цикл проверяет, существует ли currentNode, поскольку, как только мы пройдем хвост, currentNode будет null. Поэтому на каждой итерации мы проверяем, совпадают ли данные, хранящиеся в currentNode, с данными узла, который мы хотим удалить. Если это так, мы проверяем, существует ли previousNode. Если это так, мы делаем то же самое, что и выше, и заставляем previousNode указывать на узел после currentNode. Если previousNode не определено, то мы знаем, что данные хранятся в головном узле, поэтому мы переназначаем заголовок следующему узлу, удаляя его из нашего связанного списка. После этого мы уменьшаем размер и возвращаемся, выходя из цикла while. Если мы пройдемся по всему связанному списку и не найдем узел, содержащий эти данные, мы вернем undefined.
Теперь мы можем добавлять, извлекать и удалять элементы. Нам нужно сделать так, чтобы мы могли вставить новый узел в наш связанный список, а не просто добавить его в конец.
insertAt(index, data) {
if (index < 0 || index > this.size - 1) {
return undefined;
} else {
let newNode = new ListNode(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
} else {
let currentNode = this.head;
let previousNode;
for (let i = 0; i < index; i++) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = newNode;
newNode.next = currentNode;
}
this.size++;
}
}
Мы проверяем, действителен ли наш индекс. Если это так, мы инициализируем новый узел. Если index равен 0, мы добавляем новый заголовок в наш список. Итак, мы назначаем следующий указатель нашего newNode текущему заголовку, а затем переназначаем заголовок связанного списка на newNode. В противном случае нам нужно перебрать наш связанный список. Подобно тому, как мы это делали бы при удалении узлов. Как только мы находим узел, предшествующий индексу, в который мы хотим вставить, и узел, который в настоящее время находится там, мы назначаем следующий указатель previousNode нашему newNode, а затем назначаем указатель нашего newNode currentNode (узел, который раньше находился в этом индексе ).
Наш следующий метод вернет индекс узла, содержащего некоторые данные.
indexOf(data) {
let currentNode = this.head;
let index = 0;
while (!!currentNode) {
if (currentNode.data === data) {
return index;
} else {
currentNode = currentNode.next;
index++;
}
}
return -1;
}
Мы просто перебираем наш связанный список, отслеживая индекс, если мы находим узел, содержащий данные, мы возвращаем этот индекс. Если в нашем связанном списке нет узла с этими данными, мы вернем -1. Это воспроизводит функциональные возможности встроенной indexOf функции JavaScript для строк или массивов.
Что, если мы хотим очистить наш связанный список? Что ж, процесс на самом деле прост.
clear() {
this.head = null;
this.size = 0;
}
Без ссылки на голову наш связанный список также теряет ссылки на остальные узлы, а затем мы просто сбрасываем наш размер на 0.
Эти методы предоставят базовую функциональность связанного списка. Конечно, вы можете добавить еще много методов, в зависимости от того, какие функции вам нужны. Мы можем добавлять, вставлять, удалять и находить все наши узлы, а также полностью очищать список.
В заключении
Связанные списки представляют собой простую структуру данных, однако привыкание к использованию указателей и последовательному перемещению может оказаться довольно сложной задачей. Весь код этого блога можно найти в этом репозитории GitHub. Сильные стороны связанных списков действительно связаны с его динамической памятью и простотой добавления и удаления узлов в начале и середине списка. Двусвязный список можно использовать, когда вам нужно часто переходить вперед и назад (например, при просмотре веб-страниц, отмене и повторении в редакторе текста / изображений или при перемещении по списку воспроизведения музыки). Понимание связанных списков также поможет понять другие структуры данных с указателями, такие как деревья и графы.
