2.1 Clase Node

Representa cada elemento de la DLL.

class Node:
    """Nodo de una lista doblemente enlazada."""
    __slots__ = ("value", "prev", "next")   # Reduce uso de memoria
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None
    def __repr__(self):
        return f"Node({self.value!r})"

__slots__ es opcional pero recomendado para listas muy grandes, pues elimina el __dict__ de cada nodo y reduce el consumo de RAM aproximadamente en un 30 %.

2.2 Clase DoublyLinkedList

Contiene la lógica de inserción, borrado, búsqueda y recorridos.

class DoublyLinkedList:
    """Lista doblemente enlazada con API estilo Pythonic."""
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0
    # ---------- Propiedades ----------
    @property
    def size(self):
        return self._size
    def __len__(self):
        return self._size
    def __iter__(self):
        current = self.head
        while current:
            yield current.value
            current = current.next
    def __reversed__(self):
        current = self.tail
        while current:
            yield current.value
            current = current.prev
    # ---------- Operaciones básicas ----------
    def append(self, value):
        """Añade al final (O(1))."""
        new_node = Node(value)
        if not self.head:               # Lista vacía
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1
    def prepend(self, value):
        """Añade al inicio (O(1))."""
        new_node = Node(value)
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self._size += 1
    def insert(self, index, value):
        """Inserta en posición index (O(min(index, n-index)))."""
        if index < 0 or index > self._size:
            raise IndexError("Índice fuera de rango")
        if index == 0:
            self.prepend(value)
            return
        if index == self._size:
            self.append(value)
            return
        # Elegir dirección de recorrido más corta
        if index < self._size // 2:
            cur = self.head
            for _ in range(index):
                cur = cur.next
        else:
            cur = self.tail
            for _ in range(self._size - index):
                cur = cur.prev
        new_node = Node(value)
        prev_node = cur.prev
        # Re‑enlazado
        new_node.prev = prev_node
        new_node.next = cur
        prev_node.next = new_node
        cur.prev = new_node
        self._size += 1
    def remove(self, value):
        """Elimina la primera aparición de value (O(n))."""
        cur = self.head
        while cur:
            if cur.value == value:
                # Caso cabeza
                if cur.prev is None:
                    self.head = cur.next
                    if self.head:
                        self.head.prev = None
                # Caso cola
                elif cur.next is None:
                    self.tail = cur.prev
                    self.tail.next = None
                else:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                self._size -= 1
                return
            cur = cur.next
        raise ValueError(f"{value!r} no está en la lista")
    def pop(self, index=-1):
        """Quita y devuelve el nodo en index (por defecto último)."""
        if self._size == 0:
            raise IndexError("pop de lista vacía")
        if index < 0:
            index = self._size + index
        if not 0 <= index < self._size:
            raise IndexError("Índice fuera de rango")
        # Selección de nodo similar a insert
        if index == 0:
            node = self.head
            self.head = node.next
            if self.head:
                self.head.prev = None
            if node is self.tail:   # Sólo un elemento
                self.tail = None
        elif index == self._size - 1:
            node = self.tail
            self.tail = node.prev
            self.tail.next = None
        else:
            if index < self._size // 2:
                node = self.head
                for _ in range(index):
                    node = node.next
            else:
                node = self.tail
                for _ in range(self._size - index - 1):
                    node = node.prev
            node.prev.next = node.next
            node.next.prev = node.prev
        self._size -= 1
        return node.value
    # ---------- Utilidades ----------
    def clear(self):
        """Vacía la lista (O(1) usando GC)."""
        self.head = self.tail = None
        self._size = 0
    def to_list(self):
        """Convierte a list de Python (útil para debugging)."""
        return list(iter(self))
    def __repr__(self):
        return f"DoublyLinkedList({self.to_list()})"

4.1 Navegador web (historial)

Un historial de navegación necesita poder retroceder (back) y avanzar (forward) en tiempo constante. Cada página visitada se almacena como nodo, mientras que los punteros prev y next permiten cambiar de estado sin recorrer toda la lista.

4.2 Implementación de Undo/Redo

Los editores de texto o gráficos mantienen una cadena de acciones. Con una DLL, undo se mueve al nodo prev y redo al nodo next, logrando O(1) en ambas operaciones.

4.3 Simulación de colas de prioridad con re‑ordenamiento

Cuando una tarea cambia su prioridad, basta con desenlazar el nodo y re‑insertarlo en la posición adecuada, evitando la copia completa que requeriría una list.

4.4 Sistemas de archivos en memoria (VFS)

Algunos VFS utilizan DLL para mantener la lista de bloques libres, permitiendo inserciones y fusiones rápidas de rangos contiguos.