Lista enlazada explicada: cómo funciona, código y complejidad

Qué problema resuelve una lista enlazada

Un arreglo (en Python, una list) guarda sus elementos en un único bloque contiguo de memoria. Leer a[i] es inmediato, pero insertar al principio desplaza todos los demás elementos una posición a la derecha, lo que cuesta O(n). La lista enlazada evita ese desplazamiento: cada elemento vive en su propio nodo y los nodos se conectan mediante referencias. Para insertar solo hay que cambiar un par de referencias.

Las listas enlazadas son la base de muchas otras estructuras: pilas, colas, los cubos de una tabla hash (encadenamiento separado), cachés LRU y listas de adyacencia en grafos.

La idea en palabras sencillas

Piensa en una búsqueda del tesoro: cada pista te dice dónde está la siguiente. No puedes saltar a la pista 7; primero tienes que seguir las pistas 1 a 6. La lista solo recuerda el primer nodo, llamado cabeza (head). El último nodo no apunta a nada (None).

Ejemplo resuelto: insertar y eliminar

Partimos de la lista 3 -> 7 -> 9. Insertamos 5 después del 3 y luego eliminamos el 7.

1. Crea un nodo nuevo con el valor 5.
2. Haz que new.next apunte al nodo que sigue al 3 (el nodo 7).
3. Haz que node3.next apunte al nodo nuevo. La lista queda 3 -> 5 -> 7 -> 9.
4. Para eliminar el 7, busca el nodo anterior (el 5) recorriendo desde la cabeza.
5. Asigna node5.next = node5.next.next, que se salta el 7. La lista queda 3 -> 5 -> 9. El recolector de basura de Python libera el nodo inalcanzable.

Implementación en Python de una lista simplemente enlazada

Esta clase guarda una referencia a la cabeza y un contador de tamaño. Permite añadir al principio y al final, eliminar el primer valor que coincida e iterar.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

Aquí push_back recorre toda la lista, por lo que es O(n). Mantener una referencia extra tail lo deja en O(1); es lo que hacen las implementaciones reales de colas.

Operaciones clásicas: invertir y detectar ciclos

Invertir una lista in situ es la pregunta de entrevista más común sobre listas enlazadas. Recorre la lista una vez y da la vuelta a cada puntero next.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle es el algoritmo de la tortuga y la liebre de Floyd: un puntero lento avanza un paso y uno rápido avanza dos. Si hay un bucle, el rápido acaba alcanzando al lento; si no, llega a None. Usa O(1) de memoria adicional.

Complejidad temporal y espacial

En la práctica, los arreglos suelen ser más rápidos incluso en operaciones donde la lista enlazada tiene mejor notación Big O, porque sus elementos están contiguos en memoria y aprovechan bien la caché de la CPU. Los nodos de una lista enlazada están dispersos.

Variantes y errores comunes

• Olvidar la lista vacía: comprueba siempre head is None antes de leer head.next.
• Perder el resto de la lista al sobrescribir next antes de guardarlo (mira nxt en reverse).
• No actualizar head al eliminar el primer nodo, o tail al eliminar el último.
• Usar recursión en listas muy largas: el límite de recursión por defecto de Python es de unos 1000 marcos, así que el código iterativo es más seguro.
• Un nodo cabeza ficticio (centinela) elimina la mayoría de los casos especiales: todo nodo real tiene entonces un nodo anterior.
• En una lista doblemente enlazada, cada inserción y eliminación debe actualizar cuatro referencias; olvidar una corrompe la lista sin avisar.

Cuándo usar una lista enlazada y qué usar en Python

Usa una lista enlazada cuando insertes y elimines en los extremos o en el medio, en posiciones de las que ya tienes una referencia, y rara vez necesites acceso aleatorio. Ejemplos: una caché LRU (lista doblemente enlazada más diccionario hash), la lista de bloques libres de un asignador de memoria, el historial de deshacer o los cubos de una tabla hash.

En el código Python de todos los días rara vez escribirás la tuya. Para una cola o deque, usa collections.deque, que da O(1) al añadir y extraer por ambos extremos. Para secuencias generales, usa list. Escribe tu propia lista enlazada para aprender, para entrevistas y cuando necesites empalmar nodos en O(1), como en una caché LRU.

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]