no creo que será posible conseguir O(1) tanto para la inserción y búsqueda. En el momento en que agrega una matriz (o incluso vectores de división de lujo), la inserción se convierte en O(n).
Existen formas de mitigar el daño según el comportamiento esperado de su lista. Si habrá muchas más búsquedas que inserciones/eliminaciones, puede ser mejor usar vectores (matrices de tamaño variable): estas son razonablemente eficientes, no del todo como matrices, pero mejores que las listas de desplazamiento (ya que estas tienden a ser listas de matrices, todavía está atravesando una lista técnicamente, pero cada elemento de la lista generalmente tiene su tamaño, lo que lo hace más eficiente).
Si inserciones y deleciones son más frecuentes, puede hacer que el índice de construir un perezoso de modo que sólo hace cuando es necesario. Por ejemplo, las inserciones y eliminaciones solo cambiarán la parte de la lista vinculada (y marcarán el índice como sucia); solo cuando alguien intente usar el índice, se reconstruirá y se marcará como limpio.
Incluso puede optimizar la reconstrucción, manteniendo un registro de la primera entrada sucia. Esto significará que si solo inserta o elimina en la última mitad de la lista, no necesita reconstruir todo el índice cuando alguien quiera usarlo.
Una solución que una vez implementé fue una lista 2D. Por esto, quiero decir:
+-----------+ +-----------+ +-----------+
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
Mientras esto hacía tanto la inserción como la búsqueda O (n), el equilibrio era correcto. En una solución de matriz pura, la búsqueda es O(1) y la inserción es O(n). Para una lista enlazada pura, la inserción es O(1) (una vez que haya encontrado el punto de inserción, por supuesto, una operación que es en sí misma O(n)) y la búsqueda es O(n).
La lista 2D es O(n) para ambos, pero con un factor inferior. Si está buscando insertar, puede encontrar la columna derecha simplemente examinando la primera fila de cada columna. Luego recorre la columna misma buscando la fila correcta. Luego se inserta el elemento y se aumenta el conteo para esa columna. De manera similar para las eliminaciones, aunque en ese caso el recuento se reduce y la columna completa se elimina cuando su cuenta llega a cero.
Para una búsqueda de índice, que atraviesan las columnas para encontrar la columna correcta, entonces atravesar los elementos de la columna para conseguir el artículo correcto.
Y, puede incluso ser auto-ajuste, tratando de mantener la altura y anchura máximas más o menos lo mismo.
Una respuesta completa con muchas buenas ideas: gracias, realmente lo aprecio. –