Все, что вам нужно знать о связанных списках: структура данных с помощью JavaScript

Что такое связанный список и как реализовать базовый связанный список в JavaScript?

Изначально это сообщение было опубликовано по адресу:
https://raulmelo.dev/blog/data-structure-with-javascript-linked-list

Привет, разработчики.

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

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

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

Помнить:

Знание - сила и никогда не бывает бесполезным.

О списках

Массивы - один из наиболее эффективных способов хранения коллекций данных, таких как, например, список друзей в Instagram.

В JavaScript, когда мы хотим создать список чего-либо, все, что нам нужно, - это очень простая открывающая / закрывающая квадратная скобка ([]) и вставлять в нее столько элементов, сколько хотите.

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

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

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

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

В JavaScript мы не сильно страдаем от этого, потому что язык был разработан таким образом, и у нас также есть собственные методы массива (я полагаю, очень хорошо оптимизированные), которые удаляют или добавляют элемент и восстанавливают список, как метод Array.prototype.splice().

const months = ['Jan', 'March', 'April', 'June'];
// insert exactly in the index one (1, 0) the string `Feb`
months.splice(1, 0, 'Feb');
console.log(months); // Array ["Jan", "Feb", "March", "April", "June"]
// removes everything from the index 3 til the last el ("April" and "June")
months.splice(3, months.length)
console.log(months); // ["Jan", "Feb", "March"]

Связанный список: концепция

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

У каждого узла будет 2 свойства:

• element: данные, которые мы хотим сохранить в нашем списке;
• next: ссылка на другой узел или значение null (несуществующий следующий узел).

Возможно, лучший способ визуализировать это - представить поезд.

В поезде у нас всегда есть «голова», и оттуда она соединяет первый «вагон», затем второй «вагон» соединяется с первым до конца поезда.

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

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

Другими словами, связанные списки предназначены для создания и изменения соединений между узлами.

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

Связанный список: реализация

Перед какой-либо реализацией давайте взглянем на API, который нам понадобится для такого списка:

• .append(element) - метод добавления нового элемента в конец списка;
• .indexOf(element) - метод, используемый, чтобы узнать, где в индексе был добавлен наш элемент;
• .insertAt(position, element) - метод, используемый для добавления элемента в определенную позицию;
• .remove(element) - метод удаления элемента из списка;
• .removeAt(position) - метод, используемый для удаления элемента в определенной позиции;
• .toString() - метод, используемый для обзора нашего списка.

И снова, вместо того, чтобы использовать классы / прототип JS, я собираюсь использовать мою любимую фабрику шаблонов с некоторыми заполнителями для нашего API:

function LinkedListFactory() {
  return {
    append,
    indexOf,
    insertAt,
    remove,
    removeAt,
    toString,
  };
  function append(element) {}
  function indexOf(element) {}
  function insertAt(position, element) {}
  function remove(element) {}
  function removeAt(position) {}
  function toString() {}
}

«Глобальные» переменные

Перед реализацией методов нам нужно создать 2 переменные, которые будут использоваться почти во всех методах:

• head - переменная для хранения нашего самого первого элемента, с которого все начнется. Он начнется со значения null;
• length - управляющая переменная для удобного хранения размера списка. Он начнется со значения 0.

function LinkedListFactory() {
  let head = null;
  let length = 0;
  return {
    append,
    indexOf,
    insertAt,
    remove,
    removeAt,
    toString,
  };
  function append(element) {}
  function indexOf(element) {}
  function insertAt(position, element) {}
  function remove(element) {}
  function removeAt(position) {}
  function toString() {}
}

.append (элемент)

В методе append нам сначала нужно создать внутреннюю базовую структуру, которую мы можем назвать «узлом».

Узел - это простой объект, который будет содержать элемент, который мы добавляем в список, и следующий элемент (саму ссылку).

Поскольку добавление всегда будет добавлять элемент в конец списка, next всегда будет null:

function append(element) {
  const node = {
    element,
    next: null
  }
}

Первый сценарий - когда наш список пуст, или когда head равно null. В этом случае мы назначим наш вновь созданный узел на голову:

function append(element) {
  const node = {
    element,
    next: null,
  };
  if (head === null) {
    head = node;
  }
}

Теперь мы должны рассмотреть другие случаи (если не случай главного или предпоследнего узла).

Поскольку мы хотим добавить элемент в конец нашего списка, мы должны перебирать все узлы, пока .next не станет равным null.

