Listas enlazadas: nodos conectados por punteros

En el artículo anterior vimos cómo los arrays ofrecen acceso aleatorio en O(1) gracias a que son contiguos en memoria. Esa contigüidad, sin embargo, tiene un precio: insertar o eliminar en medio cuesta O(n) porque hay que desplazar elementos. Las listas enlazadas resuelven ese problema sacrificando lo contrario: no son contiguas, no tienen acceso aleatorio, pero insertar y eliminar (si tienes la referencia al nodo correcto) es O(1).

Entender cuándo cambiar un array por una lista enlazada —y cuándo no— es una de las decisiones de diseño más frecuentes en programación. Spoiler: en la práctica las listas enlazadas se usan menos de lo que la literatura sugiere, porque los arrays dinámicos ganan casi siempre por localidad de caché. Pero tienen sus nichos.

Explicación conceptual

Una lista enlazada es una colección de nodos, donde cada nodo contiene dos cosas:

1. Un dato (el valor que queremos guardar).

2. Un puntero (o referencia) al siguiente nodo.

Los nodos viven en posiciones arbitrarias del heap, no necesariamente juntos. Lo único que los une es la cadena de punteros. El primer nodo se llama head (cabeza); el último tiene el puntero next apuntando a null, indicando el final.

head → [ dato | next ] → [ dato | next ] → [ dato | next ] → null

Variantes principales:

• Lista simple: cada nodo solo conoce al siguiente.

• Lista doble: cada nodo conoce al siguiente y al anterior. Permite recorrer hacia atrás.

• Lista circular: el último nodo apunta al primero en vez de a null. Útil para colas circulares y round-robin.

Ejemplo gráfico

La imagen destacada muestra cuatro nodos conectados por flechas, con el último apuntando a null. Cada nodo se dibuja como una caja dividida en "dato" y "next", recalcando que un nodo es siempre ese par de campos.

Implementación en PHP

PHP no trae listas enlazadas nativas, pero sí una clase en la SPL: SplDoublyLinkedList (lista doble). Igualmente, implementarla manualmente es buen ejercicio.

// Implementación manual de lista simple
class Nodo {
    public int $valor;
    public ?Nodo $siguiente = null;
    public function __construct(int $valor) {
        $this->valor = $valor;
    }
}

class ListaEnlazada {
    private ?Nodo $cabeza = null;

    public function agregarAlInicio(int $v): void {
        $nuevo = new Nodo($v);
        $nuevo->siguiente = $this->cabeza;
        $this->cabeza = $nuevo;
    }

    public function buscar(int $v): ?Nodo {
        $actual = $this->cabeza;
        while ($actual !== null) {
            if ($actual->valor === $v) return $actual;
            $actual = $actual->siguiente;
        }
        return null;
    }

    public function eliminar(int $v): void {
        if ($this->cabeza === null) return;
        if ($this->cabeza->valor === $v) {
            $this->cabeza = $this->cabeza->siguiente;
            return;
        }
        $prev = $this->cabeza;
        while ($prev->siguiente !== null && $prev->siguiente->valor !== $v) {
            $prev = $prev->siguiente;
        }
        if ($prev->siguiente !== null) {
            $prev->siguiente = $prev->siguiente->siguiente;
        }
    }
}

Y usando la SPL:

$lista = new SplDoublyLinkedList();
$lista->push(10);
$lista->push(20);
$lista->push(30);
foreach ($lista as $v) {
    echo $v . "\n";
}

Implementación en Java

Java trae java.util.LinkedList, que es una lista doble. También puedes implementarla a mano:

// Implementación manual de lista simple
public class ListaEnlazada<T> {
    private static class Nodo<T> {
        T valor;
        Nodo<T> siguiente;
        Nodo(T v) { this.valor = v; }
    }

    private Nodo<T> cabeza;

    public void agregarAlInicio(T v) {
        Nodo<T> nuevo = new Nodo<>(v);
        nuevo.siguiente = cabeza;
        cabeza = nuevo;
    }

