🔗 Listas Enlazadas

init

Pruébalo: Presiona recorrer para seguir el puntero de cabeza hacia un índice — cuenta los saltos. Luego inserta o elimina en la misma posición — el recableado de punteros es O(1), pero aún tienes que llegar al lugar.

Por qué importa

Las listas enlazadas te enseñan a pensar en términos de punteros — un concepto fundamental en ciencias de la computación. Aunque en la práctica suelen ser más lentas que los arreglos, abren la puerta a entender árboles, grafos y la gestión de memoria.

La idea

Imagina una búsqueda del tesoro. Cada pista te dice dónde encontrar la siguiente pista. No puedes saltar a la pista #5 — debes seguir la cadena desde el inicio.

Eso es una lista enlazada. Cada nodo contiene datos y un puntero al siguiente nodo.

El compromiso está invertido respecto a los arreglos:

• Insertar/eliminar en una posición conocida: O(1) — solo recableas los punteros
• Encontrar una posición por índice: O(n) — debes recorrer la cadena

Cuando necesitas insertar/eliminar con frecuencia al principio o después de un nodo conocido, ganan las listas enlazadas. Cuando necesitas acceso aleatorio, ganan los arreglos.

Puntos clave

• Insertar/eliminar en una posición conocida es O(1) — solo cambias punteros
• El acceso por índice es O(n) — debes recorrer desde la cabeza
• No hay espacio desperdiciado, pero sí memoria extra por nodo para los punteros
• Bueno para inserciones frecuentes al frente o después de nodos conocidos

Profundizando

Simple vs doble vs circular

La característica estrella de la lista doblemente enlazada es el empalme (splice) O(1): dado un nodo n al que ya tienes un puntero, puedes eliminarlo de la lista con dos escrituras de puntero:

n.prev.next = n.next;
n.next.prev = n.prev;

Sin recorrido. Por esto cada implementación de caché LRU bajo el sol usa una lista doblemente enlazada respaldada por una tabla hash: la tabla hash te da búsqueda O(1) del nodo por clave; la lista doblemente enlazada te permite mover ese nodo O(1) al frente en cada acceso.

Las variantes circulares sustentan los planificadores por turnos (round-robin) — todo planificador de procesos de un sistema operativo que da a cada hilo ejecutable una porción de tiempo tiene una lista circular en alguna parte. El puntero “next” del último hilo apunta de vuelta al primero; simplemente sigues recorriendo.

Sobrecarga de memoria — los números reales

Un nodo de lista de enlace simple que contiene un int32 en un sistema de 64 bits:

[ 4 bytes de datos ][ 4 bytes de relleno ][ 8 bytes de puntero next ] = 16 B

Los datos son 4 bytes, el almacenamiento son 16 bytes — 4× de sobrecarga por elemento. Una lista de enlace doble con los mismos datos:

[ 4 bytes de datos ][ 4 bytes de relleno ][ 8 bytes next ][ 8 bytes prev ] = 24 B

6× de sobrecarga. Y estos nodos no son secuenciales en memoria — cada uno es una asignación de heap separada, así que recorrer la lista es una fiesta de fallos de caché. Los mismos int32 en un Vec<i32> se empaquetan en 4 bytes cada uno, contiguos, prebuscados por la CPU. Para un bucle de un millón de elementos, el arreglo puede ser de 50 a 100× más rápido a pesar de un Big-O idéntico.

La lección: las listas enlazadas son la elección correcta cuando realmente necesitas un empalme (splice) O(1) con una referencia a un nodo activo (caché LRU, planificador del SO, listas intrusivas en estructuras de datos del kernel). Para todo lo demás, prefiere los arreglos — consulta la sección de localidad de caché de la lección de arreglos.

Detalles matemáticos

Complejidad temporal

Access by index: O(n)

Insert at head: O(1)

Insert after node: O(1)

Delete node (given prev): O(1)

Search: O(n)

Espacio

Cada nodo almacena datos + puntero(s)

Memory per node: sizeof(T) + sizeof(pointer)

Implementación

Nodo de lista enlazada

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

// Insertar en la cabeza: O(1)
fn push_front(head: &mut Option<Box<Node<T>>>, data: T) {
    let new_node = Box::new(Node {
        data,
        next: head.take(),
    });
    *head = Some(new_node);
}

Cuándo usarla

• Inserciones/eliminaciones frecuentes al frente
• Tamaño desconocido, con restricciones de memoria
• Bloque de construcción para pilas y colas
• Para entender la manipulación de punteros

Práctica

Tres problemas clásicos de listas enlazadas, cada uno resaltando un patrón de punteros diferente:

• Invertir una lista enlazada — fácil · el baile de los tres punteros, el ejercicio canónico de manipulación de punteros
• Detectar un ciclo (la tortuga y la liebre de Floyd) — medio · alternativa con espacio O(1) a un conjunto de visitados
• Fusionar dos listas enlazadas ordenadas — fácil · empalmar nodos sin asignar memoria — el paso de mezcla del merge sort

→ Explora todos los problemas de práctica