ЛР: Data Structures: Связный список

Существует два типа связных списков, о которых мы поговорим:

Односвязный список
Двусвязный список

Нода связного списка

Под нодой связного списка далее будет иметься ввиду следующая структура:

interface Node {
    value: any;
    next: Node | null;
}

const anotherNode: Node = {
    value: "Another value, that you need",
    next: null,
}

const node: Node = {
    value: "Any value, that you want",
    next: anotherNode
}

Односвязный список

Односвязный список, это последовательность "нод", которые содержат текущее значение, а также ссылку на следующую ноду:

const head = {
    value: "The first node!",
    next: /* next node */
}

Первую ноду, которая образует связный список обычно называют head.

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

Связный список это по сути куча хэшмап, которые рандомно расположены в памяти. Сложность добавления ноды занимает $O(1)$, ибо нам не нужно перетаскивать элементы;
Данная структура данных имеет динамический размер, в отличии от массива, а также может использовать в качестве значений любой тип данных

Минусы односвязного списка:

Для того чтобы найти элемент, нужно дойти до него начиная с первой ноды;
Для того чтобы найти предыдущий элемент, нужно держать переменную для предыдущей ноды

Двусвязный список

Двусвязный список - это список нод, каждая из которых содержит значение и ссылку на предыдущую и следующую ноду.

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

interface Node {
    value: any;
    next: Node | null;
    previous: Node | null;
}

Данная структура имеет все те же плюсы и минусы, что и у односвязного списка, однако, в случае двусвязного списка мы можем вычислить предыдущую ноду без использования временной переменной, это является как плюсом, так и минусом, ибо теперь для того чтобы удалить ноду из середины, нам нужно поменять значение поля previous у следующей ноды и значения поля next у предыдущей ноды:

const deleteNode = (head: Node, id: any) => {
  let currentNode = head;
  let foundNode: Node | null = null;

  while (currentNode.next) {
    if (head.value === id) {
      foundNode = currentNode;
      break;
    }

    currentNode = currentNode.next;
  }

  if (foundNode) {
    foundNode.next?.previous = foundNode.previous;
    foundNode.previous?.next = foundNode.next;
  }

  return foundNode;
};