El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Llistes Circulars

Següent ►
►

Totes les llistes que hem construït fins ara acaben igual: un últim node el seguent del qual és None, el senyal de "aquí s'acaba" que atura els nostres recorreguts. En aquesta lliçó eliminem aquest senyal a propòsit: l'últim node apuntarà al primer, tancant la cadena en un anell. El resultat és la llista circular, en les seves variants simple i doble, una estructura feta a mida dels problemes que no s'acaben mai: torns que roten, repartiments equitatius, processos que tornen a començar. A TaskFlow li donarem el seu ús natural: el repartiment cíclic de tasques entre els membres de l'equip, a l'estil round-robin. Però un anell sense None és també una trampa: qualsevol recorregut escrit "com sempre" (while actual is not None) es converteix en un bucle infinit. Aprendre a recórrer amb la condició d'aturada correcta és tan important aquí com l'estructura mateixa.

Contingut

  1. Tancar l'anell: què canvia i què es trenca
  2. Llista circular simple: implementació amb inserció i esborrat
  3. Recorreguts segurs: condicions d'aturada correctes
  4. Round-robin: el repartiment cíclic a TaskFlow
  5. Llista circular doble: l'anell amb marxa enrere
  6. Quan (i quan no) fer servir una llista circular

Tancar l'anell: què canvia i què es trenca

El canvi estructural és una sola fletxa: on la llista simple tenia ultim.seguent = None, la circular té ultim.seguent = primer.

graph LR
    A["Anna"] --> B["Bruno"]
    B --> C["Carla"]
    C -- "la fletxa que tanca l'anell" --> A
    U[ultim] --> C

Conseqüències immediates:

  • Ja no existeix None com a senyal de final. Tot recorregut s'ha d'inventar una altra condició d'aturada; altrament, girarà eternament. És el perill número u i li dediquem una secció sencera.
  • Desapareix la distinció "ser al principi / ser al final" en el sentit físic: des de qualsevol node s'arriba a qualsevol altre simplement avançant. L'anell no té extrems, només un punt de referència que nosaltres decidim.
  • N'hi ha prou amb una sola referència per gestionar-la: guardant self.ultim, el primer és sempre self.ultim.seguent. Dos pel preu d'un — així guanyem inserció O(1) per tots dos "extrems" sense mantenir dues referències.

Llista circular simple: implementació amb inserció i esborrat

Reutilitzem la classe Node de 02-02 (dada + seguent); el que canvia és la contenidora:

class LlistaCircular:
    """Llista enllaçada circular simple: l'últim node apunta al primer."""
    def __init__(self):
        self.ultim = None    # referència a l'últim; el primer és ultim.seguent
        self.mida = 0

    def esta_buida(self):
        return self.ultim is None

    def inserir_al_final(self, dada):
        """Afegeix darrere de l'últim i passa a ser el nou últim. Cost: O(1)."""
        nou = Node(dada)
        if self.esta_buida():
            nou.seguent = nou            # s'apunta a si mateix!
            self.ultim = nou
        else:
            nou.seguent = self.ultim.seguent   # 1: el nou mira el primer
            self.ultim.seguent = nou           # 2: l'antic últim l'enganxa
            self.ultim = nou                   # 3: l'últim es muda
        self.mida += 1

    def __len__(self):
        return self.mida

Atura't en el cas de la llista buida: el primer node s'apunta a si mateix (nou.seguent = nou). És l'anell mínim, d'una sola baula, i compleix la definició: l'últim (ell) apunta al primer (ell). Molts errors en circulars neixen de tractar malament aquest cas.

