El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Listas Circulares

Siguiente ►
►

Todas las listas que hemos construido hasta ahora terminan igual: un último nodo cuyo siguiente es None, la señal de "aquí se acaba" que detiene nuestros recorridos. En esta lección eliminamos esa señal a propósito: el último nodo apuntará al primero, cerrando la cadena en un anillo. El resultado es la lista circular, en sus variantes simple y doble, una estructura hecha a medida de los problemas que no terminan nunca: turnos que rotan, repartos equitativos, procesos que vuelven a empezar. En TaskFlow le daremos su uso natural: el reparto cíclico de tareas entre los miembros del equipo, al estilo round-robin. Pero un anillo sin None es también una trampa: cualquier recorrido escrito "como siempre" (while actual is not None) se convierte en un bucle infinito. Aprender a recorrer con la condición de parada correcta es tan importante aquí como la estructura misma.

Contenido

  1. Cerrar el anillo: qué cambia y qué se rompe
  2. Lista circular simple: implementación con inserción y borrado
  3. Recorridos seguros: condiciones de parada correctas
  4. Round-robin: el reparto cíclico en TaskFlow
  5. Lista circular doble: el anillo con marcha atrás
  6. Cuándo (y cuándo no) usar una lista circular

Cerrar el anillo: qué cambia y qué se rompe

El cambio estructural es una sola flecha: donde la lista simple tenía ultimo.siguiente = None, la circular tiene ultimo.siguiente = primero.

graph LR
    A["Ana"] --> B["Bruno"]
    B --> C["Carla"]
    C -- "la flecha que cierra el anillo" --> A
    U[ultimo] --> C

Consecuencias inmediatas:

  • Ya no existe None como señal de final. Todo recorrido debe inventarse otra condición de parada; de lo contrario, girará eternamente. Es el peligro número uno y le dedicamos una sección entera.
  • Desaparece la distinción "estar al principio / estar al final" en el sentido físico: desde cualquier nodo se alcanza cualquier otro simplemente avanzando. El anillo no tiene extremos, solo un punto de referencia que nosotros decidamos.
  • Basta una sola referencia para gestionarla: guardando self.ultimo, el primero es siempre self.ultimo.siguiente. Dos por el precio de una — así ganamos inserción O(1) por ambos "extremos" sin mantener dos referencias.

Lista circular simple: implementación con inserción y borrado

Reutilizamos la clase Nodo de 02-02 (dato + siguiente); lo que cambia es la contenedora:

class ListaCircular:
    """Lista enlazada circular simple: el último nodo apunta al primero."""
    def __init__(self):
        self.ultimo = None    # referencia al último; el primero es ultimo.siguiente
        self.tamano = 0

    def esta_vacia(self):
        return self.ultimo is None

    def insertar_al_final(self, dato):
        """Añade tras el último y pasa a ser el nuevo último. Coste: O(1)."""
        nuevo = Nodo(dato)
        if self.esta_vacia():
            nuevo.siguiente = nuevo          # ¡se apunta a sí mismo!
            self.ultimo = nuevo
        else:
            nuevo.siguiente = self.ultimo.siguiente   # 1: el nuevo mira al primero
            self.ultimo.siguiente = nuevo             # 2: el antiguo último lo engancha
            self.ultimo = nuevo                       # 3: el último se muda
        self.tamano += 1

    def __len__(self):
        return self.tamano

Detente en el caso de la lista vacía: el primer nodo se apunta a sí mismo (nuevo.siguiente = nuevo). Es el anillo mínimo, de un solo eslabón, y cumple la definición: el último (él) apunta al primero (él). Muchos errores en circulares nacen de tratar mal este caso.

¿Y el insertar_al_inicio? Aquí la circularidad regala una perla: en un anillo, insertar al inicio e insertar al final son exactamente el mismo recableado — el nodo nuevo se engancha siempre entre el último y el primero. La única diferencia es si self.ultimo se muda al nodo nuevo (entonces el nuevo es el último: inserción al final) o se queda donde estaba (entonces el nuevo, al ser "el siguiente del último", es el nuevo primero: inserción al inicio):

    def insertar_al_inicio(self, dato):
        """Añade delante del primero. Coste: O(1)."""
        nuevo = Nodo(dato)
        if self.esta_vacia():
            nuevo.siguiente = nuevo
            self.ultimo = nuevo
        else:
            nuevo.siguiente = self.ultimo.siguiente
            self.ultimo.siguiente = nuevo
            # self.ultimo no se toca: el nuevo queda como primero
        self.tamano += 1

