Я не верю, что будет возможно получить 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) для обоих, но с меньшим коэффициентом. Если вы хотите вставить, вы можете найти правильный столбец, просто изучив первый ряд каждого столбца. Затем вы пересекаете сам столбец, ища правильный ряд. Затем элемент вставляется и счет для этого столбца увеличивается. Аналогично для удалений, хотя в этом случае счет уменьшается, и весь столбец удаляется, когда его счет достигает нуля.
Для поиска по индексу вы пересекаете столбцы, чтобы найти правильный столбец, а затем перебираете элементы в столбце, чтобы получить нужный элемент.
И это может быть даже автоматическая настройка, пытаясь сохранить максимальную высоту и ширину примерно одинаковыми.