I l'inserir_al_principi? Aquí la circularitat regala una perla: en un anell, inserir al principi i inserir al final són exactament el mateix recablejat — el node nou s'enganxa sempre entre l'últim i el primer. L'única diferència és si self.ultim es muda al node nou (llavors el nou és l'últim: inserció al final) o es queda on era (llavors el nou, en ser "el següent de l'últim", és el nou primer: inserció al principi):

    def inserir_al_principi(self, dada):
        """Afegeix davant del primer. Cost: O(1)."""
        nou = Node(dada)
        if self.esta_buida():
            nou.seguent = nou
            self.ultim = nou
        else:
            nou.seguent = self.ultim.seguent
            self.ultim.seguent = nou
            # self.ultim no es toca: el nou queda com a primer
        self.mida += 1

I l'esborrat, amb el seu doble cas frontera:

    def esborrar(self, condicio):
        """Esborra el primer node (en ordre de recorregut) que compleix la condició.
        Retorna la dada o None. Cost: O(n)."""
        if self.esta_buida():
            return None
        anterior = self.ultim
        actual = self.ultim.seguent           # comencem pel primer
        for _ in range(self.mida):            # com a màxim, una volta completa
            if condicio(actual.dada):
                if actual is actual.seguent:        # únic node de l'anell
                    self.ultim = None
                else:
                    anterior.seguent = actual.seguent   # pont
                    if actual is self.ultim:            # esborrem l'últim
                        self.ultim = anterior
                self.mida -= 1
                return actual.dada
            anterior = actual
            actual = actual.seguent
        return None
  • El patró anterior/actual de 02-02 continua vigent, amb una elegància extra: anterior arrenca a self.ultim, que és exactament el node previ al primer. En una circular, tot node té anterior; no hi ha cas especial de cap.
  • El cas "únic node" es detecta amb actual is actual.seguent (s'apunta a si mateix) i buida la llista.
  • La condició d'aturada del bucle ja no és None: és comptar (for _ in range(self.mida)), la primera de les tècniques de recorregut segur que formalitzem tot seguit.

Recorreguts segurs: condicions d'aturada correctes

L'error letal en circulars és aquest:

# MAI amb una llista circular!
actual = llista.ultim.seguent
while actual is not None:      # mai no serà None: bucle infinit
    print(actual.dada)
    actual = actual.seguent

Hi ha dues tècniques correctes, cadascuna amb el seu terreny:

Tècnica 1 — Comptar els nodes (requereix mida fiable):

    def __iter__(self):
        """Una volta completa començant pel primer. Cost: O(n)."""
        if self.esta_buida():
            return
        actual = self.ultim.seguent
        for _ in range(self.mida):
            yield actual.dada
            actual = actual.seguent

Tècnica 2 — El node sentinella: recordar el node de partida i aturar-se en tornar-lo a veure:

def una_volta(llista):
    """Recorre l'anell exactament una vegada, sense fer servir mida."""
    if llista.esta_buida():
        return
    inici = llista.ultim.seguent
    actual = inici
    while True:
        print(actual.dada)
        actual = actual.seguent
        if actual is inici:       # hem tornat al punt de partida: fi
            break
Tècnica Requereix Avantatge Risc
Comptar (range(mida)) Comptador correcte Simple, sense comparacions d'identitat Si mida està malament, volta de més o de menys
Sentinella (is inici) Res extra Funciona encara que no hi hagi comptador Comprovar després d'avançar; amb == en lloc d'is, aturades falses

Dos detalls del sentinella que valen un examen: la comparació va amb is (identitat: el mateix node, no una dada igual — dues tasques diferents podrien tenir dades iguals) i es fa després d'avançar, no abans; si es comprova al començament del bucle, la condició és certa a la primera iteració i no es visita res. El patró while True + break després d'avançar resol aquell "fer almenys una passada" amb claredat.

Round-robin: el repartiment cíclic a TaskFlow

L'equip de TaskFlow té un problema clàssic: repartir les tasques entrants de manera equitativa i rotatòria entre els seus membres — a cada tasca nova li toca el membre següent del torn, i després de l'últim es torna al primer. Aquest esquema es diu round-robin i és omnipresent: sistemes operatius repartint CPU entre processos, balancejadors repartint peticions entre servidors, jocs repartint torns entre jugadors. La seva estructura natural és l'anell:

class RepartidorTasques:
    """Assigna tasques als membres de l'equip per torn rotatori."""
    def __init__(self, noms):
        self.equip = LlistaCircular()
        for nom in noms:
            self.equip.inserir_al_final(nom)
        self.torn = self.equip.ultim    # la "referència de torn" sobre l'anell

    def assignar(self, tasca):
        """Assigna la tasca al membre següent del torn. Cost: O(1)."""
        self.torn = self.torn.seguent           # avançar el torn (mai no hi ha final)
        tasca["assignada_a"] = self.torn.dada
        return tasca

    def baixa(self, nom):
        """Un membre deixa l'equip: surt de l'anell. Cost: O(n)."""
        if self.torn.dada == nom:               # no deixar el torn sobre qui se'n va
            self.torn = self.torn.seguent
        self.equip.esborrar(lambda d: d == nom)


repartiment = RepartidorTasques(["Anna", "Bruno", "Carla"])

tasques = [{"id": i, "titol": f"Tasca {i}", "prioritat": 2, "estat": "pendent"}
           for i in range(1, 8)]
for t in tasques:
    repartiment.assignar(t)
    print(f'{t["titol"]} -> {t["assignada_a"]}')

Sortida:

Tasca 1 -> Anna
Tasca 2 -> Bruno
Tasca 3 -> Carla
Tasca 4 -> Anna        ← l'anell torna a començar, sense cap if
Tasca 5 -> Bruno
Tasca 6 -> Carla
Tasca 7 -> Anna

L'elegant és a assignar: no hi ha cap comprovació de "he arribat al final?". Amb una list normal hauríem escrit el clàssic index = (index + 1) % len(equip), amb la seva aritmètica modular; l'anell fa la volta per pura topologia: avançar sempre funciona. A més, altes i baixes de l'equip (gent que entra i surt del torn) són les insercions i esborrats barats que les llistes enllaçades ens donen sense desplaçar ningú — amb el detall fi de baixa: si el torn era sobre qui se'n va, s'avança abans d'esborrar-lo, per no quedar-nos apuntant a un node fora de l'anell.

Llista circular doble: l'anell amb marxa enrere

Si tanquem l'anell sobre nodes dobles (NodeDoble de 02-03), obtenim la llista circular doble: ultim.seguent és el primer i primer.anterior és l'últim. Totes les fletxes correspostes, cap None a l'estructura.

graph LR
    A["Anna"] -- seguent --> B["Bruno"]
    B -- anterior --> A
    B -- seguent --> C["Carla"]
    C -- anterior --> B
    C -- seguent --> A
    A -- anterior --> C
class LlistaCircularDoble:
    """Anell doblement enllaçat: navegable en tots dos sentits, sense extrems."""
    def __init__(self):
        self.referencia = None    # un node qualsevol de l'anell ("el primer")
        self.mida = 0

    def inserir(self, dada):
        """Insereix abans de la referència (= al final de l'anell). Cost: O(1)."""
        nou = NodeDoble(dada)
        if self.referencia is None:
            nou.seguent = nou            # anell d'una sola baula...
            nou.anterior = nou           # ...en tots dos sentits
            self.referencia = nou
        else:
            ultim = self.referencia.anterior       # l'últim és gratis!
            nou.anterior = ultim                   # el nou mira a banda i banda
            nou.seguent = self.referencia
            ultim.seguent = nou                    # els veïns li tornen la mirada
            self.referencia.anterior = nou
        self.mida += 1

    def esborrar_node(self, node):
        """Treu el node de l'anell. Cost: O(1) donat el node."""
        if node.seguent is node:             # única baula
            self.referencia = None
        else:
            node.anterior.seguent = node.seguent
            node.seguent.anterior = node.anterior
            if node is self.referencia:
                self.referencia = node.seguent
        self.mida -= 1
        return node.dada

Dos regals de la circularitat doble:

  • L'últim és gratis: self.referencia.anterior. A la circular simple, arribar al node previ d'un de donat costava una volta; aquí és una fletxa. Per això aquesta classe no necessita guardar ultim: amb una sola referència té tots dos "extrems" a un salt.
  • esborrar_node sense casos de cap ni cua: en un anell doble, tots els nodes són interiors — sempre existeixen node.anterior i node.seguent. Compara amb les quatre branques de la llista doble lineal de 02-03: aquí només queden el cas "única baula" i la cura de no deixar referencia sobre el node sortint. La circularitat, que semblava una complicació, simplifica l'esborrat.

Per a què voldria TaskFlow la versió doble? Per a un torn rotatori que també es pugui desfer: "la tasca 7 s'ha cancel·lat, torna el torn a qui el tenia abans" és self.torn = self.torn.anterior, O(1). Amb la circular simple, retrocedir un torn costaria una volta sencera a l'anell.

Quan (i quan no) fer servir una llista circular

Situació Circular? Per què
Torns rotatoris (round-robin, jocs, balanceig) Sí El "després de l'últim, el primer" és l'estructura, no un if
Reproducció en bucle (playlist, carrusel, animació cíclica) Sí El recorregut no ha d'acabar mai
Buffer que se sobreescriu circularment Sí (idea emparentada) La cua circular del mòdul 4 fa servir aquesta mateixa idea sobre un array
Seqüència amb principi i final clars (el tauler de tasques) No El None final és informació: "no n'hi ha més"; l'anell la destrueix
Necessites recorreguts que acaben sols No Tota aturada exigeix comptador o sentinella: complexitat gratuïta

La regla pràctica: fes servir una circular quan la rotació sigui part del domini del problema, no com a substituta general de la llista lineal. El tauler de TaskFlow continuarà sent lineal; el repartiment de torns, circular. Cada estructura al seu lloc.

Errors Comuns i Consells

  • El bucle infinit per while actual is not None. L'error definitori de les circulars. Tan bon punt una llista és circular, aquest patró queda prohibit: o comptes nodes o fas servir sentinella. Si el teu programa "es penja" en recórrer, gairebé segur que és això.
  • Comprovar el sentinella abans d'avançar. while actual is not inici com a primera línia del bucle no executa ni una iteració (comences a inici). El patró correcte visita, avança i llavors compara.
  • Fer servir == en lloc d'is amb el sentinella. Dos nodes diferents poden contenir dades iguals (dues tasques amb el mateix títol); == s'aturaria a l'impostor. La identitat de node es comprova sempre amb is.
  • Oblidar l'anell d'una sola baula. El node que s'apunta a si mateix (a la doble, en tots dos sentits) és el cas frontera de tota circular: inserir el primer i esborrar l'últim l'han de crear i desfer amb cura. Prova els teus mètodes amb llistes de 0, 1 i 2 nodes, com sempre.
  • Deixar una referència externa sobre un node esborrat. El self.torn del repartidor o la self.referencia de l'anell doble s'han de moure abans d'esborrar el node al qual apunten. Una referència de torn sobre un node fora de l'anell repartirà tasques a un fantasma.
  • Consell: en les circulars, els diagrames en paper importen encara més que en les lineals: dibuixa l'anell, marca la referència externa i simula l'esborrat del node assenyalat. Els tres errors anteriors es veuen a simple vista en el dibuix.

Exercicis

Exercici 1 — Josephus domèstic. L'equip de TaskFlow sorteja qui presenta la demo: posats en cercle, es compta de 3 en 3 i l'assenyalat queda eliminat; guanya l'últim que queda. Escriu supervivent(noms, k) que, fent servir LlistaCircular (o nodes circulars a mà), elimini cada k-èsima persona i retorni el nom de l'última. Prova amb ["Anna", "Bruno", "Carla", "David", "Elena"] i k=3. (Aquest és el problema de Josephus, un clàssic amb dos mil anys d'història.)

Exercici 2 — Torn amb marxa enrere. Amplia RepartidorTasques perquè faci servir LlistaCircularDoble i afegeix-hi el mètode desfer_assignacio(), que retrocedeix el torn una posició en O(1) (la pròxima tasca tornarà a tocar a qui li anava a tocar abans de l'última assignació). Demostra-ho amb una seqüència: assignar 4 tasques, desfer-ne una, assignar-ne una altra.

Exercici 3 — Voltes comptades. Escriu una funció repartir_voltes(llista_circular, n_voltes) que recorri l'anell exactament n_voltes vegades completes fent servir la tècnica del sentinella (sense fer servir mida), retornant la llista de dades visitades. Comprova amb un anell de 3 elements i 2 voltes que retorna 6 dades i que comença cada volta pel mateix node.

Solucions

Solució 1:

def supervivent(noms, k):
    """Problema de Josephus sobre un anell. Cost: O(n·k)."""
    anell = LlistaCircular()
    for nom in noms:
        anell.inserir_al_final(nom)

    anterior = anell.ultim
    actual = anell.ultim.seguent            # el primer
    while len(anell) > 1:
        for _ in range(k - 1):              # avançar k-1 llocs
            anterior = actual
            actual = actual.seguent
        print("Eliminat:", actual.dada)
        anterior.seguent = actual.seguent   # pont: surt de l'anell
        if actual is anell.ultim:
            anell.ultim = anterior
        anell.mida -= 1
        actual = anterior.seguent           # el següent a l'eliminat continua comptant
    return anell.ultim.dada

print(supervivent(["Anna", "Bruno", "Carla", "David", "Elena"], 3))

Sortida: s'elimina la Carla, després l'Anna, després l'Elena, després en Bruno — sobreviu en David. Observa que l'eliminació fa servir el pont de sempre (anterior.seguent = actual.seguent) i que l'anell fa natural el "continuar comptant des del següent": no hi ha cap cas especial en passar per on era l'eliminat. Amb una list caldria fer malabarismes d'índexs amb %; amb l'anell, la topologia treballa per nosaltres.

Solució 2:

class RepartidorTasquesV2:
    def __init__(self, noms):
        self.equip = LlistaCircularDoble()
        for nom in noms:
            self.equip.inserir(nom)
        self.torn = self.equip.referencia.anterior   # així el 1r assignat és el 1r inserit

    def assignar(self, tasca):
        self.torn = self.torn.seguent          # avançar: O(1)
        tasca["assignada_a"] = self.torn.dada
        return tasca

    def desfer_assignacio(self):
        """Torna el torn a la posició prèvia. Cost: O(1)."""
        self.torn = self.torn.anterior         # la fletxa 'anterior' en acció!


repartiment = RepartidorTasquesV2(["Anna", "Bruno", "Carla"])
for i in range(1, 5):
    t = repartiment.assignar({"id": i, "titol": f"T{i}", "prioritat": 2, "estat": "pendent"})
    print(t["titol"], "->", t["assignada_a"])   # Anna, Bruno, Carla, Anna
repartiment.desfer_assignacio()                  # el torn retrocedeix fins a la Carla
t = repartiment.assignar({"id": 5, "titol": "T5", "prioritat": 2, "estat": "pendent"})
print(t["titol"], "->", t["assignada_a"])        # T5 -> Anna (li torna a tocar)

desfer_assignacio és una sola assignació gràcies a la fletxa anterior de l'anell doble: exactament l'operació que a la circular simple hauria costat una volta completa. És la mateixa moralitat de 02-03 (la fletxa extra compra retrocessos O(1)), ara en versió anell.

Solució 3:

def repartir_voltes(llista_circular, n_voltes):
    """Recorre l'anell n_voltes vegades amb sentinella. Sense fer servir mida."""
    if llista_circular.esta_buida() or n_voltes <= 0:
        return []
    inici = llista_circular.ultim.seguent    # sentinella: el primer
    visitats = []
    voltes = 0
    actual = inici
    while True:
        visitats.append(actual.dada)
        actual = actual.seguent
        if actual is inici:           # comparar DESPRÉS d'avançar, amb 'is'
            voltes += 1
            if voltes == n_voltes:
                break
    return visitats

anell = LlistaCircular()
for x in ("A", "B", "C"):
    anell.inserir_al_final(x)
print(repartir_voltes(anell, 2))   # ['A', 'B', 'C', 'A', 'B', 'C']

Sis dades, i cada volta arrenca al mateix node A: el sentinella funciona. Els tres ingredients del recorregut segur són a la vista: sentinella fixat abans de començar, comparació amb is i comprovació després d'avançar. Canvia'n qualsevol dels tres i tindràs, segons el cas, zero iteracions, aturades falses o un bucle etern.

Conclusió

Tancar l'anell —fer que l'últim node apunti al primer, i en la versió doble també a la inversa— converteix la llista en l'estructura natural de tot allò rotatori: el repartidor round-robin de TaskFlow assigna torns sense aritmètica modular ni comprovacions de final, el problema de Josephus es resol amb el pont de sempre, i l'anell doble regala el retrocés de torn en O(1) i un esborrat sense casos de cap ni cua. A canvi, vam perdre el None que aturava els recorreguts, i vam aprendre les dues disciplines que el substitueixen: comptar nodes o vigilar un sentinella amb is després d'avançar. Amb això queda completa la família de les llistes: simple, doble i circular, cadascuna amb la seva taula de costos i el seu lloc a TaskFlow. A la propera lliçó no hi haurà teoria nova: serà pur entrenament — invertir llistes, detectar cicles amb dues referències, fusionar taulers ordenats per prioritat, moure tasques de posició i rematar l'historial navegable — els exercicis que converteixen allò après en ofici, i diversos d'ells, clàssics absoluts d'entrevista tècnica.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats