Comparación de modelos

Lista frente a array

Las dos son secuencias. Compara insertar en la posición 500 de una secuencia de 1000 valores, sin tener ninguna referencia previa.

Sin ninguna referencia previa (la lista solo tiene la cabeza), ¿qué cuesta insertar en la posición 800 de 1000 valores en cada representación?Array: unos 200 desplazamientos. Lista: unos 800 saltos para llegar y un enlaceLos dos O(1): los dos llegan a la posición 800 con una cuenta y escribenArray: unos 800 desplazamientos. Lista: O(1), porque basta cambiar un enlaceArray: unos 800 desplazamientos. Lista: unos 800 saltos para llegar y un enlace