Acceder al elemento número 1000: ¿array (lista de Python) o linked list?
Opciones
- Ambos son O(1), porque se conoce la posición
- Array: O(1); linked list: O(n), nodo a nodo (Opción correcta)
- Array: O(n); linked list: O(1) con un índice
- Ambos son O(log n), reduciendo a la mitad la búsqueda
Respuesta
Array O(1); linked list O(n) porque hay que recorrerla nodo a nodo
Por qué
Un array guarda los elementos contiguos en memoria, así que la posición del elemento k se calcula directamente: O(1).
Una linked list guarda los elementos en nodos separados, cada uno apuntando al siguiente. Para llegar al elemento 1000 hay que seguir 1000 enlaces: O(n).
A cambio, una linked list puede insertar o quitar un nodo en O(1) cuando ya estás en el lugar correcto.
Recuerda
Array = acceso rápido por índice. Linked list = inserción rápida donde estás.