Listas enlazadas: simples y dobles

Qué cubre este capítulo

El array gana manteniendo sus elementos juntos en memoria. La lista enlazada hace la apuesta contraria: que cada elemento viva donde sea, y conectarlos con punteros. Esa sola decisión le da la vuelta a todo el perfil de costos. Pierdes el acceso O(1) por índice —no hay dirección que calcular, así que llegar al elemento k significa seguir k punteros— y a cambio ganas inserción y borrado en O(1) en cualquier posición donde ya estés parado, sin que nada más se mueva. Este capítulo construye tanto la lista simplemente enlazada como su prima doblemente enlazada, y las pone a competir contra la lista respaldada por array para mostrar, en concreto, qué operación está hecha para ganar cada estructura.

Un poco de historia

Las listas enlazadas son una de las ideas más viejas de la computación que no era simplemente una instrucción de máquina. Salieron del trabajo temprano en inteligencia artificial: Allen Newell, Cliff Shaw y Herbert Simon las metieron en IPL, el Information Processing Language, alrededor de 1955 y 1956, para representar estructuras que crecían y se reacomodaban mientras el programa corría — algo que los arrays fijos no podían hacer con gracia. La idea se difundió rápido porque resolvía un problema real de la época: la memoria era escasa y valiosa, y una lista enlazada te deja hacer crecer una colección de nodo en nodo con la memoria libre que tengas, en vez de reservar por adelantado un bloque contiguo grande. Ese intercambio fundacional —flexibilidad en el acomodo a cambio de renunciar al acceso aleatorio— es exactamente el que sigues pesando hoy.

La intuición

Un nodo es un valor más un puntero al siguiente nodo. La lista en sí no es más que una referencia al primer nodo, la cabeza; todo lo demás lo encuentras siguiendo punteros desde ahí. El último nodo no apunta a nada, y así es como sabes que llegaste al final.

Como los nodos no están en fila, no hay aritmética que te brinque al elemento k. Para leer el quinto elemento arrancas en la cabeza y sigues el puntero next cinco veces. Ese es el precio. Lo que compras es que insertar o borrar no mueve nada: para insertar después de un nodo que ya tienes, haces que tu nodo nuevo apunte a donde ese nodo apuntaba, y luego apuntas ese nodo a tu nodo nuevo. Dos asignaciones, listo, sin importar qué tan larga sea la lista. Compáralo con el array, donde insertar a la mitad arrastra un lugar a la derecha a todos los elementos posteriores.

La lista doblemente enlazada agrega un segundo puntero en cada nodo, de regreso al anterior. Cuesta un poco de memoria y un poco de contabilidad, y compra dos cosas que la lista simplemente enlazada no puede hacer barato: borrar un nodo cuando lo único que tienes es el nodo mismo, y recorrer hacia atrás desde la cola.

Complejidad: cómo escala

Los costos de la lista enlazada son casi la imagen en espejo de los del array:

• Acceso por índice, y búsqueda por valor: $O(n)$. Recorres desde la cabeza.
• Insertar o borrar en un nodo que ya tienes: $O(1)$. Recableas los punteros.
• Insertar al frente, o agregar al final con un puntero tail: $O(1)$.

Aquí no hay recurrencia que desdoblar — el análisis es puro contar saltos de punteros. Lo único que vale la pena decir con precisión es por qué el acceso es genuinamente $O(n)$ y no esconde un camino más barato: los únicos puntos de entrada a la lista son la cabeza y (si la mantienes) la cola, y desde un extremo el elemento k está a k saltos, sin atajo, porque los nodos no cargan información de posición.

La gráfica de abajo es el costo de acceso, medido. Lee todos los elementos de una lista enlazada por índice y lo cronometra contra hacer lo mismo en una lista respaldada por array. La línea de la enlazada se curva hacia arriba con fuerza —leer los n elementos por índice son n recorridos separados, un trabajo $O(n^2)$— mientras que la línea del array se pega al piso:

En n = 4000 los números son brutales: leer cada elemento por índice tomó unos 81 ms en la lista enlazada y 0.06 ms en el array — el array fue como mil trescientas veces más rápido. Eso no es una diferencia de factor constante; es una diferencia de clase de complejidad, $O(n^2)$ contra $O(n)$, y es la razón de existir entera del array.

