Arreglos o listas enlazadas: qué ganas y qué pagas

← Volver a Blog y artículos

Los arreglos y las listas enlazadas almacenan secuencias, pero hacen compromisos opuestos sobre la disposición en memoria, y esa elección decide qué operaciones son baratas.

Arreglos: acceso rápido por posición

Un arreglo guarda sus elementos uno junto a otro en memoria. Encontrar el elemento número k es una simple aritmética de direcciones, así que el acceso por índice es O(1). El costo aparece al insertar o eliminar en medio: todos los elementos posteriores deben desplazarse, lo que toma O(n). El almacenamiento contiguo también aprovecha bien las cachés del procesador, lo que ayuda en la práctica.

Listas enlazadas: reorganización rápida

Una lista enlazada guarda cada valor en un nodo junto con un puntero al siguiente nodo. Si ya tienes una referencia a un nodo, insertar o eliminar después de él solo requiere reconectar un puntero, en O(1). A cambio, llegar al nodo k exige recorrer k pasos, y cada nodo necesita memoria adicional para su puntero.

Los arreglos dinámicos reducen gran parte de la diferencia

Un arreglo dinámico crece reservando un bloque mayor cuando se llena. Como la capacidad aumenta de forma multiplicativa, agregar al final es O(1) amortizado. Para la mayoría de los programas cotidianos, es la opción por defecto más sensata.

Guía rápida de decisión

Necesitas acceso por índice, búsqueda binaria o memoria compacta: elige un arreglo.
Insertas o eliminas con frecuencia en posiciones intermedias conocidas y ya tienes referencias a los nodos: considera una lista enlazada.
No estás seguro: empieza con un arreglo dinámico y mide antes de cambiar.

Un error común

Las listas enlazadas no son automáticamente más rápidas para insertar. Si primero debes buscar la posición, esa búsqueda cuesta O(n) y puede anular la ventaja.

Continúa con el libro

Consulta el tratamiento completo, los ejemplos y los ejercicios en Algoritmos explicados con claridad.