Ответ 1
Я не верю, что можно будет получить O(1) для вставки и поиска. В тот момент, когда вы добавляете массив (или даже фантазии, расщепляемые векторы), вставка становится O(n).
Существуют способы смягчения ущерба в зависимости от ожидаемого поведения вашего списка. Если будет гораздо больше запросов, чем вставки/удаления, может быть лучше просто использовать векторы (массивы с переменным размером) - они достаточно эффективны, не совсем похожи на массивы, но лучше, чем списки переходов (поскольку они, как правило, являются списками массивов, он по-прежнему технически перемещается по списку, но каждый элемент в списке обычно имеет свой размер, что делает его более эффективным).
Если вставки и удаления более часты, вы можете сделать индекс строкой ленивым, чтобы он выполнялся только тогда, когда это необходимо. Например, вставки и удаления изменят только часть связанного списка (и отметят индекс как грязный) - только когда кто-то попытается использовать индекс, он будет перестроен и помечен как чистый.
Вы даже можете оптимизировать перестройку, сохранив запись о первой грязной записи. Это будет означать, что если вы вставляете или удаляете только последнюю половину списка, вам не нужно перестраивать весь индекс, когда кто-то хочет его использовать.
Решением, которое я когда-то реализовал, был 2D-список. Под этим я имею в виду:
+-----------+ +-----------+ +-----------+
List -> | count = 7 | -> | Count = 4 | -> | Count = 6 | -> null
+-----------+ +-----------+ +-----------+
| | |
V V V
+-----------+ +-----------+ +-----------+
| [0] | | [7] | | [11] |
+-----------+ +-----------+ +-----------+
| | |
V V V
+-----------+ +-----------+ +-----------+
| [1] | | [8] | | [12] |
+-----------+ +-----------+ +-----------+
| | |
: : :
: : :
| | |
V V V
+-----------+ +-----------+ +-----------+
| [6] | | [10] | | [16] |
+-----------+ +-----------+ +-----------+
| | |
V V V
null null null
В то время как это сделало как вставку, так и поиск O (n), баланс был прав. В решении с чистым массивом поиск равен O(1), а вставка O(n). Для чистого связанного списка вставка O(1) (как только вы нашли точку вставки, конечно, операцию, которая сама является O(n)), а поиск - O(n).
2D-список O(n) для обоих, но с меньшим коэффициентом. Если вы хотите вставить, вы можете найти нужный столбец, просто просмотрев первую строку каждого столбца. Затем вы пересекаете столбец, который ищет правильный ряд. Затем элемент вставляется и счетчик для этого столбца увеличивается. Аналогично для делеций, хотя в этом случае счетчик уменьшается, а весь столбец удаляется, когда его количество достигает нуля.
Для поиска индекса вы перемещаете столбцы, чтобы найти правильный столбец, а затем перемещайте элементы в столбце, чтобы получить нужный элемент.
И это может быть даже автоматическая настройка, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.