Y el borrado, con su doble caso frontera:

    def borrar(self, condicion):
        """Borra el primer nodo (en orden de recorrido) que cumple la condición.
        Devuelve el dato o None. Coste: O(n)."""
        if self.esta_vacia():
            return None
        anterior = self.ultimo
        actual = self.ultimo.siguiente        # empezamos por el primero
        for _ in range(self.tamano):          # como mucho, una vuelta completa
            if condicion(actual.dato):
                if actual is actual.siguiente:        # único nodo del anillo
                    self.ultimo = None
                else:
                    anterior.siguiente = actual.siguiente   # puente
                    if actual is self.ultimo:               # borramos el último
                        self.ultimo = anterior
                self.tamano -= 1
                return actual.dato
            anterior = actual
            actual = actual.siguiente
        return None
  • El patrón anterior/actual de 02-02 sigue vigente, con una elegancia extra: anterior arranca en self.ultimo, que es exactamente el nodo previo al primero. En una circular, todo nodo tiene anterior; no hay caso especial de cabeza.
  • El caso "único nodo" se detecta con actual is actual.siguiente (se apunta a sí mismo) y vacía la lista.
  • La condición de parada del bucle ya no es None: es contar (for _ in range(self.tamano)), la primera de las técnicas de recorrido seguro que formalizamos a continuación.

Recorridos seguros: condiciones de parada correctas

El error letal en circulares es este:

# ¡NUNCA con una lista circular!
actual = lista.ultimo.siguiente
while actual is not None:      # jamás será None: bucle infinito
    print(actual.dato)
    actual = actual.siguiente

Hay dos técnicas correctas, cada una con su terreno:

Técnica 1 — Contar los nodos (requiere tamano fiable):

    def __iter__(self):
        """Una vuelta completa empezando por el primero. Coste: O(n)."""
        if self.esta_vacia():
            return
        actual = self.ultimo.siguiente
        for _ in range(self.tamano):
            yield actual.dato
            actual = actual.siguiente

Técnica 2 — El nodo centinela: recordar el nodo de partida y parar al volver a verlo:

def una_vuelta(lista):
    """Recorre el anillo exactamente una vez, sin usar tamano."""
    if lista.esta_vacia():
        return
    inicio = lista.ultimo.siguiente
    actual = inicio
    while True:
        print(actual.dato)
        actual = actual.siguiente
        if actual is inicio:      # hemos vuelto al punto de partida: fin
            break
Técnica Requiere Ventaja Riesgo
Contar (range(tamano)) Contador correcto Simple, sin comparaciones de identidad Si tamano está mal, vuelta de más o de menos
Centinela (is inicio) Nada extra Funciona aunque no haya contador Comprobar después de avanzar; con == en vez de is, paradas falsas

Dos detalles del centinela que valen un examen: la comparación va con is (identidad: el mismo nodo, no un dato igual — dos tareas distintas podrían tener datos iguales) y se hace después de avanzar, no antes; si se comprueba al principio del bucle, la condición es cierta en la primera iteración y no se visita nada. El patrón while True + break tras avanzar resuelve ese "hacer al menos una pasada" con claridad.

Round-robin: el reparto cíclico en TaskFlow

El equipo de TaskFlow tiene un problema clásico: repartir las tareas entrantes de forma equitativa y rotatoria entre sus miembros — a cada tarea nueva le toca el siguiente miembro del turno, y después del último se vuelve al primero. Este esquema se llama round-robin y es omnipresente: sistemas operativos repartiendo CPU entre procesos, balanceadores repartiendo peticiones entre servidores, juegos repartiendo turnos entre jugadores. Su estructura natural es el anillo:

class RepartidorTareas:
    """Asigna tareas a los miembros del equipo por turno rotatorio."""
    def __init__(self, nombres):
        self.equipo = ListaCircular()
        for nombre in nombres:
            self.equipo.insertar_al_final(nombre)
        self.turno = self.equipo.ultimo    # el "puntero de turno" sobre el anillo

    def asignar(self, tarea):
        """Asigna la tarea al siguiente miembro del turno. Coste: O(1)."""
        self.turno = self.turno.siguiente       # avanzar el turno (nunca hay final)
        tarea["asignada_a"] = self.turno.dato
        return tarea

    def baja(self, nombre):
        """Un miembro deja el equipo: sale del anillo. Coste: O(n)."""
        if self.turno.dato == nombre:            # no dejar el turno sobre el que se va
            self.turno = self.turno.siguiente
        self.equipo.borrar(lambda d: d == nombre)