function append(element) {
  const node = {
    element,
    next: null,
  };
  if (head === null) {
    head = node;
  } else {
    let currentNode = head;
    while (currentNode.next !== null) {
      currentNode = currentNode.next;
    }
  }
}

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

function append(element) {
  const node = {
    element,
    next: null,
  };
  if (head === null) {
    head = node;
  } else {
    let currentNode = head;
    while (currentNode.next !== null) {
      currentNode = currentNode.next;
    }
    currentNode.next = node;
  }
}

Наконец, нам понадобится в обоих случаях (заголовок или нет) увеличить на 1 размер нашего списка (length), поэтому важно выходить за рамки условия.

function append(element) {
  const node = {
    element,
    next: null,
  };
  if (head === null) {
    head = node;
  } else {
    let currentNode = head;
    while (currentNode.next !== null) {
      currentNode = currentNode.next;
    }
    currentNode.next = node;
  }
  length++;
}

.indexOf (элемент)

Этот метод предназначен для поиска места в нашем списке данного элемента.

Во-первых, нам понадобятся две переменные контроллера: nodeIndex и currentElement. Первое будет использоваться как возвращаемое значение, но также для того, чтобы знать, где мы находимся на итерации, а второе - для сравнения, если это тот элемент, который мы ищем:

function indexOf(element) {
  let nodeIndex = 0;
  let currentNode = head;
}

Помните, я говорил вам, что head может быть null или .next последнего узла будет null? Мы будем использовать это условие для обхода всех узлов.

function indexOf(element) {
  let nodeIndex = 0;
  let currentNode = head;
  while (currentNode) {
    if (element === currentNode.element) {
      return nodeIndex;
    }
    nodeIndex++;
    currentNode = currentNode.next;
  }
}

Теперь, пока currentNode не станет null, мы сначала проверим, является ли элемент тем, который мы ищем. Если это так, мы можем сразу вернуть значение nodeIndex.

Если нет, то нам нужно будет увеличить 1 до nodeIndex и присвоить currentNode currentNode.next, или, другими словами, просто перейти к следующему узлу, чтобы повторить сравнение.

Наконец, если мы не можем найти элемент, который ищет пользователь, мы должны указать, что не смогли.

Традиционно для подобных случаев такие методы возвращают -1, но ничто не мешает нам вернуть другое значение, например null:

function indexOf(element) {
  let nodeIndex = 0;
  let currentNode = head;
  while (currentNode) {
    if (element === currentNode.element) {
      return nodeIndex;
    }
    nodeIndex++;
    currentNode = currentNode.next;
  }
  return -1
}

.insertAt (позиция, элемент)

В этой операции мы проделаем ту же операцию, что и для indexOf (управление индексом), плюс нам нужно будет настроить соединения узлов.

Представьте себе следующий сценарий: у нас есть 4 связанных узла в нашем списке, и мы хотим вставить новый элемент в позицию 2 (вторая позиция, потому что это индекс, отсчитываемый от 0).

В основном нам потребуются:

1. Прокрутите узлы;
2. Найдите, кто находится в позиции 2;
3. сделайте этот узел .next указывающим на элемент, который мы вставляем
4. сделать так, чтобы наш новый узел .next указывал на элемент, который мы только что нашли .next

Это может показаться немного запутанным, но я расскажу вам о самой реализации шаг за шагом.

Первая проверка, которую нам нужно сделать, - это то, существует ли позиция, которую пользователь просит добавить, в нашем списке. Нам нужно убедиться, что если мы не добавляем элемент в позицию 4, если у нас есть только 1 элемент в нашем списке:

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  
  if(!isPositionInTheRange){
    return false
  }
}

Совет: переменная, содержащая эту логику, является просто семантическим способом описания (на английском языке) условия.

Как и в других методах, нам нужно будет перебрать наш список, чтобы увидеть, куда нам нужно добавить этот элемент. Это означает, что нам нужно создать переменную контроллера и наш узел:

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  
  if(!isPositionInTheRange){
    return false
  }
  
  // Our brand new node
  const node = {
    element,
    next: null
  }
  
  // Controller to iterate over the list
  let currentNode = head;
}

В нашем первом случае пользователь хочет добавить элемент в первую позицию (заголовок). Все, что нам нужно сделать, это сказать, что новый узел .next будет текущим элементом, а голова теперь будет новым узлом:

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  if (!isPositionInTheRange) {
    return false;
  }
  const node = {
    element,
    next: null,
  };
  let currentNode = head;
  const isHeadPosition = position === 0;
  if (isHeadPosition) {
    // Assign currentNode (head) to `node.next`
    node.next = currentNode;
    // Replace the current head with this node
    head = node;
  } else {
  }
}

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

