Многие новые разработчики приходят к программированию через Javascript, потому что он повсеместно распространен в сети и может использоваться практически для чего угодно. Как язык сценариев высокого уровня, он имеет множество встроенных функций и доступных библиотек, что означает, что многим разработчикам не нужно погружаться в специальные структуры данных.
Это также отправная точка для многих разработчиков-самоучок, которые не знакомы с такими темами информатики, как структуры данных. Это включало меня.
Зачем заново внедрять связанные списки?
Связанные списки - одна из простейших структур данных, и во многих расширенных структурах данных используются аналогичные методы, но более сложное поведение. Это самая легкая отправная точка.
В этом посте мы собираемся воссоздать односвязные и двусвязные списки. Мы собираемся начать с очень простой реализации, а затем постепенно улучшать ее, чтобы было действительно ясно, что мы делаем и почему.
Связанный список против массива
Примечание: связанные списки похожи на массивы, но не то же самое. Мы рассмотрим некоторые различия, но в большинстве случаев ключевым является скорость вставки / удаления по сравнению с чтением с произвольным доступом. Есть также несколько интересных вещей, которые вы можете сделать со связанными списками, которые массивы не делают так элегантно.
Единый связанный список - прототип
Вот визуальное представление о том, что мы делаем. Это фрагмент данных, объединенный с указателем на следующий элемент данных.
Мы собираемся начать как можно проще с базового прототипа, который позволит нам связать один элемент с другим в одном направлении.
Прототип односвязного списка:
const link3 = { data: "how data structures work!", next: null } const link2 = { data: "is it to know ", next: link3 } const link1 = { data: "How sweet ", next: link2 } let current = link1; let output = ""; while (current) { output += current.data; current = current.next; } console.log(output);
Если вы запустите этот код, вы увидите текст «Как приятно знать, как работают структуры данных!».
Ограничения
Единый связанный список имеет довольно очевидное ограничение: назад не идти! В то же время требуется очень мало памяти. Также легко вставлять элементы в конце.
Я также хочу выделить еще одну проблему: последовательность. Поскольку это язык с нестатической типизацией, нет гарантии, что каждый элемент в списке является другим элементом списка. Но это отдельный вопрос, который мы рассмотрим позже.
Двойной связанный список
Список с двойной связью аналогичен, но теперь каждый элемент имеет другое свойство «prev».
const link3 = { data: "how data structures work!", next: null, prev: null } const link2 = { data: "is it to know ", next: null, prev: null } const link1 = { data: "How sweet ", next: null, prev: null } link1.next = link2; link2.next = link3; link2.prev = link1; link3.prev = link2; let output = ""; let current = link1; while (current) { output += current.data; current = current.next; } console.log(output); let outputBack = ""; current = link3; while (current) { outputBack += current.data; current = current.prev; } console.log(outputBack);
Теперь можно перейти от ссылки, чтобы связать в обоих направлениях. И хотя это простейшая возможная реализация структуры в виде списка, она явно не масштабируется.
На данный момент наш список отстой. Добавление элементов - это боль, и мы не можем запросить их длину или что-то еще. У нас есть набор элементов, которые ссылаются друг на друга, но у нас пока нет согласованной и масштабируемой структуры данных. Давай исправим.
Преобразование прототипа в реальную структуру
Теперь у нас есть способ двигаться вперед и назад по нашему списку, но наш прототип все еще очень ограничен. Нет простого способа добавлять, удалять или сортировать элементы в нашем списке.
Как мы можем это улучшить? На данный момент давайте поставим себе несколько основных целей:
- Получите первый и последний элементы списка.
- Получить размер списка
- Добавить элементы в список.
Они хорошо выглядят. Во-первых, мы должны формализовать наши элементы, чтобы обеспечить единообразие. Каждый элемент списка будет называться «узлом» и может быть представлен так:
class Node { constructor(data, next = null, prev = null) { this.data = data; this.next = next; this.prev = prev; } }
Далее нам понадобится контейнер - сама абстракция списка.
class List { constructor() { this.length = 0; this.head = null; this.tail = null; } append(data) { const node = new Node(data); this.length++; if(!this.head) { this.head = node; this.tail = node; return this; } this.tail.next = node; node.prev = this.tail; this.tail = node; return this; } }
Прогресс!
Теперь мы чего-то добиваемся. Хотя это все еще ограничено, это структура данных, которую вы действительно можете использовать.
Вы можете добавить гораздо больше функций (добавление в начало списка по сравнению с его нижней частью, удаление и т. Д.). Для этого есть много источников.
Особые случаи
Связанные списки для большинства людей по-прежнему очень похожи на массивы. Концептуально они похожи тем, что представляют собой одномерные наборы данных. Однако их тактико-технические характеристики совершенно разные. Со связанными списками вы не можете напрямую получить доступ к элементу в середине. Вы можете перейти только к следующему или предыдущему элементу. Вставить элемент в связанный список проще и быстрее, чем в массив.
Связанные списки также допускают особую структуру. Например, есть особый случай, зацикленный список, о котором вам следует знать.
Проверь это:
const list = new List(); list.append("First"); list.append("Second"); list.append("Third"); list.tail.next = list.head; let current = list.head; while (current.next) { console.log(current.data); current = current.next; } // will loop forever
Здесь у нас есть список, который будет постоянно меняться.
Преимущества связанных списков:
За кулисами у массивов есть определенное количество разрешенных элементов. Добавление или удаление элементов может быть довольно дорогостоящим для компьютера. В связанном списке добавление или удаление элементов выполняется очень дешево и быстро.
Недостатки связанных списков
Нет произвольного доступа. Как видно из кода, списки доступны только по порядку. Это означает, что поиск, сортировка и другие подобные операции в списке очень дороги.
Задавать вопросы
Надеюсь, это будет полезно. Я хотел бы знать, есть ли у вас вопросы об этой структуре, о том, для чего ее можно использовать, о чем угодно.
Что бы вы хотели узнать дальше?