Arrays y listas enlazadas
Las dos formas de guardar una secuencia — memoria contigua contra nodos enlazados — y por qué el array gana más veces de las que dice el Big-O.
En esta página
Todas las estructuras que estudiarás después — pilas, colas, tablas hash, árboles — se construyen sobre dos formas primitivas de guardar una secuencia en memoria. Entender su diferencia física, no solo su API, es lo que te permitirá predecir el rendimiento de todo lo demás.
Dos fotografías de la memoria
Un array guarda sus elementos en un bloque contiguo; una lista enlazada los reparte donde haya sitio y los cose con punteros:
La contigüidad del array es la que regala el acceso O(1): la dirección del elemento i es base + i × tamaño. La lista no puede hacer esa cuenta — tiene que caminar.
Esa diferencia física genera todos los costes:
| Operación | Array | Lista enlazada |
|---|---|---|
| Acceso por índice | O(1) — aritmética | O(n) — caminar desde la cabeza |
| Buscar un valor | O(n) | O(n) |
| Insertar/borrar al principio | O(n) — desplazar todo | O(1) — recolocar un puntero |
| Insertar/borrar al final | O(1) amortizado | O(1) con puntero a cola |
| Insertar/borrar en medio | O(n) — desplazar | O(1) si ya tienes el nodo |
| Memoria extra | Ninguna | Un puntero (o dos) por elemento |
La letra pequeña de la lista — “si ya tienes el nodo” — es crucial: llegar hasta el nodo ya cuesta O(n). La lista brilla cuando otra estructura te guarda la referencia al nodo, como verás en la caché LRU.
El array dinámico: por qué push es O(1) “amortizado”
Los arrays de los lenguajes modernos (el Array de JavaScript, el list de Python, el Vec de Rust) son dinámicos: cuando el bloque se llena, reservan otro mayor (típicamente el doble) y copian todo. Esa copia es O(n)… pero ocurre tan pocas veces que, repartida entre todos los push, cada uno sale a O(1) amortizado. Es el mismo truco de “pagar caro rara vez” que ya viste en el redimensionado de las tablas hash.
En cambio, unshift (insertar al principio) desplaza todos los elementos cada vez: O(n) siempre. Un bucle de unshift es O(n²) disfrazado — el clásico bug de rendimiento silencioso.
La ventaja invisible del array: la caché de la CPU
El Big-O de la tabla sugiere un empate técnico. La realidad de la máquina, no:
La consecuencia práctica: el array es la respuesta por defecto. La lista enlazada se gana su sitio en casos concretos, no como opción general.
Cuándo la lista enlazada es la elección correcta
- Caché LRU: una tabla hash guarda referencias directas a los nodos de una lista doblemente enlazada — mover un elemento al frente es O(1) real. Es exactamente el problema de la caché LRU.
- Colas y deques: insertar y extraer por ambos extremos en O(1) sin desplazar nada.
- Insertar mientras iteras: puedes empalmar nodos sin invalidar el recorrido ni mover el resto.
Y una advertencia honesta: en JavaScript rara vez escribirás una lista enlazada fuera de estos patrones — pero reconocerla dentro de las estructuras que usas (y en las entrevistas) es no negociable.
El detalle JavaScript
El Array de JavaScript es un array dinámico de verdad mientras lo trates como tal: índices densos desde 0. Si lo llenas con huecos (arr[5000] = x sobre un array vacío) el motor lo degrada internamente a un diccionario, y adiós contigüidad. Densidad = velocidad.