Структуры данных JavaScript – связанный список

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

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список». К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и основных операций:

• Операция, проверяющая список на пустоту.
• Три операции добавления объекта в список (в начало, конец или внутрь после любого (n-го) элемента списка);
• Операция, вычисляющая первый (головной) элемент списка;
• Операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

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

value: значение элемента
next: указатель на следующий элемент в связанном списке (null, если его нет)
Основными свойствами структуры данных связанного списка являются:

size: количество элементов в связанном списке
head: первый элемент в связанном списке
tail: последний элемент в связанном списке
Основные операции структуры данных связанного списка:

insertAt: вставляет элемент по определенному индексу
removeAt: удаляет элемент по определенному индексу
getAt: извлекает элемент по определенному индексу
clear: очищает связанный список
reverse: меняет порядок элементов в связанном списке на обратный

Javascript Код

class LinkedList {
  constructor() {
    this.nodes = [];
  }

  get size() {
    return this.nodes.length;
  }

  get head() {
    return this.size ? this.nodes[0] : null;
  }

  get tail() {
    return this.size ? this.nodes[this.size - 1] : null;
  }

  insertAt(index, value) {
    const previousNode = this.nodes[index - 1] || null;
    const nextNode = this.nodes[index] || null;
    const node = { value, next: nextNode };

    if (previousNode) previousNode.next = node;
    this.nodes.splice(index, 0, node);
  }

  insertFirst(value) {
    this.insertAt(0, value);
  }

  insertLast(value) {
    this.insertAt(this.size, value);
  }

  getAt(index) {
    return this.nodes[index];
  }

  removeAt(index) {
    const previousNode = this.nodes[index - 1];
    const nextNode = this.nodes[index + 1] || null;

    if (previousNode) previousNode.next = nextNode;

    return this.nodes.splice(index, 1);
  }

  clear() {
    this.nodes = [];
  }

  reverse() {
    this.nodes = this.nodes.reduce(
      (acc, { value }) => [{ value, next: acc[0] || null }, ...acc],
      []
    );
  }

  *[Symbol.iterator]() {
    yield* this.nodes;
  }
}

• Мы создали класс с конструктором, который инициализирует пустой массив узлов для каждого экземпляра.
• Мы определили размера, который возвращает Array.prototype.length для возврата количества элементов в массиве узлов.
• Мы определили геттер head, который возвращает первый элемент массива узлов или null, если он пуст.
• Мы Определи геттер tail, который возвращает последний элемент массива узлов или null, если он пуст.
• Мы определили метод insertAt (), который использует Array.prototype.splice () для добавления нового объекта в массив узлов, обновляя следующий ключ предыдущего элемента.
• Мы определили два удобных метода insertFirst () и insertLast (), которые используют метод insertAt () для вставки нового элемента в начало или конец массива узлов соответственно.
• Мы определили метод getAt (), который извлекает элемент по заданному индексу.
• Мы определили removeAt (), который использует Array.prototype.splice () для удаления объекта в массиве узлов, обновляя следующий ключ предыдущего элемента.
• Мы определили метод clear (), который очищает массив узлов.
• Мы определили метод reverse (), который использует Array.prototype.reduce () и оператор распространения (…) для изменения порядка в массиве узлов, соответствующим образом обновляя следующий ключ каждого элемента.
• Мы определили метод генератора для Symbol.iterator, который делегирует итератору массива узлов, используя синтаксис yield *.

const list = new LinkedList();

list.insertFirst(1);
list.insertFirst(2);
list.insertFirst(3);
list.insertLast(4);
list.insertAt(3, 5);

list.size;                      // 5
list.head.value;                // 3
list.head.next.value;           // 2
list.tail.value;                // 4
[...list.map(e => e.value)];    // [3, 2, 1, 5, 4]

list.removeAt(1);               // 2
list.getAt(1).value;            // 1
list.head.next.value;           // 1
[...list.map(e => e.value)];    // [3, 1, 5, 4]

list.reverse();
[...list.map(e => e.value)];    // [4, 5, 1, 3]

list.clear();
list.size;                      // 0