O (1) удаление для очереди JavaScript

Question

Как я могу создать очередь в JavaScript, где я могу добавлять / удалять элементы в почти O (1) / постоянное время?Прямо сейчас у меня есть простой массив в виде очереди, но чтобы найти элемент для удаления, мне нужно пройти через массив, а затем вызвать Array.prototype.splice.

Мало того, но если у вас есть очередь FIFO, основанная на простом массиве, вам нужно будет вызвать Array.prototype.shift или Array.prototype.unshift, и оба они O (N), потому что они должныобновить индексы каждого элемента в массиве.

Так что я ищу, чтобы получить постоянное время вставки / удаления элементов в любом месте списка / очереди.Простой массив, кажется, не дает этого, если вы попытаетесь превратить его в очередь FIFO.

Answer 1

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

См. Ответ здесь:

https://www.quora.com/How-can-I-create-a-queue-in-JavaScript-where-I-can-search-for-or-remove-elements-in-near-O-1-time-Right-now-I-have-a-simple-array-as-a-queue-but-to-find-an-element-to-delete-I-have-to-go-through-the-array-and-then

Вот реализация, которая кажетсяРабота:

https://github.com/ORESoftware/linked-queue

Простой пример того, почему это работает, с массивом, каждый вызов shift / unshift O (N), поэтому следующее занимает 80 секунд!

const values = [];

const t = Date.now();

for (let i = 0; i < 100000; i++) {
  values.unshift({});
}

console.log('total time:', Date.now() - t); // 80 seconds!

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

const {LinkedQueue} = require('@oresoftware/linked-queue');

const q = new LinkedQueue();

const t = Date.now();

for (let i = 0; i < 100000; i++) {
  q.addToFront({});
}

console.log('total time:', Date.now() - t);  // 60 milliseconds!