Как разработчики, вся наша работа сосредоточена на данных и на том, как ими управлять и манипулировать ими. Методы, используемые для хранения, доступа и изменения данных, имеют большое влияние на эффективность системы в целом. Структуры данных - это не что иное, как способы хранения данных для эффективного использования. Связанный список - одна из таких структур данных. Это одна из наиболее распространенных структур данных и самая простая для понимания концепция взаимосвязанных узлов. В этой статье я попытаюсь объяснить основы связанных списков и попытаться представить их с помощью javascript. Прежде чем переходить к связанным спискам, давайте обсудим несколько основ.

Что такое структуры данных?

Цитата из Википедии: «структура данных - это формат организации, управления и хранения данных, обеспечивающий эффективный доступ и изменение. Точнее, структура данных - это набор значений данных, взаимосвязей между ними, а также функций или операций, которые могут быть применены к данным ». Они разработаны таким образом, чтобы упростить данные и повысить эффективность приложения.

Некоторые из обычно используемых структур данных представляют собой массивы, связанные списки, стеки, очереди и хеш-таблицы. Массивы - это самые простые структуры данных. В языках низкого уровня, таких как C, массивам назначаются непрерывные ячейки памяти, и их размер должен быть заранее определен, т.е. они статичны. Здесь выделяются связанные списки.

Что такое связанные списки?

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

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

  • Они динамические, т.е. память распределяется по мере необходимости.
  • Вставлять и удалять элементы проще, чем массивы.
  • Легко выполнять стеки и очереди со связанными списками.

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

  • Для хранения ссылок требуется дополнительное пространство памяти.
  • Доступ к элементам только последовательный.
  • Обратное перемещение затруднено в связанных списках. (не так много в двусвязных списках)

Как программист javascript, связанные списки ничем не отличаются от массивов, которые мы используем. Массивы, которые мы используем в javascript, также являются динамическими. Они обеспечивают все операции, предоставляемые связанными списками. Почему же тогда, как вы можете подумать, нам нужно изучать связанные списки? Что ж, связанные списки - хороший способ понять, как реализованы базовые структуры данных. Глубокое понимание того, как все работает под капотом, упростило бы нам разработку более эффективного кода, а также преуспевало бы на собеседованиях! Да, интервью. Структуры данных - важная тема, обсуждаемая в интервью. Поищите на любом веб-сайте вопросы о практике собеседования, и вы найдете большинство вопросов о структурах данных и алгоритмах. Никогда не повредит делать добро на собеседовании, а?

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

Принципы работы связанного списка:

Существуют разные типы связанных списков, такие как простой связанный список, двусвязные списки и круговые связанные списки. Сегодня мы просто попробуем разобраться в простом связном списке. Надеюсь, в будущем я напишу несколько более подробных сообщений о других типах. А пока просто взгляните на представление двух других типов связанных списков.

Я попытаюсь объяснить связанные списки на примерах в javascript. Как я уже упоминал, связанный список - это набор узлов. Узлы, в свою очередь, содержат поле данных и ссылку на следующий узел. В javascript мы бы создали узел следующим образом:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Теперь это просто элемент связанного списка. Весь список состоит из ссылки на заголовок или начало связанного списка. Сама голова - это узел, содержащий первый элемент данных. Простая реализация связного списка не требует ничего, кроме заголовка списка. Чтобы просмотреть весь список, вы просто начинаете просматривать следующие ссылки, пока следующая ссылка не станет нулевой, что будет концом списка. Я просто добавлю размер элемента, чтобы отслеживать размер списка, чтобы нам не приходилось просматривать весь список каждый раз, когда нам нужно запрашивать его размер. Итак, в javascript мы бы реализовали что-то вроде этого:

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
}
linkedList = new LinkedList();

Это создает пустой связанный список с нулевым заголовком и размером 0.

Мы добавляем методы в класс LinkedList для вставки, удаления, добавления или просто поиска элемента.

Распечатать элементы связанного списка

Итак, давайте начнем с попытки распечатать элементы списка. Итак, основное действие, которое нам нужно сделать для этого, будет:

  1. Начните с головы и проверьте, пуст ли список.
  2. Если пусто, можно вывести сообщение о пустом списке.
  3. В противном случае просматривайте список по одному узлу за раз, используя ссылку на следующий узел и распечатывая данные в каждом узле по пути.

Моя реализация выглядит примерно так:

printList() {
  if (!this.head) {
    console.log("Empty List");
  }
  let currentNode = this.head;
  while (currentNode) {
    console.log(currentNode.data);
    currentNode = currentNode.next;
  }
}

Напоминаем: это метод в классе Linked List.

Итак, что произойдет, если я создам пустой массив, как показано ниже, и попытаюсь его распечатать?

linkedList = new LinkedList();
console.log("**************");
linkedList.printList();

Итак, мы получили ожидаемое выходное сообщение в виде пустого списка.

Добавление элементов в связанный список

Так что сейчас мы мало что можем сделать с нашим списком, не так ли? Итак, как насчет того, чтобы позволить нашему классу добавлять новые элементы в конец списка. Как мы это делаем?

  1. Нам нужно проверить, пуст ли список. В таком случае мы создаем новый узел и делаем его головой.
  2. Если список не пуст, мы просматриваем список, пока не дойдем до конца списка.
  3. Создайте новый узел и добавьте его в конец списка.
  4. Увеличьте размер списка на 1 по мере добавления нового элемента в список.

Что-то вроде этого:

