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

Exercicis amb Llistes

Següent ►
►

Ha arribat l'hora de convertir allò après en ofici. Aquesta lliçó no introdueix teoria nova: és una sessió completa d'entrenament amb sis exercicis progressius que integren tot el mòdul — des de manipular nodes solts fins a muntar peces reals del tauler de TaskFlow amb operacions combinades. Diversos d'ells (invertir una llista enllaçada, detectar cicles amb dues referències, fusionar llistes ordenades) són a més clàssics absoluts d'entrevista tècnica: dominar-los no és només aprovar aquest mòdul, és preparació professional directa. Treballa cada exercici en tres passos: dibuixa els nodes i les fletxes en paper, escriu el codi sense mirar la solució, i prova'l amb llistes de 0, 1, 2 i diversos elements. Només llavors compara amb la solució comentada.

Contingut

  1. Material de partida: les classes del mòdul
  2. Exercici 1 — Comptar i extreure amb nodes solts (escalfament)
  3. Exercici 2 — Invertir una llista enllaçada in situ
  4. Exercici 3 — Detectar un cicle amb dues referències (llebre i tortuga)
  5. Exercici 4 — Fusionar dos taulers ordenats per prioritat
  6. Exercici 5 — Moure una tasca de posició al tauler
  7. Exercici 6 — Historial navegable complet amb llista doble

Material de partida: les classes del mòdul

Tots els exercicis reutilitzen les classes construïdes a les lliçons anteriors; copia-les al teu fitxer de treball tal com van quedar:

  • Node i LlistaEnllacada (lliçó 02-02): cap, cua, mida, amb inserir_al_principi, inserir_al_final, esborrar, cercar, __iter__, __len__, __str__.
  • NodeDoble i LlistaDoblementEnllacada (lliçó 02-03): amb inserir_al_final, esborrar_node, cercar_node, __iter__, __reversed__.
  • La tasca de TaskFlow continua sent el dict de sempre: {"id": ..., "titol": ..., "prioritat": ..., "estat": ...}.

Funció auxiliar per fabricar taulers de prova ràpidament:

def tauler_de(*titols_prioritats):
    """Crea una LlistaEnllacada de tasques: tauler_de(("Logo", 2), ("Hotfix", 1))."""
    tauler = LlistaEnllacada()
    for i, (titol, prioritat) in enumerate(titols_prioritats, start=1):
        tauler.inserir_al_final({"id": i, "titol": titol,
                                 "prioritat": prioritat, "estat": "pendent"})
    return tauler

Errors Comuns i Consells

