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

Зачем вам нужна эта структура данных?

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

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

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

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

[2] Двойной связанный список

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

Каждый элемент (также называемый узлом) списка состоит из двух элементов — данных и ссылки на следующий узел. Последний узел имеет ссылку на ноль. Точка входа в связанный список называется головой списка.

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

Двойной связанный список

Двусвязный список имеет две ссылки: одну на следующий узел, а другую на предыдущий узел.

Связанный список в JavaScript

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

В классе LinkedListNode свойство data содержит значение, которое должен хранить элемент связанного списка, а свойство next является указателем на следующий элемент в списке. Следующее свойство начинается со значения null, потому что вы еще не знаете следующий узел. Затем вы можете создать связанный список, используя класс LinkedListNode следующим образом:

Создание первого узла

Const head = new LinkedListNode(10);

Добавление второго узла

head.next = new LinkedListNode(99);

Добавление третьего узла

head.next.next = new LinkedListNode(45);

Как просматривать данные

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

Этот код использует переменную current в качестве указателя, перемещающегося по связанному списку. Текущая переменная инициализируется в начале списка, и цикл while продолжается до тех пор, пока текущая не станет нулевой. Внутри цикла печатается значение, хранящееся в текущем узле, а затем следующий указатель переходит к следующему узлу.

В JavaScript требуется создать класс для инкапсуляции этой функциональности.

Например:

const head = symbol(“head”);
class LinkedList {
 constructor(){
  this[head] = null;
 }
}

Как добавить новые данные в связанный список?

Чтобы добавить элемент в связанный список, необходимо просмотреть связанный список и найти правильное место для добавления данных.

Удаление данных

При удалении данных нам нужно убедиться, что все указатели «следующие» остаются нетронутыми после удаления узла.

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

Вот код!

Заключительные мысли!

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