6 - Operaciones en listas doblemente enlazadas

Control total en ambos sentidos

Las listas doblemente enlazadas en Python incorporan dos referencias en cada nodo: ant y sig. Esto habilita recorridos hacia adelante y hacia atrás y simplifica eliminaciones locales, a cambio de mantener dos enlaces en sincronía. Las siguientes secciones detallan cada operación básica con ejemplos en Python.

class NodoDoble:
    def __init__(self, valor):
        self.valor = valor
        self.ant = None
        self.sig = None


class ListaDoble:
    def __init__(self):
        self.cabeza = None
        self.cola = None

6.1 Inserción al inicio

class ListaDoble:
    # ...
    def insertar_inicio(self, valor):
        nuevo = NodoDoble(valor)
        nuevo.sig = self.cabeza
        if self.cabeza:
            self.cabeza.ant = nuevo
        else:
            self.cola = nuevo
        self.cabeza = nuevo

Si la lista estaba vacía, cabeza y cola apuntan al nuevo nodo; de lo contrario, se enlaza como anterior del que era cabeza.

6.2 Inserción al final

class ListaDoble:
    # ...
    def insertar_final(self, valor):
        nuevo = NodoDoble(valor)
        if self.cola is None:
            self.cabeza = self.cola = nuevo
            return
        nuevo.ant = self.cola
        self.cola.sig = nuevo
        self.cola = nuevo

6.3 Eliminación eficiente

Al conocer el nodo objetivo, se elimina sin recorrer desde la cabeza: solo se actualizan los enlaces de sus vecinos.

class ListaDoble:
    # ...
    def eliminar_nodo(self, nodo):
        if nodo is None:
            return
        if nodo.ant:
            nodo.ant.sig = nodo.sig
        else:
            self.cabeza = nodo.sig
        if nodo.sig:
            nodo.sig.ant = nodo.ant
        else:
            self.cola = nodo.ant
        nodo.ant = nodo.sig = None

Si el nodo es cabeza o cola, se actualizan las referencias globales. En el centro, se enlazan directamente sus vecinos.

6.4 Recorrido hacia adelante

class ListaDoble:
    # ...
    def imprimir(self):
        reco = self.cabeza
        while reco:
            print(reco.valor, end=" -> ")
            reco = reco.sig
        print("None")

6.5 Recorrido hacia atrás

class ListaDoble:
    # ...
    def imprimir_inverso(self):
        reco = self.cola
        while reco:
            print(reco.valor, end=" <- ")
            reco = reco.ant
        print("None")

6.6 Consideraciones cuando la lista está vacía

Mantener sincronizados cabeza y cola es clave. Al eliminar el único nodo, ambas referencias deben quedar en None; al insertar el primero, se inicializan juntas.

  • Verifica ant y sig antes de acceder: pueden ser None.
  • Al limpiar la lista, rompe enlaces para que el recolector libere los nodos.
  • No mezcles funciones pensadas para listas simples; los enlaces dobles requieren mantener dos lados coherentes.

6.7 Código completo listo para ejecutar

Script autocontenido para probar todas las operaciones con python listas_dobles.py.

# listas_dobles.py

class NodoDoble:
    def __init__(self, valor):
        self.valor = valor
        self.ant = None
        self.sig = None


class ListaDoble:
    def __init__(self):
        self.cabeza = None
        self.cola = None

    def insertar_inicio(self, valor):
        nuevo = NodoDoble(valor)
        nuevo.sig = self.cabeza
        if self.cabeza:
            self.cabeza.ant = nuevo
        else:
            self.cola = nuevo
        self.cabeza = nuevo

    def insertar_final(self, valor):
        nuevo = NodoDoble(valor)
        if self.cola is None:
            self.cabeza = self.cola = nuevo
            return
        nuevo.ant = self.cola
        self.cola.sig = nuevo
        self.cola = nuevo

    def eliminar_nodo(self, nodo):
        if nodo is None:
            return
        if nodo.ant:
            nodo.ant.sig = nodo.sig
        else:
            self.cabeza = nodo.sig
        if nodo.sig:
            nodo.sig.ant = nodo.ant
        else:
            self.cola = nodo.ant
        nodo.ant = nodo.sig = None

    def imprimir(self):
        reco = self.cabeza
        while reco:
            print(reco.valor, end=" -> ")
            reco = reco.sig
        print("None")

    def imprimir_inverso(self):
        reco = self.cola
        while reco:
            print(reco.valor, end=" <- ")
            reco = reco.ant
        print("None")

    def limpiar(self):
        while self.cabeza:
            siguiente = self.cabeza.sig
            self.cabeza.ant = None
            self.cabeza.sig = None
            self.cabeza = siguiente
        self.cola = None


def main():
    lista = ListaDoble()
    lista.insertar_inicio(10)
    lista.insertar_final(20)
    lista.insertar_inicio(5)
    print("Recorrido adelante:")
    lista.imprimir()
    print("Recorrido inverso:")
    lista.imprimir_inverso()
    # Eliminar el nodo intermedio (valor 10)
    lista.eliminar_nodo(lista.cabeza.sig)
    print("Tras eliminar el nodo central:")
    lista.imprimir()
    lista.limpiar()


if __name__ == "__main__":
    main()
Ilustración de lista doblemente enlazada

Ejecuta y modifica el script para practicar inserciones y eliminaciones en ambos sentidos con la doble referencia ant/sig.

Ejecutar en editor online
Retornar