    public Nodo<T> buscar(T v) {
        Nodo<T> actual = cabeza;
        while (actual != null) {
            if (actual.valor.equals(v)) return actual;
            actual = actual.siguiente;
        }
        return null;
    }

    public void eliminar(T v) {
        if (cabeza == null) return;
        if (cabeza.valor.equals(v)) {
            cabeza = cabeza.siguiente;
            return;
        }
        Nodo<T> prev = cabeza;
        while (prev.siguiente != null && !prev.siguiente.valor.equals(v)) {
            prev = prev.siguiente;
        }
        if (prev.siguiente != null) {
            prev.siguiente = prev.siguiente.siguiente;
        }
    }
}

Usando la librería estándar:

LinkedList<Integer> lista = new LinkedList<>();
lista.add(10);
lista.add(20);
lista.addFirst(5);
// lista = [5, 10, 20]

Operaciones básicas

Inserción

• Al inicio: crea un nodo nuevo, su next apunta a la cabeza actual, y la cabeza pasa a ser él. O(1), sin importar el tamaño de la lista.

• Al final (sin puntero a la cola): recorrer hasta el último nodo. O(n).

• Al final (con puntero a la cola que mantienes): O(1).

• En medio (si ya tienes la referencia al nodo anterior): O(1).

• En medio (si hay que buscar la posición): O(n) para buscar + O(1) para insertar = O(n).

Búsqueda

Hay que recorrer nodo por nodo comparando. O(n) siempre. No hay forma de saltar al medio como en un array: cada nodo solo conoce al siguiente.

Eliminación

• Si tienes la referencia al nodo anterior: O(1), simplemente cambias un puntero.

• Si hay que buscar el nodo: O(n) para buscar + O(1) para eliminar = O(n).

El secreto de las listas enlazadas es: si ya estás parado en el nodo correcto (porque estás iterando, por ejemplo), todas las operaciones son O(1). El costo aparece cuando tienes que llegar ahí.

Complejidad (Big-O)

OperaciónLista simpleLista dobleAcceso por índiceO(n)O(n) (optimizado a n/2 con puntero a tail)BúsquedaO(n)O(n)Inserción al inicioO(1)O(1)Inserción al finalO(n) sin tail, O(1) con tailO(1)Inserción si tienes ref. al previoO(1)O(1)Eliminación si tienes ref. al nodoO(1)O(1)EspacioO(n) + punterosO(n) + punteros ×2

Ventajas y desventajas

Ventajas:

• Inserción y eliminación O(1) cuando ya tienes la referencia.

• No requiere bloques contiguos de memoria: útil en situaciones de fragmentación extrema.

• Crece dinámicamente sin copias masivas como el resize del ArrayList.

• Implementar otras estructuras (pilas, colas) sobre listas enlazadas es directo.

Desventajas:

• Acceso aleatorio O(n). Leer el elemento 100 implica saltar 100 veces por punteros.

• Pésima localidad de caché: los nodos están dispersos en el heap, cada next puede ser un fallo de caché. Esto hace que, en la práctica, recorrer una lista enlazada sea órdenes de magnitud más lento que recorrer un array, aunque ambos sean O(n).

• Overhead de memoria por los punteros (4 u 8 bytes por nodo, ×2 en lista doble).

• Propensa a bugs de punteros (perder referencias, ciclos accidentales).

Casos de uso reales

• Cuando sabes de antemano que las inserciones/eliminaciones en medio dominan sobre las búsquedas. Ejemplo clásico: un buffer de cambios que se escribe, se procesa y se descarta.

• Implementación de pilas y colas: aunque las pilas y colas modernas suelen usar arrays dinámicos, las versiones didácticas y ciertos usos específicos (colas de prioridad por niveles) se apoyan en listas enlazadas.

• Listas de bloques libres en allocadores de memoria: típico en sistemas operativos y runtimes.

• Estructuras que requieren inserción en el medio sin reubicación: como el historial de undo/redo de un editor.

• LRU caches: el LinkedHashMap de Java combina hash table con lista doble para mantener orden de acceso.

