Как избавиться от slice и снизить сложность алгоритма? Какая структура данных для этого подойдёт?

Проблема использования slice

Метод slice в массивах создаёт новый массив, копируя элементы из исходного диапазона. Это приводит к временной сложности O(n), где n — количество копируемых элементов. При частых операциях удаления или вставки в середине массива это становится узким местом производительности.

Решение: двусвязный список

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

Пример кода

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  remove(node) {
    if (node.prev) node.prev.next = node.next;
    if (node.next) node.next.prev = node.prev;
    if (node === this.head) this.head = node.next;
    if (node === this.tail) this.tail = node.prev;
  }
}

Применение

Двусвязные списки эффективны в задачах, где требуется частое удаление или вставка элементов, например, в реализации очередей с приоритетом, редакторах текста (операции undo/redo) или кэшах (LRU cache).

Вывод

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