Во-первых, нам понадобятся 2 переменные контроллера, index (для итерации на основе этого) и previousNode (для повторного создания ссылок, когда мы найдем позицию):

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  if (!isPositionInTheRange) {
    return false;
  }
  const node = {
    element,
    next: null,
  };
  let currentNode = head;
  const isHeadPosition = position === 0;
  if (isHeadPosition) {    
    node.next = currentNode;
    head = node;
  } else {
    let previousNode = null;
    let index = 0;
  }
}

Затем мы будем повторять, используя index. Пока индекс меньше желаемой позиции, мы обновим наши контроллеры previousNode и currentNode:

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  if (!isPositionInTheRange) {
    return false;
  }
  const node = {
    element,
    next: null,
  };
  let currentNode = head;
  const isHeadPosition = position === 0;
  if (isHeadPosition) {    
    node.next = currentNode;
    head = node;
  } else {
    let previousNode = null;
    let index = 0;
    
    while (index++ < position){
      previousNode = currentNode;
      currentNode = currentNode.next;
    }
  }
}

Помните: index ++ сначала оценивает число, а только потом увеличивает на единицу.

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

Когда мы достигнем этого, все, что нам нужно сделать, это заново установить связи между previousNode ‹-› new node ‹-› currentNode:

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  if (!isPositionInTheRange) {
    return false;
  }
  const node = {
    element,
    next: null,
  };
  let currentNode = head;
  const isHeadPosition = position === 0;
  if (isHeadPosition) {    
    node.next = currentNode;
    head = node;
  } else {
    let previousNode = null;
    let index = 0;
    
    while (index++ < position){
      previousNode = currentNode;
      currentNode = currentNode.next;
    }
    
    previousNode.next = node;
    node.next = currentNode;
  }
}

Наконец, нам нужно добавить +1 в длину нашего списка, независимо от того, где в списке он был вставлен, и вернуть true, чтобы проинформировать пользователя об успешном завершении операции:

function insertAt(position, element) {
  const isPositionInTheRange = position > -1 && position <= length;
  if (!isPositionInTheRange) {
    return false;
  }
  const node = {
    element,
    next: null,
  };
  let currentNode = head;
  const isHeadPosition = position === 0;
  if (isHeadPosition) {    
    node.next = currentNode;
    head = node;
  } else {
    let previousNode = null;
    let index = 0;
    
    while (index++ < position){
      previousNode = currentNode;
      currentNode = currentNode.next;
    }
    
    previousNode.next = node;
    node.next = currentNode;
  }
  
  length++;
  return true;
}

.removeAt (позиция)

Метод removeAt имеет очень похожую реализацию, которую мы только что видели в insertAt, нам нужно:

1. перебирать список;
2. найти соответствующий элемент в этой позиции;
3. соединить предыдущий элемент со следующим;
4. уменьшить размер списка

Начиная, еще раз давайте сначала проверим, содержит ли позиция запроса элемент:

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
}

Затем нам нужно создать переменную контроллера currentNode для итерации:

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
  
  let currentNode = head;
}

Снова у нас будет 2 ситуации: голова или не голова. Если есть head, все, что нам нужно сделать, это переназначить head, чтобы он был currentNode (в данном случае сам элемент head) его значению .next:

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
  
  let currentNode = head;
  
  if(position === 0){
    head = currentNode.next;
  }
}

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

Теперь нам нужно удалить элементы, которые не являются головой. Для этого давайте создадим две другие переменные контроллера, index и previousNode:

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
  
  let currentNode = head;
  
  if(position === 0){
    head = currentNode.next;
  } else {
    let index = 0;
    let previousNode = null;
  }
}

И еще раз, перебираем все элементы, пока не достигнем желаемой позиции:

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
  
  let currentNode = head;
  
  if(position === 0){
    head = currentNode.next;
  } else {
    let index = 0;
    let previousNode = null;
    
    while(index++ < position){
      previousNode = currentNode;
      currentNode = currentNode.next
    }
  }
}

Теперь мы воссоздадим ссылки на узлы, соединив previousNode.next с currentNode.next:

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
  
  let currentNode = head;
  
  if(position === 0){
    head = currentNode.next;
  } else {
    let index = 0;
    let previousNode = null;
    
    while(index++ < position){
      previousNode = currentNode;
      currentNode = currentNode.next
    }
    
    previousNode.next = currentNode.next;
    
  }
}

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