En qué es buena y en qué no

Ve por una lista enlazada cuando tu trabajo esté en los extremos o en posiciones de las que ya tienes una referencia, y rara vez necesites brincar a un índice arbitrario. Colas, deques, la lista de desalojo dentro de un LRU cache, listas de adyacencia en un grafo — esas son estructuras enlazadas naturales porque las operaciones son todas empalma-aquí, saca-allá, nunca "dame el elemento 5000". La lista también crece de nodo en nodo sin resize y sin copia, así que no hay picos amortizados ni un momento en el que necesite los datos duplicados en memoria.

Los costos son reales y muchas veces decisivos. Cada nodo es una asignación separada con overhead de punteros, así que una lista enlazada usa más memoria que un array con los mismos valores, y —esto importa más que la memoria— los nodos están dispersos, así que recorrer la lista destroza el cache. Recorrer un array fluye por memoria contigua que el CPU va prefetcheando; recorrer una enlazada persigue punteros a direcciones aleatorias, pagando un cache miss en cada salto. En la práctica esto hace que los arrays le ganen a las listas enlazadas en iteración aunque ambos sean $O(n)$, y es la razón de que el consejo "usa un array a menos que tengas una razón específica para no hacerlo" casi siempre sea correcto.

Los datos, o las entradas

Las entradas vuelven a ser secuencias pequeñas de enteros — los valores no importan, la estructura sí. Lo interesante de observar es qué significa realmente "acceso" cuando no hay aritmética de índices: el acto físico de recorrer desde la cabeza, siguiendo un puntero a la vez.

Constrúyela, una función a la vez

Insertar al frente es la operación que la lista enlazada vuelve trivial — un nodo nuevo apunta a la cabeza vieja, y la cabeza se mueve:

def push_front(self, value):
    """O(1): the new node points at the old head, then head moves to it.
    No traversal, no shifting — this is where the linked list shines."""
    self.head = Node(value, self.head)
    if self.tail is None:
        self.tail = self.head
    self._n += 1

Agregar al final es igual de barato mientras mantengas un puntero tail, para no tener que recorrer hasta el final para encontrarlo:

def append(self, value):
    """O(1): a tail pointer lets us link onto the end without walking there."""
    node = Node(value)
    if self.tail is None:
        self.head = self.tail = node
    else:
        self.tail.next = node
        self.tail = node
    self._n += 1

Ahora el lado del costo. Obtener el elemento index no tiene atajo — arrancas en la cabeza y das index saltos. El probe opcional registra el valor en cada salto, que es lo que alimenta la animación:

def get(self, index, probe=None):
    """O(n): the cost the array doesn't have. There is no formula for the
    address of element `index`; you start at the head and follow one `next`
    pointer at a time until you've taken `index` hops."""
    if not 0 <= index < self._n:
        raise IndexError(index)
    node = self.head
    for _ in range(index):
        if probe is not None:
            probe.append(node.value)
        node = node.next
    if probe is not None:
        probe.append(node.value)
    return node.value

Y aquí está la recompensa que justifica el costo de acceso: insertar después de un nodo que ya tienes son dos asignaciones de punteros, independientes del largo de la lista:

def insert_after(self, node, value):
    """O(1): rewire two pointers. Nothing else moves — the whole reason to
    pay the access cost above is to buy insertions this cheap."""
    node.next = Node(value, node.next)
    if node is self.tail:
        self.tail = node.next
    self._n += 1

La lista doblemente enlazada se gana su puntero extra en el borrado. Con solo tener el nodo, puede sacarse a sí misma en O(1) tocando a sus vecinos — una lista simplemente enlazada primero tendría que encontrar el nodo anterior recorriendo desde la cabeza:

def delete(self, node):
    """O(1): unlink a node given only the node itself — impossible in a
    singly linked list, which would first have to find the predecessor by
    walking from the head (O(n))."""
    if node.prev is not None:
        node.prev.next = node.next
    else:
        self.head = node.next
    if node.next is not None:
        node.next.prev = node.prev
    else:
        self.tail = node.prev
    self._n -= 1

Míralo funcionar