Abans de començar, les ensopegades que veuràs més vegades en aquests sis exercicis concrets:

  • Perdre la referència a la resta de la llista en recablejar (sobretot a l'exercici 2): tan bon punt reassignes seguent sense haver guardat abans on apuntava, la cua de la llista s'esfuma. La solució universal és una variable temporal que "subjecti" allò que estàs a punt de deixar anar.
  • Descuidar cap, cua i mida en operar amb nodes pel teu compte: si inverteixes o mous nodes manipulant fletxes, les referències estratègiques de la classe han de quedar coherents al final, o el següent inserir_al_final corromprà la llista.
  • Provar només el cas bonic. Llista buida, un node, dos nodes, l'element al cap, l'element a la cua: cada exercici indica les seves fronteres i les solucions les tracten explícitament. Un algorisme de llistes que no has provat a les fronteres no està acabat.
  • Comparar nodes amb == on toca is (exercici 3 especialment): identitat i igualtat no són el mateix, i amb tasques-dict duplicades la diferència és una fallada real.
  • Consell general: als exercicis de recablejat (2, 4 i 5), escriu primer en paper la seqüència numerada d'assignacions i valida sobre el dibuix que cap fletxa necessària no es perd abans de ser copiada. És el mètode de les lliçons anteriors, i aquí és on rendeix.

Exercicis

Exercici 1 — Comptar i extreure amb nodes solts (escalfament). Sense fer servir LlistaEnllacada (només la classe Node i una variable cap), escriu dues funcions: (a) comptar_estat(cap, estat), que retorni quantes tasques de la cadena tenen aquest estat; (b) extreure_completades(cap), que elimini de la cadena totes les tasques amb estat "completada" i retorni el nou cap (compte: les completades poden ser al principi, al mig, al final... o ser-ho totes). Fronteres: cadena buida i cadena on tot s'elimina.

Exercici 2 — Invertir una llista enllaçada in situ. Escriu un mètode invertir() per a LlistaEnllacada que inverteixi l'ordre dels nodes sense crear nodes nous ni estructures auxiliars: només redirigint fletxes seguent. El tauler A -> B -> C ha de quedar C -> B -> A, amb cap, cua i el recorregut coherents. Cost exigit: O(n) en temps i O(1) en espai extra. Pista: recorre amb tres referències (previ, actual, posterior). A TaskFlow: veure el tauler "de les últimes a les primeres" sense construir-ne una còpia.

Exercici 3 — Detectar un cicle amb dues referències (llebre i tortuga). Una errada en programar una llista circular (lliçó 02-04) pot deixar un cicle accidental en un tauler que hauria de ser lineal: el recorregut no acaba mai. Escriu te_cicle(cap) que retorni True/False fent servir l'algorisme de Floyd: dues referències que avancen alhora, una de salt en salt (tortuga) i una altra de dos en dos (llebre); si hi ha cicle, la llebre acabarà atrapant la tortuga; si no, la llebre arribarà a None. Prohibit fer servir memòria auxiliar proporcional a la llista (res de guardar els nodes visitats en un set). Explica en un comentari per què l'algorisme acaba sempre.

Exercici 4 — Fusionar dos taulers ordenats per prioritat. Dos equips fusionen els seus projectes. Cada tauler és una LlistaEnllacada ja ordenada per prioritat ascendent (gràcies a l'inserir_ordenat de l'exercici 2 de la lliçó 02-02). Escriu fusionar(tauler_a, tauler_b) que retorni una nova LlistaEnllacada ordenada amb totes les tasques, reutilitzant els nodes existents (sense crear nodes nous: només recablejant), en O(n + m). En cas d'empat de prioritat, les tasques del tauler A van abans. Fronteres: un o tots dos taulers buits. Nota: els taulers originals queden buits després de la fusió (els seus nodes ara pertanyen al resultat); deixa els seus cap/cua/mida a zero perquè no quedin corruptes.

Exercici 5 — Moure una tasca de posició al tauler. L'usuari arrossega una tasca a una altra posició del tauler (l'operació estrella de qualsevol gestor de tasques). Escriu un mètode moure(self, id_tasca, nova_posicio) per a LlistaEnllacada que localitzi la tasca per id, la desenganxi i la reinsereixi a la posició indicada (0 = principi), reutilitzant el node (sense crear-ne un de nou), i retorni True si existia o False si no. Cuida: moure a la mateixa posició, moure al cap, moure a la cua, id inexistent, i que cap/cua/mida quedin coherents. Quin és el cost?

Exercici 6 — Historial navegable complet amb llista doble. Completa el HistorialTasques de la lliçó 02-03 amb el comportament real d'un navegador: quan l'usuari és a mig historial (després de prémer "enrere") i visita una tasca nova, totes les tasques que quedaven "endavant" es descarten — la nova visita es converteix en el final de l'historial. Afegeix també on_soc() (tasca actual o None) i recorregut() (llista de títols de tot l'historial marcant amb * la posició actual). Fes servir LlistaDoblementEnllacada i esborra els nodes descartats de debò (amb esborrar_node), mantenint mida correcta. Demostra la seqüència: visitar T1, T2, T3, enrere, enrere, visitar T4 → l'historial ha de ser T1, T4.

Solucions

Solució 1:

def comptar_estat(cap, estat):
    """Recorregut clàssic amb comptador. Cost: O(n)."""
    comptador = 0
    actual = cap
    while actual is not None:
        if actual.dada["estat"] == estat:
            comptador += 1
        actual = actual.seguent
    return comptador

