Развитие языка JavaScript постепенно переносит всю тяжесть вычислений с одного сервера на сеть пользовательских компьютеров. Это супер-хорошо. Программирование на стороне сервера вынуждает очень тщательно оптимизировать код по быстродействию и занимаемой памяти, в это же время разработка клиентской части несколько отстает.

Часто для удобного и быстрого кодирования применяют специализированные структуры данных. Именно так и поступают при разработке на Java:

https://habr.com/ru/post/237043/

А вот для подобной работы с JavaScript оптимизированных инструментов по умолчанию не предоставляется. Реализация Array(), Set() и Map() перекладывается на плечи разработчиков браузерных движков, а все их разработки на сегодняшний день загнались хэш-таблицы с удвоением размера и копированием :

https://habr.com/ru/company/ruvds/blog/518032/

Зададимся вопросом — а что если требуются уже прямо сейчас действительно оптимальные по производительности и памяти структуры данных. Какой минимальный набор таких структур достаточно реализовать и поддерживать? Один из вариантов ответа — это сделать двунаправленный связный список и сбалансированное дерево поиска.

Что это нам даст?

Реализуя связный список LinkedList мы получаем сразу список, двунаправленную очередь и стек. И если это сделать без JavaScript Array(), а лишь используя простые ссылки на объекты, то получаем действительно оптимальную структуру данных.

Если же сделать бинарное сбалансированное дерево поиска TreeMap, например идеально сбалансированное AVL-дерево:

https://habr.com/ru/post/150732/

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

1) Array = {TreeMap.get(i) , TreeMap.set(i, value), TreeMap.keys()} — динамический массив любого размера, правда операция получить список ключей TreeMap.keys() выполняется за O(nlog(n)). Вообще в теоретическом массиве каждое удаление элемента должно сопровождаться сдвигом оставшегося хвоста элементов, но на практике просто оставляют пробелы. Если непрерывность индексации массива вам непринципиальна (некоторые элементы удалены), а важен лишь перебор и порядок - то AVL-TreeMap хорошо итерируется с помощью next(key) и previous(key) или можно обойти дерево рекурсивно в порядке возрастания или убывания ключей inOrder(). Кроме того AVL-дерево может выдать нам отсортированный по ключам массив. Одним словом выходит нечто похожее на PHP-array, только с асимптотикой O(log(n)), хотя O(1) от хэш-таблиц - это очень прикольно:

https://habr.com/ru/post/162685/

2) Set = TreeMap.set(element, counter) — множество уникальных элементов.

3) Map = TreeMap.set(key, value) — стандартная структура типа ключ-значение. Перебор всех элементов в цикле лучше делать через функции next(key) и previous(key) или использовать стандартные обходы деревьев preOrder(), inOrder(), postOrder():

https://habr.com/ru/post/144850/

Глубина рекурсии в AVL-дереве порядка log(n).

4) MinHeap и MaxHeap — минимальная и максимальная кучи, они же очереди с приоритетами. Сложность O(log(n)) - этого достаточно для нормальной работы.

5) Matrix = TreeMap.get("i_j") и Tensor = TreeMap.get("i_j_k"): простые операции преобразования индексов в строку и обратно ([i, j, k] = "i_j_k") дают нам оптимальные по занимаемой памяти многомерные матрицы, и можно забыть о проблеме разреженности матриц.

6) List — теоретически структуру можно получить если использовать в качестве ключей дробные числа, тогда вставка элемента между i и j будет такая: TreeMap.set((i+j)/2, element)

7) SearchTree — ну и собственно дерево поиска, тоже нам пригодится.

Все операции в TreeMap достаточно оптимальны, порядка O(log(n)).

Вот минимально необходимый интерфейс структуры TreeMap:

/* интерфейс */ 
class TreeMap {     
tree;     
constructor() {         
//интерфейс можно дополнять своими функциями - он отделен от реализации:
this.tree = new AVLTree();
}
get(key) {...}
set(key, value) {...}
delete(key) {...}
getMinKey() {...}
popMinKey() {...}
getMaxKey() {...}
popMaxKey() {...}    
next(key) {...} //следующий элемент (с ключом большим чем key)
previous(key) {...} //предыдущий элемент (с ключом меньше чем key)   
has(key) {...}
keys() {...}
toArray() {...}
/**
* Универсальный рекурсивный обход дерева: через все комбинации [узел, правое поддерево, левое поддерево]
* @param {function} func - callback функция
* @param {type} params - параметры функции
* @param {string} order - порядок обхода дерева
* @returns {params} - возвращает переданные параметры возможно модифицированные
*/
traverse(func, params, order) {...}
clear() {...}    
}
/* реализация */ 
class AVLTree {...}

Исходные коды доступны по ссылке, лицензия свободная:

git clone https://gitflic.ru/project/neutrino/js-collections.git