Así se ve el acceso O(n) desde adentro. Estamos buscando el valor 5 en una lista de once nodos, y está cerca del final. Cada cuadro es un salto: naranja es el nodo que estamos viendo, los nodos difuminados son por los que ya pasamos, verde es el acierto. No hay forma de brincar hacia adelante — el único camino es seguir el puntero next al vecino. Tomó nueve saltos llegar al valor. Un array habría ido directo:

El código completo

Ambas versiones en un solo lugar — cambia entre ellas. La pestaña desde cero tiene las dos listas: la simplemente enlazada con sus extremos O(1) y su acceso O(n), y la doblemente enlazada cuyo puntero prev hace el borrado O(1). La pestaña de librería es la estructura enlazada que de verdad usas en Python — collections.deque, una lista doblemente enlazada de bloques pequeños con trabajo O(1) en ambos extremos.

"""Singly and doubly linked lists, from scratch.

A linked list gives up the array's one trick — O(1) access by index — to win a
different one: O(1) insertion and deletion at a position you already hold,
without moving any other element. There is no address arithmetic here; the only
way to reach the k-th element is to start at the head and follow k pointers.
"""


class Node:
    """A singly linked node: a value and a pointer to the next node."""
    __slots__ = ("value", "next")

    def __init__(self, value, next=None):
        self.value = value
        self.next = next


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._n = 0

    # region: push_front
    def push_front(self, value):
        """O(1): the new node points at the old head, then head moves to it.
        No traversal, no shifting — this is where the linked list shines."""
        self.head = Node(value, self.head)
        if self.tail is None:
            self.tail = self.head
        self._n += 1
    # endregion

    # region: append
    def append(self, value):
        """O(1): a tail pointer lets us link onto the end without walking there."""
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self._n += 1
    # endregion

    # region: get
    def get(self, index, probe=None):
        """O(n): the cost the array doesn't have. There is no formula for the
        address of element `index`; you start at the head and follow one `next`
        pointer at a time until you've taken `index` hops."""
        if not 0 <= index < self._n:
            raise IndexError(index)
        node = self.head
        for _ in range(index):
            if probe is not None:
                probe.append(node.value)
            node = node.next
        if probe is not None:
            probe.append(node.value)
        return node.value
    # endregion

    # region: insert_after
    def insert_after(self, node, value):
        """O(1): rewire two pointers. Nothing else moves — the whole reason to
        pay the access cost above is to buy insertions this cheap."""
        node.next = Node(value, node.next)
        if node is self.tail:
            self.tail = node.next
        self._n += 1
    # endregion

    # region: find
    def find(self, value, probe=None):
        """O(n): follow `next` pointers from the head until the value shows up."""
        node = self.head
        idx = 0
        while node is not None:
            if probe is not None:
                probe.append(node.value)
            if node.value == value:
                return idx
            node = node.next
            idx += 1
        return -1
    # endregion

    def __len__(self):
        return self._n

    def to_list(self):
        out, node = [], self.head
        while node is not None:
            out.append(node.value)
            node = node.next
        return out


class DNode:
    """A doubly linked node: a value plus pointers BOTH ways."""
    __slots__ = ("value", "prev", "next")

    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


class DoublyLinkedList:
    """The prev pointer costs one extra link per node and buys two things a
    singly linked list can't do in O(1): delete a node you hold, and pop from
    the back. It's the structure behind most real deques and LRU caches."""

    def __init__(self):
        self.head = None
        self.tail = None
        self._n = 0

    # region: dpush_back
    def push_back(self, value):
        """O(1): link a node on at the tail, wiring both directions."""
        node = DNode(value)
        node.prev = self.tail
        if self.tail is not None:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self._n += 1
        return node
    # endregion

    # region: ddelete
    def delete(self, node):
        """O(1): unlink a node given only the node itself — impossible in a
        singly linked list, which would first have to find the predecessor by
        walking from the head (O(n))."""
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self._n -= 1
    # endregion

    def __len__(self):
        return self._n

    def to_list(self):
        out, node = [], self.head
        while node is not None:
            out.append(node.value)
            node = node.next
        return out

