Listas enlazadas

Agregar un valor al principio de una lista enlazada cambia dos punteros, tenga la lista 4 valores o 4 millones.

Valores que apuntan al siguiente

Un arreglo guarda sus valores uno al lado del otro, y por eso cambiar el principio es caro. Una lista enlazada abandona esa regla. Cada valor vive en su propio registro pequeño llamado nodo, y los nodos pueden estar en cualquier lugar de la memoria. Las notas del 6.006 del MIT describen un nodo con dos campos: el elemento (item) y next, un puntero al nodo siguiente. La lista en sí solo recuerda el primer nodo, llamado cabeza (head). El next del último nodo es null, lo que marca el final.

Para leer la lista empiezas en head y sigues los punteros next uno por uno, como quien sigue una cadena de notas en la que cada una dice dónde está escondida la siguiente. Eso tiene un costo. No hay fórmula para la dirección del cuarto nodo, así que obtener el valor de la posición i significa visitar i + 1 nodos. El MIT da get at(i) para una lista enlazada como O(n), mientras que el arreglo lo resolvía en un paso.

// un nodo por valor: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// recorrer la lista
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Cambiar la lista volviendo a enlazar

La ventaja aparece cuando cambias la lista. Para poner un valor nuevo al principio, crea un nodo cuyo next sea la cabeza actual y luego haz que head apunte al nodo nuevo. Dos cambios de puntero, y nada más se mueve. Eliminar el primer nodo es un solo cambio: hacer que head apunte a head.next. Compáralo con el arreglo, donde las mismas operaciones movían todos los valores.

En el medio, el trabajo está en encontrar el lugar. Para insertar en la posición i, recorres hasta el nodo justo anterior (i visitas) y luego haces los mismos dos cambios de puntero: new.next = prev.next y después prev.next = new. El orden importa. Si cambias primero prev.next, el resto de la lista se pierde, porque ya nada apunta a él. En el laboratorio, un paso es un nodo visitado o un puntero cambiado, así que insertar en la posición 2 de una lista de 4 nodos cuesta 2 visitas más 2 cambios, 4 pasos.

Cuándo usarla

Una lista enlazada encaja bien cuando la mayoría de los cambios ocurren en un lugar al que ya tienes un puntero, como el principio, y casi nunca necesitas la posición i. Las colas y las pilas se pueden construir con listas enlazadas, y también las cadenas dentro de una tabla hash de la unidad siguiente. Hay variantes. Una lista doblemente enlazada le da a cada nodo también un puntero prev, así que puedes recorrerla hacia atrás y eliminar un nodo en un paso una vez que lo tienes. Guardar un puntero tail además de head hace barato agregar al final.

En el JavaScript de todos los días casi nunca se escribe una lista enlazada, porque los arreglos están muy optimizados y las cachés de los procesadores modernos favorecen los valores guardados uno junto a otro. Aun así, la idea importa: los árboles, los grafos y muchas estructuras de las bibliotecas se construyen con nodos y punteros exactamente de esta manera.