function removeAt(position){
  const isPositionInTheRange = position > -1 && position < length;
  
  if(!isPositionInTheRange){
    return null
  }
  
  let currentNode = head;
  
  if(position === 0){
    head = currentNode.next;
  } else {
    let index = 0;
    let previousNode = null;
    
    while(index++ < position){
      previousNode = currentNode;
      currentNode = currentNode.next
    }
    
    previousNode.next = currentNode.next;
  }
  
  length--;
  return currentNode.element;
}

.remove (элемент)

Этот метод будет довольно просто реализовать. Это потому, что у нас уже есть метод для поиска индекса элемента (indexOf), а также есть метод для удаления элемента из позиции (removeAt):

function remove(element){
  const elementIndex = indexOf(element);
  return removeAt(elementIndex);
}

.нанизывать()

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

И снова нам нужно будет пройти по всем узлам и объединить значение элемента в строку:

function toString() {
  let result = "";
  let current = head;
  while (current) {
    result += `${current.element}${current.next ? ", " : ""}`;
    current = current.next;
  }
  return result;
}

Обс .: Работает только для примитивных значений. Если вы хотите поддерживать такие элементы, как objects, functions и т. Д., Вам необходимо улучшить конкатенацию и синтаксический анализ данных.

Конечный результат

function LinkedListFactory() {
  let head = null;
  let length = 0;
  return {
    append,
    indexOf,
    insertAt,
    remove,
    removeAt,
    toString,
  };
  function append(element) {
    const node = {
      element,
      next: null,
    };
    if (head === null) {
      head = node
    } else {
      let currentNode = head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }
    length++;
  }
  function indexOf(element) {
    let nodeIndex = 0;
    let currentNode = head;
    while (currentNode) {
      if (element === currentNode.element) {
        return nodeIndex;
      }
      nodeIndex++;
      currentNode = currentNode.next;
    }
    return -1;
  }
  function insertAt(position, element) {
    const isPositionInTheRange = position > -1 && position <= length;
    if (!isPositionInTheRange) {
      return false;
    }
    const node = {
      element,
      next: null,
    };
    let currentNode = head;
    const isHeadPosition = position === 0;
    if (isHeadPosition) {
      node.next = currentNode;
      head = node;
    } else {
      let previousNode = null;
      let index = 0;
      while (index++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = node;
      node.next = currentNode;
    }
    length++;
    return true;
  }
  function removeAt(position) {
    const isPositionInTheRange = position > -1 && position < length;
    if (!isPositionInTheRange) {
      return null;
    }
    let currentNode = head;
    if (position === 0) {
      head = currentNode.next;
    } else {
      let index = 0;
      let previousNode = null;
      while (index++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
    return currentNode;
  }
  function removeAt(position) {
    const isPositionInTheRange = position > -1 && position < length;
    if (!isPositionInTheRange) {
      return null;
    }
    let currentNode = head;
    if (position === 0) {
      head = currentNode.next;
    } else {
      let index = 0;
      let previousNode = null;
      while (index++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
    return currentNode.element;
  }
  function remove(element) {
    const elementIndex = indexOf(element);
    return removeAt(elementIndex);
  }
  function toString() {
    let result = "";
    let current = head;
    while (current) {
      result += `${current.element}${current.next ? ", " : ""}`;
      current = current.next;
    }
    return result;
  }
}
const linkedList = LinkedListFactory();
linkedList.append(1);
linkedList.append(10);
linkedList.append(-1);
linkedList.append(40);
linkedList.append(-123);
console.log(linkedList.toString()); // 1, 10, -1, 40, -123
console.log(linkedList.removeAt(3)); // 40
console.log(linkedList.toString()); // 1, 10, -1, -123
console.log(linkedList.indexOf(1)); // 0
console.log(linkedList.remove(1)); // 1
console.log(linkedList.toString()); // 10, -1, -123

Заключение

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

Также есть два его варианта: «двусвязный» (следующая и предыдущая ссылка) и циркулярный, но я думаю, что он будет лучше в другой статье.

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

Если у вас есть какие-либо комментарии по этому поводу, напишите мне в Твиттере, чтобы мы могли вместе накапливать знания!

Ваше здоровье.

использованная литература

• Https://developer.mozilla.org/en-US/docs/Web/JavaScript/Memory_Management
• Https://www.geeksforgeeks.org/applications-of-linked-list-data-structure
• Https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
• Https://en.wikipedia.org/wiki/Linked_list

Структура данных с помощью JavaScript

• "Куча"
• "Очередь"
• Связанный список

3 части серии

Теги

• "#Информатика"
• "#Структура данных"

Больше контента на plainenglish.io