reparto = RepartidorTareas(["Ana", "Bruno", "Carla"])

tareas = [{"id": i, "titulo": f"Tarea {i}", "prioridad": 2, "estado": "pendiente"}
          for i in range(1, 8)]
for t in tareas:
    reparto.asignar(t)
    print(f'{t["titulo"]} -> {t["asignada_a"]}')

Salida:

Tarea 1 -> Ana
Tarea 2 -> Bruno
Tarea 3 -> Carla
Tarea 4 -> Ana        ← el anillo vuelve a empezar, sin ningún if
Tarea 5 -> Bruno
Tarea 6 -> Carla
Tarea 7 -> Ana

Lo elegante está en asignar: no hay ninguna comprobación de "¿he llegado al final?". Con una list normal habríamos escrito el clásico indice = (indice + 1) % len(equipo), con su aritmética modular; el anillo hace la vuelta por pura topología: avanzar siempre funciona. Además, altas y bajas del equipo (gente que entra y sale del turno) son las inserciones y borrados baratos que las listas enlazadas nos dan sin desplazar a nadie — con el detalle fino de baja: si el turno estaba sobre quien se marcha, se avanza antes de borrarlo, para no quedarnos apuntando a un nodo fuera del anillo.

Lista circular doble: el anillo con marcha atrás

Si cerramos el anillo sobre nodos dobles (NodoDoble de 02-03), obtenemos la lista circular doble: ultimo.siguiente es el primero y primero.anterior es el último. Todas las flechas correspondidas, ningún None en la estructura.

graph LR
    A["Ana"] -- siguiente --> B["Bruno"]
    B -- anterior --> A
    B -- siguiente --> C["Carla"]
    C -- anterior --> B
    C -- siguiente --> A
    A -- anterior --> C
class ListaCircularDoble:
    """Anillo doblemente enlazado: navegable en ambos sentidos, sin extremos."""
    def __init__(self):
        self.referencia = None    # un nodo cualquiera del anillo ("el primero")
        self.tamano = 0

    def insertar(self, dato):
        """Inserta antes de la referencia (= al final del anillo). Coste: O(1)."""
        nuevo = NodoDoble(dato)
        if self.referencia is None:
            nuevo.siguiente = nuevo      # anillo de un eslabón...
            nuevo.anterior = nuevo       # ...en ambos sentidos
            self.referencia = nuevo
        else:
            ultimo = self.referencia.anterior      # ¡el último es gratis!
            nuevo.anterior = ultimo                # el nuevo mira a ambos lados
            nuevo.siguiente = self.referencia
            ultimo.siguiente = nuevo               # los vecinos le devuelven la mirada
            self.referencia.anterior = nuevo
        self.tamano += 1

    def borrar_nodo(self, nodo):
        """Saca el nodo del anillo. Coste: O(1) dado el nodo."""
        if nodo.siguiente is nodo:           # único eslabón
            self.referencia = None
        else:
            nodo.anterior.siguiente = nodo.siguiente
            nodo.siguiente.anterior = nodo.anterior
            if nodo is self.referencia:
                self.referencia = nodo.siguiente
        self.tamano -= 1
        return nodo.dato

Dos regalos de la circularidad doble:

  • El último es gratis: self.referencia.anterior. En la circular simple, llegar al nodo previo a uno dado costaba una vuelta; aquí es una flecha. Por eso esta clase no necesita guardar ultimo: con una sola referencia tiene ambos "extremos" a un salto.
  • borrar_nodo sin casos de cabeza ni cola: en un anillo doble, todos los nodos son interiores — siempre existen nodo.anterior y nodo.siguiente. Compara con las cuatro ramas de la lista doble lineal de 02-03: aquí solo quedan el caso "único eslabón" y el cuidado de no dejar referencia sobre el nodo saliente. La circularidad, que parecía una complicación, simplifica el borrado.

¿Para qué querría TaskFlow la versión doble? Para un turno rotatorio que también pueda deshacerse: "la tarea 7 se ha cancelado, devuelve el turno a quien lo tenía antes" es self.turno = self.turno.anterior, O(1). Con la circular simple, retroceder un turno costaría una vuelta entera al anillo.