def extreure_completades(cap):
    """Elimina totes les tasques completades. Retorna el nou cap. Cost: O(n)."""
    # Fase 1: avançar el cap mentre les primeres estiguin completades
    while cap is not None and cap.dada["estat"] == "completada":
        cap = cap.seguent                # l'antic cap queda sense referències
    # Fase 2: fer pont sobre les completades interiors amb el patró anterior/actual
    anterior = cap
    while anterior is not None and anterior.seguent is not None:
        if anterior.seguent.dada["estat"] == "completada":
            anterior.seguent = anterior.seguent.seguent   # pont
            # (no avancem: el nou següent també podria estar completada)
        else:
            anterior = anterior.seguent
    return cap

Comentaris: la fase 1 resol el cas "completades al principi" (inclòs "totes completades", que retorna None, la cadena buida). A la fase 2, el detall fi és no avançar després de fer pont: si dues completades van seguides, el nou anterior.seguent també s'ha d'examinar. És l'error més freqüent d'aquest exercici: qui avança sempre, se salta una de cada dues completades consecutives.

Solució 2:

    def invertir(self):
        """Inverteix la llista redirigint fletxes. O(n) temps, O(1) espai."""
        previ = None
        actual = self.cap
        self.cua = self.cap              # l'antic cap serà la nova cua
        while actual is not None:
            posterior = actual.seguent   # 1: subjectar la resta abans de deixar-la anar
            actual.seguent = previ       # 2: girar la fletxa
            previ = actual               # 3: avançar previ...
            actual = posterior           # 4: ...i actual
        self.cap = previ                 # l'últim visitat és el nou cap

El cor és el quartet del bucle, sempre en aquest ordre. La línia 1 és la variable temporal que "subjecta" la resta de la llista: sense ella, la línia 2 destruiria l'únic camí cap endavant. Traça-ho a mà amb A -> B -> C:

graph LR
    subgraph "Després de la primera iteració"
    A["A"] -- "fletxa invertida" --> N["None"]
    B["B (actual)"] --> C["C"]
    P["previ"] --> A
    end

Cada iteració gira exactament una fletxa; en esgotar-se actual, previ sosté l'antiga última, que passa a ser el cap. Fronteres: amb llista buida el bucle no s'executa i cap/cua queden None; amb un node, la fletxa A -> None "s'inverteix" sobre si mateixa sense canvis. Verifica amb print(tauler) abans i després.

Solució 3:

def te_cicle(cap):
    """Algorisme de Floyd (llebre i tortuga). O(n) temps, O(1) espai."""
    tortuga = cap
    llebre = cap
    while llebre is not None and llebre.seguent is not None:
        tortuga = tortuga.seguent          # avança 1
        llebre = llebre.seguent.seguent    # avança 2
        if tortuga is llebre:              # identitat, no igualtat!
            return True
    return False
    # Per què acaba sempre? Si no hi ha cicle, la llebre troba None en
    # com a màxim n/2 passos. Si n'hi ha, totes dues referències acaben dins
    # del cicle, i la distància llebre-tortuga es REDUEIX EN 1 a cada pas (la
    # llebre retalla 2−1=1 per iteració sobre un anell finit), així que arriba
    # a 0: es troben, sense que la llebre pugui "saltar per sobre".

