Arrays y linked lists resuelven el mismo problema superficial: guardar una colección de elementos. Pero la forma en que cada una lo hace produce trade-offs radicalmente distintos. Elegir mal no es un error de sintaxis — es un error de diseño que escala mal.
Arrays: memoria contigua
Un array ocupa un bloque continuo de memoria. Todos los elementos están uno al lado del otro, sin huecos.
Eso significa que dado el índice de cualquier elemento, la dirección de memoria se calcula en una sola operación:
dirección = dirección_base + (índice × tamaño_de_elemento)
Acceso a array[42] es exactamente igual de rápido que acceso a array[0]. No hay traversal, no hay seguir punteros. Es O(1) garantizado.
const nums = [10, 20, 30, 40, 50]
console.log(nums[3]) // 40 — una operación, sin importar el tamaño del array
El costo es la inserción y eliminación. Si insertás en el medio, tenés que mover todos los elementos que vienen después para hacer espacio. Si eliminás del medio, tenés que cerrar el hueco. Ambas operaciones son O(n) en el peor caso.
// Insertar en la posición 2 de un array de 1 millón de elementos:
// → los elementos en posiciones 2 a 999.999 se mueven una posición hacia adelante
nums.splice(2, 0, 99) // O(n) — no O(1)
Tamaño fijo. Un array de bajo nivel (como en C o Java sin wrappers) tiene tamaño definido al momento de la declaración. No puede crecer. Esto no es un bug del lenguaje — es la consecuencia directa de la memoria contigua: no hay garantía de que los bytes después del array estén disponibles.
Linked Lists: punteros en lugar de contigüidad
Una linked list no ocupa un bloque continuo. Cada elemento vive en una dirección de memoria independiente y contiene un puntero al siguiente.
// Estructura conceptual de un nodo
{
value: 10,
next: → { value: 20, next: → { value: 30, next: null } }
}
La consecuencia directa: no hay acceso por índice. Para llegar al elemento 42, tenés que empezar desde el primero y seguir 42 punteros. Es O(n).
Lo que sí es O(1) es insertar o eliminar al principio de la lista. No hay desplazamiento — solo redirigís punteros.
// Insertar al inicio de una linked list:
const nuevoNodo = { value: 99, next: cabeza }
cabeza = nuevoNodo
// Dos operaciones, sin importar el tamaño de la lista
Insertar o eliminar en cualquier posición también es O(1) si ya tenés el puntero al nodo anterior. El trabajo está en encontrar ese nodo — que es O(n).
Singly vs. Doubly Linked List
Una singly linked list tiene un puntero al siguiente nodo. Traversal solo hacia adelante.
Una doubly linked list tiene punteros al nodo anterior y al siguiente. Traversal bidireccional, y eliminar un nodo conocido es O(1) sin necesidad de encontrar el anterior.
// Nodo de doubly linked list
{
value: 30,
prev: → nodo_anterior,
next: → nodo_siguiente
}
El costo: el doble de overhead de memoria por nodo, y mayor complejidad en todas las operaciones de modificación.
Cache locality: por qué los arrays ganan en la práctica
Hay un factor que las complejidades asintóticas no capturan: el cache del procesador.
Cuando el CPU accede a una dirección de memoria, carga automáticamente un bloque de bytes vecinos al cache (una cache line). Si el siguiente acceso está en esa misma cache line, es instantáneo. Si no, hay un cache miss — y buscar en RAM es órdenes de magnitud más lento.
Los arrays son cache-friendly. Los elementos están contiguos, entonces recorrer un array es una serie de cache hits.
Las linked lists son cache-unfriendly. Los nodos están dispersos en memoria. Cada puntero que seguís probablemente apunta a una dirección que no está en cache. Recorrer una linked list de un millón de elementos puede ser dramáticamente más lento que recorrer un array equivalente, aunque ambas sean O(n) en papel.
En benchmarks reales, un array puede ser 5x a 10x más rápido que una linked list para traversal, aunque la complejidad asintótica sea idéntica.
Dynamic Arrays: el puente entre los dos mundos
En la práctica, la mayoría del código usa dynamic arrays — arrays que crecen automáticamente cuando se llenan. Son ArrayList en Java, vector en C++, y las listas en Python.
Internamente, un dynamic array es un array estático con capacidad reservada. Cuando se llena, crea un array más grande (generalmente el doble de tamaño), copia todos los elementos, y descarta el original.
El costo de esa copia es O(n), pero ocurre tan raramente que el costo amortizado de inserción sigue siendo O(1) (como vimos en el artículo anterior). El acceso por índice se mantiene O(1).
Los dynamic arrays capturan lo mejor de los arrays estáticos — acceso rápido, cache locality — sin el límite de tamaño fijo. Por eso son la estructura por defecto en casi todos los lenguajes modernos.
La comparación que importa
| Operación | Array | Linked List |
|---|---|---|
| Acceso por índice | O(1) | O(n) |
| Inserción al inicio | O(n) | O(1) |
| Inserción al final | O(1) amortizado | O(1) con tail pointer |
| Inserción en el medio | O(n) | O(1) con puntero al nodo previo |
| Eliminación | O(n) | O(1) con puntero al nodo previo |
| Cache locality | Excelente | Pobre |
| Overhead de memoria | Ninguno | Un puntero por nodo (o dos, si doubly) |
| Tamaño dinámico | Requiere copia | Nativo |
Cuándo usar cada uno
Usá arrays (o dynamic arrays) cuando:
- Necesitás acceso frecuente por índice
- Recorrés la colección secuencialmente
- El tamaño es relativamente estable o crece principalmente al final
- Cache locality importa (casi siempre)
Usá linked lists cuando:
- Insertás y eliminás frecuentemente al principio o en el medio, y tenés punteros a esos nodos
- El tamaño varía dramáticamente y el overhead de copia del dynamic array es inaceptable
- Implementás estructuras de orden superior — Stacks, Queues, y muchos tipos de árboles se construyen sobre linked lists
En la práctica, la mayoría del código de producción usa arrays o dynamic arrays casi siempre. Las linked lists aparecen cuando el problema de inserción/eliminación es lo suficientemente crítico como para justificar perder el acceso directo y la cache locality.
La regla simple: si dudás, empezá con el array dinámico del lenguaje. Cambiá a linked list solo cuando tenés evidencia concreta de que las inserciones son el cuello de botella.