Cuándo (y cuándo no) usar una lista circular

Situación ¿Circular? Por qué
Turnos rotatorios (round-robin, juegos, balanceo) Sí El "después del último, el primero" es la estructura, no un if
Reproducción en bucle (playlist, carrusel, animación cíclica) Sí El recorrido no debe terminar nunca
Buffer que se sobreescribe circularmente Sí (idea emparentada) La cola circular del módulo 4 usa esta misma idea sobre un array
Secuencia con principio y final claros (el tablero de tareas) No El None final es información: "no hay más"; el anillo la destruye
Necesitas recorridos que terminan solos No Toda parada exige contador o centinela: complejidad gratuita

La regla práctica: usa una circular cuando la rotación sea parte del dominio del problema, no como sustituta general de la lista lineal. El tablero de TaskFlow seguirá siendo lineal; el reparto de turnos, circular. Cada estructura en su sitio.

Errores Comunes y Consejos

  • El bucle infinito por while actual is not None. El error definitorio de las circulares. En cuanto una lista es circular, ese patrón queda prohibido: o cuentas nodos o usas centinela. Si tu programa "se cuelga" al recorrer, casi seguro es esto.
  • Comprobar el centinela antes de avanzar. while actual is not inicio como primera línea del bucle no ejecuta ni una iteración (empiezas en inicio). El patrón correcto visita, avanza y entonces compara.
  • Usar == en vez de is con el centinela. Dos nodos distintos pueden contener datos iguales (dos tareas con el mismo título); == pararía en el impostor. La identidad de nodo se comprueba siempre con is.
  • Olvidar el anillo de un eslabón. El nodo que se apunta a sí mismo (en la doble, en ambos sentidos) es el caso frontera de toda circular: insertar el primero y borrar el último deben crearlo y deshacerlo con cuidado. Prueba tus métodos con listas de 0, 1 y 2 nodos, como siempre.
  • Dejar una referencia externa sobre un nodo borrado. El self.turno del repartidor o la self.referencia del anillo doble deben moverse antes de borrar el nodo al que apuntan. Un puntero de turno sobre un nodo fuera del anillo repartirá tareas a un fantasma.
  • Consejo: en las circulares, los diagramas en papel importan aún más que en las lineales: dibuja el anillo, marca la referencia externa y simula el borrado del nodo señalado. Los tres errores anteriores se ven a simple vista en el dibujo.

Ejercicios

Ejercicio 1 — Josephus doméstico. El equipo de TaskFlow sortea quién presenta la demo: puestos en círculo, se cuenta de 3 en 3 y el señalado queda eliminado; gana el último que queda. Escribe superviviente(nombres, k) que, usando ListaCircular (o nodos circulares a mano), elimine cada k-ésima persona y devuelva el nombre de la última. Prueba con ["Ana", "Bruno", "Carla", "David", "Elena"] y k=3. (Este es el problema de Josephus, un clásico con dos mil años de historia.)

Ejercicio 2 — Turno con marcha atrás. Amplía RepartidorTareas para que use ListaCircularDoble y añade el método deshacer_asignacion(), que retrocede el turno una posición en O(1) (la próxima tarea volverá a tocarle a quien iba a tocarle antes de la última asignación). Demuestra con una secuencia: asignar 4 tareas, deshacer una, asignar otra.

Ejercicio 3 — Vueltas contadas. Escribe una función repartir_vueltas(lista_circular, n_vueltas) que recorra el anillo exactamente n_vueltas veces completas usando la técnica del centinela (sin usar tamano), devolviendo la lista de datos visitados. Comprueba con un anillo de 3 elementos y 2 vueltas que devuelve 6 datos y que empieza cada vuelta por el mismo nodo.

Soluciones

Solución 1:

def superviviente(nombres, k):
    """Problema de Josephus sobre un anillo. Coste: O(n·k)."""
    anillo = ListaCircular()
    for nombre in nombres:
        anillo.insertar_al_final(nombre)

    anterior = anillo.ultimo
    actual = anillo.ultimo.siguiente        # el primero
    while len(anillo) > 1:
        for _ in range(k - 1):              # avanzar k-1 puestos
            anterior = actual
            actual = actual.siguiente
        print("Eliminado:", actual.dato)
        anterior.siguiente = actual.siguiente     # puente: sale del anillo
        if actual is anillo.ultimo:
            anillo.ultimo = anterior
        anillo.tamano -= 1
        actual = anterior.siguiente         # el siguiente al eliminado sigue contando
    return anillo.ultimo.dato