Detalls imprescindibles: la condició del while comprova llebre i llebre.seguent abans del doble salt (si no, AttributeError al final d'una llista sense cicle); la comparació és is perquè busquem el mateix node — dues tasques amb dades idèntiques no són un cicle. Prova de foc:

tauler = tauler_de(("Logo", 2), ("Servidor", 2), ("Hotfix", 1))
print(te_cicle(tauler.cap))     # False
tauler.cua.seguent = tauler.cap.seguent   # sabotatge: creem un cicle
print(te_cicle(tauler.cap))     # True
# (desfer el sabotatge abans de continuar fent servir el tauler)
tauler.cua.seguent = None

L'alternativa "apuntar els nodes visitats en un set" també és O(n) en temps, però gasta O(n) de memòria; Floyd aconsegueix el mateix amb dues referències. És l'exemple canònic d'intercanvi temps-memòria resolt amb enginy, i pregunta recurrent d'entrevista.

Solució 4:

def fusionar(tauler_a, tauler_b):
    """Fusiona dues llistes ordenades per prioritat reutilitzant nodes. O(n+m)."""
    resultat = LlistaEnllacada()
    a = tauler_a.cap
    b = tauler_b.cap

    def enganxar(node):
        """Afegeix un node existent al final del resultat (recablejat pur)."""
        node.seguent = None
        if resultat.cap is None:
            resultat.cap = node
        else:
            resultat.cua.seguent = node
        resultat.cua = node
        resultat.mida += 1

    while a is not None and b is not None:
        if a.dada["prioritat"] <= b.dada["prioritat"]:   # <=: en empat guanya A
            seguent = a.seguent      # subjectar abans de recablejar
            enganxar(a)
            a = seguent
        else:
            seguent = b.seguent
            enganxar(b)
            b = seguent

    resta = a if a is not None else b   # una de les dues s'ha esgotat:
    while resta is not None:            # la resta entra en bloc, ja ordenada
        seguent = resta.seguent
        enganxar(resta)
        resta = seguent

    # Els originals cedeixen els seus nodes: deixar-los buits i coherents
    tauler_a.cap = tauler_a.cua = None
    tauler_a.mida = 0
    tauler_b.cap = tauler_b.cua = None
    tauler_b.mida = 0
    return resultat

Claus: a cada volta es compara només la parella de capdavanters i s'enganxa la menor — per això el total és O(n + m), cada node es toca una vegada. El <= (i no <) dona l'estabilitat demanada: en cas d'empat entra primer la d'A. enganxar és un mini-inserir_al_final que rep un node en lloc de crear-ne un: aquí hi ha el "reutilitzar sense crear". I el buidatge final dels originals evita l'error de les dues llistes compartint nodes: si tauler_a conservés el seu cap, modificar el resultat corrompria també A. Prova: fusionar(tauler_de(("Hotfix", 1), ("Logo", 2)), tauler_de(("Caiguda BD", 1), ("Docs", 3))) → Hotfix(A), Caiguda BD(B), Logo, Docs.

Solució 5:

    def moure(self, id_tasca, nova_posicio):
        """Desenganxa la tasca per id i la reinsereix a nova_posicio. O(n)."""
        # Fase 1: localitzar i desenganxar (patró anterior/actual de 02-02)
        anterior = None
        actual = self.cap
        while actual is not None and actual.dada["id"] != id_tasca:
            anterior = actual
            actual = actual.seguent
        if actual is None:
            return False                     # id inexistent
        if anterior is None:
            self.cap = actual.seguent        # era el cap
        else:
            anterior.seguent = actual.seguent
        if actual is self.cua:
            self.cua = anterior              # era la cua
        self.mida -= 1
        actual.seguent = None                # node solt i net

        # Fase 2: reinserir el MATEIX node a la posició demanada
        if nova_posicio <= 0 or self.cap is None:
            actual.seguent = self.cap        # mini inserir_al_principi amb node
            self.cap = actual
            if self.cua is None:
                self.cua = actual
        elif nova_posicio >= self.mida:
            self.cua.seguent = actual        # mini inserir_al_final amb node
            self.cua = actual
        else:
            previ = self.cap
            for _ in range(nova_posicio - 1):
                previ = previ.seguent
            actual.seguent = previ.seguent
            previ.seguent = actual
        self.mida += 1
        return True

Estructura en dues fases netes: desenganxar (que és l'esborrar de 02-02 conservant el node en lloc de deixar-lo anar) i reinserir (que és inserir_a rebent un node en lloc d'una dada). El matís subtil: la posició s'interpreta sobre la llista ja sense la tasca — moure a la mateixa posició funciona sense cas especial, perquè desenganxar i reinserir al mateix lloc és idempotent. Cost O(n): una passada per localitzar més una altra de parcial per situar-se; el recablejat, com sempre, O(1). Prova les quatre fronteres de l'enunciat amb un tauler de 4 tasques i imprimeix el tauler i len després de cadascuna.

Solució 6:

class HistorialTasques:
    """Historial de navegació complet sobre llista doble (TaskFlow)."""
    def __init__(self):
        self.llista = LlistaDoblementEnllacada()
        self.actual = None            # node de la posició actual

    def visitar(self, tasca):
        """Nova visita: descarta l'"endavant" i afegeix al final. O(k) descartats."""
        # Descartar tot el que hi havia després de la posició actual
        if self.actual is not None:
            while self.actual.seguent is not None:
                self.llista.esborrar_node(self.actual.seguent)   # O(1) cadascun
        self.llista.inserir_al_final(tasca)
        self.actual = self.llista.cua

    def enrere(self):
        if self.actual is not None and self.actual.anterior is not None:
            self.actual = self.actual.anterior
        return self.on_soc()

    def endavant(self):
        if self.actual is not None and self.actual.seguent is not None:
            self.actual = self.actual.seguent
        return self.on_soc()

    def on_soc(self):
        return self.actual.dada if self.actual is not None else None

    def recorregut(self):
        """Títols de l'historial, marcant la posició actual amb *."""
        marques = []
        node = self.llista.cap
        while node is not None:
            titol = node.dada["titol"]
            marques.append(f"*{titol}*" if node is self.actual else titol)
            node = node.seguent
        return marques


# Demostració de la seqüència demanada:
def tasca(i):
    return {"id": i, "titol": f"T{i}", "prioritat": 2, "estat": "en curs"}

h = HistorialTasques()
h.visitar(tasca(1)); h.visitar(tasca(2)); h.visitar(tasca(3))
print(h.recorregut())       # ['T1', 'T2', '*T3*']
h.enrere(); h.enrere()
print(h.recorregut())       # ['*T1*', 'T2', 'T3']
h.visitar(tasca(4))
print(h.recorregut())       # ['T1', '*T4*']  ← T2 i T3 descartades
print(len(h.llista))        # 2

Tot el mòdul treballa junt en aquesta classe: el descart fa servir esborrar_node — O(1) per node perquè en tenim la referència, la moralitat de 02-03 —, sempre sobre self.actual.seguent (que es va "reenganxant" sol gràcies als ponts de l'esborrat, sense índexs ni cerques); enrere/endavant són moviments O(1) per les fletxes; i recorregut compara nodes amb is per marcar la posició. És, a petita escala, el mateix disseny de l'historial de Chrome o Firefox: quan navegues des de mig historial, el futur descartat no torna.

Conclusió

Sis exercicis i tot el mòdul en joc: el patró anterior/actual i els ponts (exercici 1), la inversió in situ amb el seu quartet d'assignacions (2), la llebre i la tortuga de Floyd com a detector de cicles en O(1) de memòria (3), la fusió ordenada reutilitzant nodes en O(n + m) (4), el moure-tasca que combina desenganxar i reinserir (5) i l'historial de navegador on els esborrats O(1) de la llista doble rendeixen de debò (6). Si has arribat fins aquí resolent-los —i provant-los a les seves fronteres—, les llistes enllaçades ja no són teoria: són eina. Amb el mòdul 2 complet, TaskFlow té tauler, repartiment de torns i historial, i tu tens el vocabulari de nodes, fletxes i recablejats sobre el qual es construeix gairebé tot el que ve. Al mòdul 3 l'estrenem: la pila, l'estructura de "l'últim d'entrar és el primer de sortir", que podràs implementar en unes poques línies... precisament perquè ja saps inserir i esborrar pel cap d'una llista enllaçada en O(1). El desfer de TaskFlow t'està esperant.

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