En la práctica moderna, un ArrayList casi siempre supera a una LinkedList en Java por la localidad de caché, incluso en escenarios donde teóricamente la lista debería ganar. Benchmarks repetidos han mostrado que hay que hacer millones de inserciones en medio puras para que la LinkedList gane al ArrayList, y esas cargas casi nunca existen en código real.

Cómo se recorre

Siempre secuencial, desde la cabeza:

Nodo actual = cabeza;
while (actual != null) {
    procesar(actual.valor);
    actual = actual.siguiente;
}

En PHP con la SPL o con iteradores:

for ($nodo = $this->cabeza; $nodo !== null; $nodo = $nodo->siguiente) {
    procesar($nodo->valor);
}

Recorrido recursivo (elegante pero consume stack proporcional a la longitud, lo que discutimos en el artículo de recursión):

void imprimir(Nodo<Integer> n) {
    if (n == null) return;
    System.out.println(n.valor);
    imprimir(n.siguiente);
}

Para listas cortas es fino; para listas de miles de nodos, prefiere iterativo.

Cómo se vería en memoria

Cada nodo es un objeto independiente en el heap. La referencia cabeza vive en el stack (o en otro objeto) y apunta al primer nodo. De ahí, cada next apunta a otra zona arbitraria del heap.

stack: cabeza → heap@0x100: [valor=10, next=0x380]
                heap@0x380: [valor=20, next=0x1A0]
                heap@0x1A0: [valor=30, next=null]

Compárese con un array, donde los tres valores estarían pegados en memoria. Esta dispersión es la razón de la mala localidad de caché.

En Java, cada nodo de una LinkedList interna tiene: el header del objeto (~16 bytes), el valor (si es Integer boxed, más referencia + overhead), y dos referencias (al anterior y al siguiente, 8 bytes cada una en JVM de 64 bits). Para 1,000,000 de enteros, una LinkedList puede ocupar 5-10× más memoria que un int[].

Errores comunes

1. Perder la referencia a la cabeza

El error más frecuente y el más frustrante. Si dejas de tener una referencia al primer nodo, toda la lista se vuelve inalcanzable y el GC la recoge. Siempre mantén head (y tail si la usas) como campos de la clase contenedora.

2. No actualizar los enlaces al eliminar

// Incorrecto: el nodo B queda huérfano pero C no está enlazado
A.next = C;  // ok
// Pero si olvidaste esto:
// B.next = null; (buena práctica para no dejar referencias fantasma)

No limpiar B.next no genera bug inmediato, pero puede mantener referencias vivas al resto de la lista innecesariamente (memory leak sutil).

3. Asumir acceso O(1) como en arrays

lista.get(500) en un LinkedList es O(500). Si vas a hacer muchos accesos por índice, migra a ArrayList o carga a un array auxiliar. Es un error típico de quien viene de lenguajes donde lista es siempre ArrayList.

4. Ciclos accidentales

Si por error C.next = A, creas un ciclo. Recorrer la lista se vuelve infinito. Detectarlo requiere algoritmos específicos (el famoso "tortoise and hare" de Floyd). Escribir código defensivo con aserciones o contadores de seguridad ayuda.

5. Comparar nodos con == en lugar de .equals() (Java)

Si los valores son objetos, comparar nodo.valor == otro compara referencias, no contenido. Usa equals().

Resumen

Una lista enlazada es una colección de nodos donde cada uno contiene un dato y una referencia al siguiente (y opcionalmente al anterior). A diferencia del array, no necesita memoria contigua y permite inserciones/eliminaciones O(1) cuando ya tienes la referencia correcta. A cambio pierde el acceso aleatorio y sufre en localidad de caché.

En el uso cotidiano, un ArrayList gana a una LinkedList casi siempre. Las listas enlazadas brillan en nichos específicos: allocadores, listas de undo/redo, LRU caches combinados con hash tables.

En el siguiente artículo vemos las pilas, una estructura que se puede implementar sobre array o sobre lista enlazada y que tiene usos muy concretos: undo, evaluación de expresiones y el propio call stack de tu programa.