print(superviviente(["Ana", "Bruno", "Carla", "David", "Elena"], 3))

Salida: se elimina a Carla, luego Ana, luego Elena, luego Bruno — sobrevive David. Observa que la eliminación usa el puente de siempre (anterior.siguiente = actual.siguiente) y que el anillo hace natural el "seguir contando desde el siguiente": no hay ningún caso especial al pasar por donde estaba el eliminado. Con una list habría que hacer malabares de índices con %; con el anillo, la topología trabaja por nosotros.

Solución 2:

class RepartidorTareasV2:
    def __init__(self, nombres):
        self.equipo = ListaCircularDoble()
        for nombre in nombres:
            self.equipo.insertar(nombre)
        self.turno = self.equipo.referencia.anterior   # así el 1º asignado es el 1º insertado

    def asignar(self, tarea):
        self.turno = self.turno.siguiente      # avanzar: O(1)
        tarea["asignada_a"] = self.turno.dato
        return tarea

    def deshacer_asignacion(self):
        """Devuelve el turno a su posición previa. Coste: O(1)."""
        self.turno = self.turno.anterior       # ¡la flecha 'anterior' en acción!


reparto = RepartidorTareasV2(["Ana", "Bruno", "Carla"])
for i in range(1, 5):
    t = reparto.asignar({"id": i, "titulo": f"T{i}", "prioridad": 2, "estado": "pendiente"})
    print(t["titulo"], "->", t["asignada_a"])   # Ana, Bruno, Carla, Ana
reparto.deshacer_asignacion()                    # el turno retrocede a Carla
t = reparto.asignar({"id": 5, "titulo": "T5", "prioridad": 2, "estado": "pendiente"})
print(t["titulo"], "->", t["asignada_a"])        # T5 -> Ana (le vuelve a tocar)

deshacer_asignacion es una sola asignación gracias a la flecha anterior del anillo doble: exactamente la operación que en la circular simple habría costado una vuelta completa. Es la misma moraleja de 02-03 (la flecha extra compra retrocesos O(1)), ahora en versión anillo.

Solución 3:

def repartir_vueltas(lista_circular, n_vueltas):
    """Recorre el anillo n_vueltas veces con centinela. Sin usar tamano."""
    if lista_circular.esta_vacia() or n_vueltas <= 0:
        return []
    inicio = lista_circular.ultimo.siguiente    # centinela: el primero
    visitados = []
    vueltas = 0
    actual = inicio
    while True:
        visitados.append(actual.dato)
        actual = actual.siguiente
        if actual is inicio:          # comparar DESPUÉS de avanzar, con 'is'
            vueltas += 1
            if vueltas == n_vueltas:
                break
    return visitados

anillo = ListaCircular()
for x in ("A", "B", "C"):
    anillo.insertar_al_final(x)
print(repartir_vueltas(anillo, 2))   # ['A', 'B', 'C', 'A', 'B', 'C']

Seis datos, y cada vuelta arranca en el mismo nodo A: el centinela funciona. Los tres ingredientes del recorrido seguro están a la vista: centinela fijado antes de empezar, comparación con is y comprobación después de avanzar. Cámbiale cualquiera de los tres y tendrás, según el caso, cero iteraciones, paradas falsas o un bucle eterno.

Conclusión

Cerrar el anillo —hacer que el último nodo apunte al primero, y en la versión doble también al revés— convierte la lista en la estructura natural de todo lo rotatorio: el repartidor round-robin de TaskFlow asigna turnos sin aritmética modular ni comprobaciones de final, el problema de Josephus se resuelve con el puente de siempre, y el anillo doble regala el retroceso de turno en O(1) y un borrado sin casos de cabeza ni cola. A cambio, perdimos el None que paraba los recorridos, y aprendimos las dos disciplinas que lo sustituyen: contar nodos o vigilar un centinela con is tras avanzar. Con esto queda completa la familia de las listas: simple, doble y circular, cada una con su tabla de costes y su lugar en TaskFlow. En la próxima lección no habrá teoría nueva: será puro entrenamiento — invertir listas, detectar ciclos con dos punteros, fusionar tableros ordenados por prioridad, mover tareas de posición y rematar el historial navegable — los ejercicios que convierten lo aprendido en oficio, y varios de ellos, clásicos absolutos de entrevista técnica.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados