Listas enlazadas en Python - Operaciones en listas circulares

Entorno circular

En una lista circular, el último nodo enlaza nuevamente con el primero, creando un recorrido continuo. Esta característica exige precauciones para insertar, eliminar y recorrer sin caer en bucles infinitos. A continuación se describen las operaciones fundamentales en Python.

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


class ListaCircular:
    def __init__(self):
        self.cola = None  # cola.sig apunta al primer nodo

7.1 Inserción conservando la circularidad

class ListaCircular:
    # ...
    def insertar(self, valor):
        nuevo = NodoCircular(valor)
        if self.cola is None:
            nuevo.sig = nuevo
            self.cola = nuevo
            return
        nuevo.sig = self.cola.sig
        self.cola.sig = nuevo
        self.cola = nuevo

Si la lista está vacía, el nodo se enlaza a sí mismo. En caso contrario, se inserta entre la cola y la cabeza para mantener la circularidad.

7.2 Recorrido con condición correcta

class ListaCircular:
    # ...
    def imprimir(self):
        if self.cola is None:
            print("(lista vacia)")
            return
        inicio = self.cola.sig
        reco = inicio
        while True:
            print(reco.valor, end=" -> ")
            reco = reco.sig
            if reco == inicio:
                break
        print("(inicio)")

Se usa un ciclo controlado manualmente: se detiene cuando el cursor vuelve al nodo inicial.

7.3 Eliminación segura

class ListaCircular:
    # ...
    def eliminar(self, valor):
        if self.cola is None:
            return False
        reco = self.cola.sig
        ant = self.cola
        while True:
            if reco.valor == valor:
                if reco == ant:
                    self.cola = None
                else:
                    ant.sig = reco.sig
                    if reco == self.cola:
                        self.cola = ant
                reco.sig = None
                return True
            ant = reco
            reco = reco.sig
            if reco == self.cola.sig:
                break
        return False

Se controlan tres casos: lista vacía, nodo único y nodo en medio o en la cola. Las referencias se actualizan antes de romper el enlace.

7.4 Caso de un único nodo

Cuando la lista solo tiene un nodo, cola y cola.sig apuntan al mismo elemento. El método de eliminación debe reconocerlo para dejar la lista en None tras borrarlo.

7.5 Prevención de loops infinitos

Siempre referencia un nodo inicial antes de recorrer.
No utilices while nodo; en listas circulares no se llega a None.
Tras insertar o eliminar, verifica que cola.sig siga apuntando a la cabeza.

7.6 Código completo listo para ejecutar

Script autocontenido para practicar con python listas_circular.py.

# listas_circular.py

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


class ListaCircular:
    def __init__(self):
        self.cola = None  # cola.sig apunta al primer nodo

    def insertar(self, valor):
        nuevo = NodoCircular(valor)
        if self.cola is None:
            nuevo.sig = nuevo
            self.cola = nuevo
            return
        nuevo.sig = self.cola.sig
        self.cola.sig = nuevo
        self.cola = nuevo

    def eliminar(self, valor):
        if self.cola is None:
            return False
        reco = self.cola.sig
        ant = self.cola
        while True:
            if reco.valor == valor:
                if reco == ant:
                    self.cola = None
                else:
                    ant.sig = reco.sig
                    if reco == self.cola:
                        self.cola = ant
                reco.sig = None
                return True
            ant = reco
            reco = reco.sig
            if reco == self.cola.sig:
                break
        return False

    def imprimir(self):
        if self.cola is None:
            print("(lista vacia)")
            return
        inicio = self.cola.sig
        reco = inicio
        while True:
            print(reco.valor, end=" -> ")
            reco = reco.sig
            if reco == inicio:
                break
        print("(inicio)")

    def limpiar(self):
        if self.cola is None:
            return
        inicio = self.cola.sig
        reco = inicio
        while True:
            siguiente = reco.sig
            reco.sig = None
            if siguiente == inicio:
                break
            reco = siguiente
        self.cola = None


def main():
    lista = ListaCircular()
    for v in (5, 10, 15):
        lista.insertar(v)
    print("Lista circular:")
    lista.imprimir()
    lista.eliminar(10)
    print("Tras eliminar 10:")
    lista.imprimir()
    lista.limpiar()


if __name__ == "__main__":
    main()

Ejecuta, elimina e inserta nodos para validar que la referencia de cola siga enlazando correctamente al inicio.

Ejecutar en editor online

Retornar