Listas enlazadas y el costo de seguir punteros

En un arreglo, los elementos viven uno al lado del otro. En una lista enlazada, cada elemento puede estar en cualquier lugar y guarda la referencia al siguiente. Ese cambio parece pequeño, pero redefine qué operaciones son baratas.

El nodo: un valor y un enlace

La unidad de una lista es el nodo. Guarda un valor y un enlace:

type ListNode<T> = {
  value: T;
  next: ListNode<T> | null;
};

La lista guarda una referencia a la cabeza. Desde ahí puede llegar al segundo nodo, luego al tercero y así hasta encontrar null. Los nodos forman un orden lógico aunque no ocupen posiciones consecutivas en memoria.

No hay salto: para llegar hay que recorrer

Para leer el elemento de posición $k$, hay que seguir $k$ enlaces desde la cabeza. El acceso cuesta $O(k)$ y, en el peor caso, $O(n)$. No existe el salto directo que ofrece un arreglo con values[k] en $O(1)$.

Buscar por valor también cuesta $O(n)$ si la lista no tiene otro índice. Una lista enlazada no acelera búsquedas por sí sola; optimiza cambios locales cuando ya conocemos el nodo donde deben hacerse.

Insertar es cambiar una referencia

Insertar al principio requiere crear un nodo y cambiar una referencia:

const prepend = <T>(head: ListNode<T> | null, value: T): ListNode<T> => ({
  value,
  next: head,
});

Eso cuesta $O(1)$, sin importar cuántos nodos existan. Insertar después de un nodo conocido también cuesta $O(1)$: el nuevo apunta al sucesor y el nodo anterior pasa a apuntar al nuevo. Pero encontrar primero la posición sigue costando $O(n)$.

Eliminar, y por qué hace falta el anterior

Eliminar la cabeza consiste en reemplazarla por head.next, también en $O(1)$. Para borrar otro nodo en una lista simplemente enlazada necesitamos conocer el anterior, porque es quien debe saltar sobre el nodo eliminado.

Una lista doblemente enlazada agrega a cada nodo una referencia previous. Consume más memoria y exige mantener dos enlaces consistentes, pero permite borrar un nodo conocido o recorrer hacia atrás en $O(1)$.

Contra el arreglo dinámico

Un arreglo dinámico permite acceso por índice en $O(1)$ y suele aprovechar mejor la caché del procesador porque sus elementos están contiguos. Insertar en el medio puede desplazar muchos elementos, aunque agregar al final tiene costo amortizado $O(1)$.

Una lista evita esos desplazamientos, pero cada nodo agrega memoria para enlaces y cada salto puede llevar a otra región de memoria. En hardware real, recorrerla suele ser más lento que recorrer un arreglo incluso cuando ambos recorridos son $O(n)$.

Las invariantes que la sostienen

La implementación depende de invariantes simples: si la lista está vacía, la cabeza es null; todo nodo salvo el último tiene sucesor; el último apunta a null. Si además se guarda una cola, debe referir al último nodo y actualizarse al insertar o borrar extremos.

Los errores aparecen al cambiar enlaces en un orden que pierde parte de la cadena, dejar una cola vieja o crear un ciclo accidental. Antes de mutar, conviene identificar qué referencias deben sobrevivir a la operación.

Cuándo una lista enlazada, y cuándo no

La tabla de arriba explica por qué la lista enlazada suena mejor de lo que es. Las filas de $O(1)$ son ciertas y tienen una condición escondida: ya tener el nodo en la mano. Encontrarlo cuesta $O(n)$, así que «insertar en el medio en $O(1)$» sólo se cobra cuando el recorrido ya te dejó parado ahí, que es el caso de un iterador o de una estructura que guarda referencias a sus nodos.

Cierre

Las listas enlazadas cambian acceso aleatorio por edición local. Son útiles cuando se insertan o eliminan nodos ya localizados y sus referencias deben permanecer estables. Si predominan el recorrido y el acceso por posición, un arreglo suele ser más simple, compacto y rápido.