Многие новые разработчики приходят к программированию через 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

Здесь у нас есть список, который будет постоянно меняться.

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

За кулисами у массивов есть определенное количество разрешенных элементов. Добавление или удаление элементов может быть довольно дорогостоящим для компьютера. В связанном списке добавление или удаление элементов выполняется очень дешево и быстро.

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

Нет произвольного доступа. Как видно из кода, списки доступны только по порядку. Это означает, что поиск, сортировка и другие подобные операции в списке очень дороги.

Задавать вопросы

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

Что бы вы хотели узнать дальше?