// Method to add an element to the end of the list
appendElement(data) {
  if (this.head) {
    let currentNode = this.head;
    // Traverse the list till a next node exists
    while (currentNode.next) {
      currentNode = currentNode.next;
    }
    // Add the new node to the end of the list
    currentNode.next = new Node(data);
  }
  if (!this.head) {
    this.head = new Node(data);
  }
  this.size++;
}

Более эффективной реализацией списка может быть поддержка хвостового узла вместе с головным узлом, который отслеживает последний элемент списка. Но пока будем простыми. Мы добавляем к классу метод appendElement, добавляем несколько элементов и распечатываем список. Итак, давайте проверим это.

linkedList = new LinkedList();
console.log("**************");
linkedList.printList();
linkedList.appendElement(10);
console.log("**************");
linkedList.printList();
linkedList.appendElement(4);
console.log("**************");
linkedList.printList();

И получаем такой вывод:

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

Найдите индекс элемента в списке

Теперь попробуем найти элемент в списке. Это требует линейного обхода, пока элемент не будет найден. Давайте реализуем метод indexOf внутри класса LinkedList, чтобы он оставался как ссылки на массивы с использованием индексов. Для этого нам необходимо:

  1. Перемещайтесь по списку линейно.
  2. Проверяем, совпадают ли данные узла со значением, которое мы ищем.
  3. Возвращает счетчик из головы, в которой найдено значение.
indexOf(value) {
  let current = this.head;
  let count = 0;
  while (current) {
    if (current.data === value) {
      return count;
    }
    count++;
    current = current.next;
  }
  
  return -1;
}

Проверить наш код просто. Нам нужно добавить несколько элементов в список и найти в списке индекс долины.

linkedList = new LinkedList();
linkedList.appendElement(10);
linkedList.appendElement(7);
linkedList.appendElement(5);
linkedList.appendElement(3);
linkedList.appendElement(1);
console.log("Original List");
linkedList.printList();
console.log("**************");
console.log("Index of 5 in the list is ", linkedList.indexOf(5));

Мы получаем результат ниже:

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

Вставить элемент в список по заданному индексу

Теперь давайте попробуем вставить узел где-нибудь в середине связанного списка. Это немного более сложная операция. Давайте сначала разберемся, как мы это сделаем.

Здесь у нас есть связанный список со значениями 10, 7, 3 и 1. Мы хотим вставить новый узел, скажем, с данными 5 в индекс 2 (то есть после узла с данными 7). Итак, наконец, мы хотим, чтобы следующая из 7 ссылалась на 5, а следующая из 5 - на ссылку 3 и удалила связь между 7 и 3. Мы проделаем это, выполнив следующие шаги:

  1. Переход к 7.
  2. Получите временную ссылку на узел 3, чтобы мы не потеряли к нему доступ при перемещении 7. к ссылке 5.
  3. Сделайте так, чтобы следующий узел 7 ссылался на 5, а следующий узел 5 на узел 3. Теперь список завершен. Но не забывайте увеличивать размер!

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

insertDataAtIndex(value, index) {
  if (index >= this.size) {
    return false;
  }
  let currentNode = this.head;
  let newNode = new Node(value);
  let count = 0;
  while(currentNode && count < index - 1) {
    currentNode = currentNode.next;
    count++;
  }
  let temp = currentNode.next; //save reference to next node
  currentNode.next = newNode;
  newNode.next = temp;
  this.size++;
  return true;
}

Давайте создадим список в примере и попробуем вставить значение.

linkedList = new LinkedList();
linkedList.appendElement(10);
linkedList.appendElement(7);
linkedList.appendElement(3);
linkedList.appendElement(1);
console.log("Original List");
linkedList.printList();
console.log("**************");
// Insert value 5 at index 2
linkedList.insertDataAtIndex(5,2);
console.log("List with value inserted");
linkedList.printList();

Это дает результат:

Как мы видим, значение было вставлено там, где мы хотели его вставить.

Удалить узел по индексу в списке

Последняя операция, которую мы рассмотрим, - это удаление элемента по индексу. Удаление в javascript проще.

  1. Мы перейдем к позиции индекса перед индексом, который хотим удалить. Допустим, мы хотим удалить индекс 2. Мы перейдем к индексу 1.
  2. Сделайте указатель на следующий из следующего (пропуская элемент между ними)
  3. Уменьшите размер связанного списка на 1.

Здесь javascript позаботится об удалении элемента без ссылки. Но на таком языке, как C, нам пришлось бы явно удалить объект, иначе это привело бы к фрагментации.

Итак, теперь мы реализуем метод deleteElementAtIndex

deleteElementAtIndex(index) {
  if (index >= this.size || !this.head) {
    return;
  }
  let currentNode = this.head;
  let count = 0;
  while (currentNode && count < index - 1) {
    currentNode = currentNode.next;
    count++;
  }
  currentNode.next = currentNode.next.next;
  this.size--;
}

Теперь, используя значения, которые мы взяли в приведенном выше примере, и протестируем:

linkedList = new LinkedList();
linkedList.appendElement(10);
linkedList.appendElement(7);
linkedList.appendElement(5);
linkedList.appendElement(3);
linkedList.appendElement(1);
console.log("Original List");
linkedList.printList();
console.log("**************");
linkedList.deleteElementAtIndex(2);
console.log("List with value deeleted");
linkedList.printList();

Мы видим, что элемент с индексом 2 был удален:

До сих пор мы рассмотрели основные операции со связанным списком. Подобные операции могут использоваться для реализации стековых (LIFO - Last In First Out) или очередных (FIFO - First In First Out) структур данных с использованием связанного списка.

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