Data Structures: Связный список
Существует два типа связных списков, о которых мы поговорим:
  1. Односвязный список
  2. Двусвязный список
Нода связного списка
Под нодой связного списка далее будет иметься ввиду следующая структура:
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;
};