"""The library counterpart is collections.deque — a doubly linked list of small
blocks in CPython. It's what you actually reach for when you need O(1) work at
both ends of a sequence.

Two comparisons make the chapter's point:
  1. At the FRONT, the linked structures (our list, deque) are O(1) while the
     array-backed list.insert(0, x) is O(n) — the linked list wins.
  2. By INDEX, the array-backed list is O(1) while walking a linked structure is
     O(n) — the array wins.
Different structures win different operations; that's the whole trade.
"""
from collections import deque


# region: deque_front
def push_front_with_deque(values):
    """O(1) per appendleft — deque is doubly linked, so the front is as cheap
    as the back."""
    dq = deque()
    for value in values:
        dq.appendleft(value)
    return dq
# endregion


# region: list_front
def push_front_with_list(values):
    """O(n) per insert(0, x) — the array-backed list must shift everything right
    each time, so this is O(n^2) overall. Shown as the anti-pattern."""
    out = []
    for value in values:
        out.insert(0, value)
    return out
# endregion


# region: list_index
def sum_by_index_list(seq):
    """O(1) per index into an array-backed list — the operation the linked list
    can't match."""
    total = 0
    for i in range(len(seq)):
        total += seq[i]
    return total
# endregion

Desde cero vs librería

Este enfrentamiento es la declaración más clara de todo el punto del capítulo: distintas estructuras ganan distintas operaciones. El panel izquierdo inserta al frente n veces — nuestra lista enlazada y el deque se mantienen baratos (O(1) cada uno, así que lineal en total) mientras que la lista respaldada por array sube en picada, porque list.insert(0, x) recorre todo a la derecha cada vez. El panel derecho lee cada elemento por índice, y es exactamente al revés: el array queda plano y la lista enlazada explota.

En n = 16000, insertar al frente tomó unos 2.4 ms con nuestra lista enlazada y 0.23 ms con el deque, pero 19 ms con la lista respaldada por array — el array pierde el frente por un orden de magnitud. Cámbiale al acceso y el array gana por tres órdenes. Fíjate que el deque le gana hasta a nuestra lista enlazada en el frente: mismo Big-O, pero es una estructura afinada en C que enlaza bloques de elementos en vez de un nodo por valor, lo que recorta tanto el overhead por nodo como los cache misses. Cuando de verdad necesites una estructura enlazada en Python, esa es la que debes usar — no una cadena de nodos hecha a mano.

Dónde te la vas a encontrar

Rara vez escribes una lista enlazada a mano, pero las usas todo el tiempo a través de otras estructuras. Un deque es una. Las colas de listos y bloqueados dentro del scheduler de un sistema operativo son listas enlazadas de procesos. El LRU cache de los capítulos avanzados es un hash map que apunta hacia una lista doblemente enlazada, para poder mover un nodo al frente en O(1) en cada acceso. Las listas de adyacencia de un grafo son listas enlazadas de vecinos. Y cada vez que te han dicho "agregar al final de una lista está bien, pero insertar al frente dentro de un ciclo es un bug de rendimiento", ese consejo existe porque alguien confundió el modelo de costos de la lista respaldada por array con el de una lista enlazada.

Conclusiones

Una lista enlazada cambia el acceso indexado O(1) del array por inserción y borrado O(1) en una posición que ya tienes, dispersando sus elementos y conectándolos con punteros. El acceso y la búsqueda se vuelven recorridos O(n); empalmar se vuelve dos o cuatro asignaciones de punteros. La variante doblemente enlazada gasta un puntero extra por nodo para volver O(1) el borrado por nodo y el recorrido hacia atrás, y por eso es ella, no la simplemente enlazada, la que está debajo de los deques y los caches reales.

Pésala contra el array preguntándote dónde ocurren tus operaciones. En índices arbitrarios, o iterando en ciclos calientes donde el cache importa, gana el array — casi siempre de forma decisiva, porque la memoria contigua es una ventaja de factor constante que Big-O no muestra. En los extremos, o en posiciones que ya tienes, gana la lista enlazada. La mayoría de las veces el array es el default correcto y deque cubre los casos donde no lo es. Los siguientes dos capítulos toman esta estructura y le acotan las operaciones nada más a los extremos baratos, que es justo lo que son un stack y una queue.