El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

A la lliçó anterior vam encadenar nodes a mà i vam acabar amb expressions tan incòmodes com cap.seguent.seguent.seguent. Avui encapsulem tota aquesta mecànica en una classe LlistaEnllacada que compleix el contracte del TAD llista: inserir (al principi, al final i en una posició), esborrar, cercar, recórrer, i els mètodes màgics __len__ i __str__ perquè es comporti com una estructura de Python de ple dret. A més de construir-la, la sotmetrem al mateix escrutini que tota la resta en aquest curs: anàlisi Big O operació per operació i verificació empírica amb timeit, enfrontant-la a la list de Python just on aquesta fluixejava —inserir per davant—. Al final, el tauler de TaskFlow passarà a viure sobre la nostra nova estructura.

Contingut

Les peces: Node i l'esquelet de LlistaEnllacada
Inserir al principi i al final (i el truc de la cua)
Recórrer, __len__ i __str__
Cercar i inserir en una posició
Esborrar: el patró del node anterior
Anàlisi Big O de totes les operacions
La revenja: timeit contra list inserint per davant
TaskFlow v0.2: el tauler com a llista enllaçada

Les peces: `Node` i l'esquelet de `LlistaEnllacada`

Partim de la classe Node de la lliçó anterior, sense canvis, i hi afegim la classe contenidora que guardarà les referències estratègiques:

class Node:
    """Una dada i la referència al node següent."""
    def __init__(self, dada):
        self.dada = dada
        self.seguent = None


class LlistaEnllacada:
    """Llista enllaçada simple: implementació del TAD llista amb nodes."""
    def __init__(self):
        self.cap = None    # referència al primer node (None = llista buida)
        self.cua = None    # referència a l'últim node (el "truc" anunciat)
        self.mida = 0      # comptador d'elements, mantingut al dia

Tres decisions de disseny que convé entendre abans de continuar:

cap: l'únic punt d'entrada imprescindible. Si és None, la llista és buida.
cua: referència directa a l'últim node. No és obligatòria en una llista enllaçada, però sense ella inserir al final exigiria caminar tota la llista (O(n)); amb ella serà O(1). És el truc que vam deixar anunciat a la taula de 02-01. El preu: cada operació l'ha de mantenir actualitzada, com veurem.
mida: portar el compte en inserir i esborrar costa una suma o una resta (O(1)) i a canvi len(llista) serà instantani, en lloc de recomptar els nodes cada vegada. És el mateix esperit del cost repartit que vam veure amb l'amortitzat: pagar una miqueta a cada operació per no pagar molt de cop.

Una nota sobre la paraula seguent: l'escrivim sense dièresi a propòsit. Tot i que Python admet identificadors amb accents i dièresis, evitar caràcters no ASCII en els noms de codi és una convenció professional estesa (i coherent amb la higiene de noms URL-safe que practica aquest campus).

Inserir al principi i al final (i el truc de la cua)

Inserir al principi: el punt fort

    def inserir_al_principi(self, dada):
        """Afegeix un element davant de tot. Cost: O(1)."""
        nou = Node(dada)
        nou.seguent = self.cap          # 1: el nou apunta a l'antic primer
        self.cap = nou                  # 2: el cap passa a ser el nou
        if self.cua is None:            # 3: si la llista era buida...
            self.cua = nou              #    ...el nou també és l'últim
        self.mida += 1

Pas a pas, amb el diagrama del recablejat:

graph LR
    H[cap] -- "2: es reassigna" --> N["nou"]
    N -- "1: nou.seguent" --> A["antic primer"]
    A --> B["..."]

Línia 1 (nou.seguent = self.cap): el node acabat de crear agafa el que era el primer. Si la llista era buida, self.cap és None i el nou queda correctament com a últim (el seu seguent és None).
Línia 2 (self.cap = nou): la llista passa a començar pel nou. L'ordre d'aquestes dues línies és sagrat: si reassignéssim el cap primer, perdríem l'única referència a la resta de la llista.
Línia 3: cas especial de la llista buida — el nou node és alhora primer i últim.

Compta les operacions: dues assignacions, una comparació, una suma. Cap no depèn de quants elements hi hagi. O(1) de debò, no amortitzat: aquí no hi ha redimensionaments ocasionals com en l'append de l'array.

Inserir al final: la cua en acció

    def inserir_al_final(self, dada):
        """Afegeix un element darrere de tot. Cost: O(1) gràcies a la cua."""
        nou = Node(dada)
        if self.cua is None:            # llista buida: el nou ho és tot
            self.cap = nou
            self.cua = nou
        else:
            self.cua.seguent = nou      # l'antic últim apunta al nou
            self.cua = nou              # la cua passa a ser el nou
        self.mida += 1

Sense la referència cua, aquest mètode hauria de caminar des del cap fins a l'últim node (O(n)) només per enganxar-hi el nou. Amb ella, dues assignacions i llestos. És un exemple perfecte de com una referència extra ben mantinguda canvia la classe de cost d'una operació.

Recórrer, `len` i `str`

El recorregut és el gest que ja coneixes: actual = actual.seguent fins a None. L'oferirem de la manera més pythònica possible, com a generador, per poder escriure for tasca in llista:

    def __iter__(self):
        """Permet: for dada in llista. Recorre en ordre. Cost: O(n)."""
        actual = self.cap
        while actual is not None:
            yield actual.dada           # entrega la dada i fa una pausa aquí
            actual = actual.seguent     # en demanar la següent, avança

    def __len__(self):
        """Permet: len(llista). Cost: O(1) gràcies al comptador."""
        return self.mida

    def __str__(self):
        """Permet: print(llista). Dibuixa la cadena de nodes."""
        textos = []
        for dada in self:               # reutilitzem __iter__
            if isinstance(dada, dict) and "titol" in dada:
                textos.append(f'[{dada["id"]}:{dada["titol"]}]')
            else:
                textos.append(f"[{dada}]")
        return (" -> ".join(textos) + " -> None") if textos else "(buida)"

yield converteix __iter__ en un generador: entrega una dada, es queda "congelat" i continua quan el for demana la següent. Per a l'usuari de la classe, la llista enllaçada es recorre igual que una list.
__str__ reutilitza el mateix __iter__ (res de duplicar el bucle) i té un detall amable amb TaskFlow: si la dada és una tasca-dict, mostra id:titol en lloc del diccionari complet.
La fletxa -> None final no és decorativa: recorda visualment que l'últim node apunta a None.

Cercar i inserir en una posició

Cercar

Cercar per valor no té dreceres: cal mirar node a node. Implementem una cerca per predicat, pensada per a tasques ("dona'm la primera que compleixi aquesta condició"):

    def cercar(self, condicio):
        """Retorna la primera dada que compleix la condició, o None. Cost: O(n)."""
        actual = self.cap
        while actual is not None:
            if condicio(actual.dada):
                return actual.dada
            actual = actual.seguent
        return None

Ús: llista.cercar(lambda t: t["id"] == 42). És el mateix O(n) que cercar en una list; la lliçó 01-02 ja ens va ensenyar que "mirar-ho tot" no escala, i el mòdul 5 portarà l'índex per id que ho arregla. La llista enllaçada no competeix en aquest terreny.

Inserir en una posició

    def inserir_a(self, index, dada):
        """Insereix la dada a la posició index (0 = al principi).
        Cost: O(n) pel camí fins al punt; el recablejat és O(1)."""
        if index <= 0:
            self.inserir_al_principi(dada)
            return
        if index >= self.mida:
            self.inserir_al_final(dada)
            return
        anterior = self.cap
        for _ in range(index - 1):     # caminar fins al node anterior al punt
            anterior = anterior.seguent
        nou = Node(dada)
        nou.seguent = anterior.seguent   # 1: el nou agafa el desplaçat
        anterior.seguent = nou           # 2: l'anterior agafa el nou
        self.mida += 1

Aquí apareix la lletra petita que vam anunciar a 02-01, i convé mirar-la de cara:

Arribar al punt d'inserció costa O(n): cal caminar index - 1 salts.
Recablejar costa O(1): les dues assignacions de sempre, en l'ordre de sempre.

Llavors, on és l'avantatge sobre l'array, si tots dos són O(n) en inserir al mig? En dos llocs. Primer, als extrems: al principi la llista enllaçada és O(1) on l'array és O(n) — aquesta diferència la mesurarem de seguida. Segon, en el matís "si ja hi estem situats": quan un algorisme recorre la llista i decideix inserir o esborrar allà on ja és (com faràs en fusionar llistes ordenades a 02-05), el recablejat O(1) s'aprofita de debò, mentre que l'array pagaria el desplaçament igualment. L'array, en canvi, paga els desplaçaments de memòria sempre, sigui on sigui.

Esborrar: el patró del node anterior

Per esborrar un node cal recablejar el que hi ha abans d'ell... i en una llista enllaçada simple els nodes no saben qui els precedeix (aquesta mancança la resoldrà la llista doble a 02-03). La tècnica estàndard és avançar amb dues referències en paral·lel: anterior i actual.

    def esborrar(self, condicio):
        """Esborra el primer node la dada del qual compleix la condició.
        Retorna la dada esborrada, o None si cap no la compleix. Cost: O(n)."""
        anterior = None
        actual = self.cap
        while actual is not None:
            if condicio(actual.dada):
                if anterior is None:                    # era el primer
                    self.cap = actual.seguent
                else:
                    anterior.seguent = actual.seguent   # fer pont sobre el node
                if actual is self.cua:                  # era l'últim
                    self.cua = anterior
                self.mida -= 1
                return actual.dada
            anterior = actual
            actual = actual.seguent
        return None

graph LR
    A["anterior"] -- "pont nou" --> C["actual.seguent"]
    A -. "fletxa antiga" .-> B["actual (s'esborra)"]
    B -.-> C

Punts delicats, un per un:

Fer pont: anterior.seguent = actual.seguent fa que la cadena "salti per sobre" del node condemnat. Ja ningú no hi apunta, així que el recol·lector de brossa de Python l'allibera. No hi ha del ni alliberament manual: amb deixar anar totes les referències n'hi ha prou.
Esborrar el primer: si anterior encara és None, el node a esborrar és el cap; el pont consisteix a moure self.cap.
Esborrar l'últim: si el condemnat era la cua, cal endarrerir self.cua fins a l'anterior. Oblidar aquest cas deixa una cua fantasma apuntant a un node fora de la llista — un clàssic.
Fem servir is (identitat) i no == per comparar amb self.cua: volem saber si és el mateix node, no un de semblant.

Anàlisi Big O de totes les operacions

La taula promesa a 02-01, ja demostrada mètode a mètode:

Operació	`LlistaEnllacada`	Per què?	`list` de Python
`inserir_al_principi`	O(1)	Recablejar el cap: 2 assignacions	O(n) — ho desplaça tot
`inserir_al_final`	O(1)	Gràcies a la referència `cua`	O(1) amortitzat
`inserir_a(i, x)`	O(n)	Caminar fins a `i` (recablejat O(1))	O(n) — desplaça la resta
`esborrar` (per davant)	O(1)	Moure el cap	O(n) — la trampa de `pop(0)`
`esborrar` (en general)	O(n)	Caminar fins al node	O(n)
`cercar`	O(n)	Mirar node a node	O(n)
Recórrer (`__iter__`)	O(n)	Visita cada node una vegada	O(n)
`len()`	O(1)	Comptador mantingut	O(1)
Accés per índex	O(n)	Sense fórmula: caminar `i` salts	O(1)

La darrera fila és el preu de la dispersió i no s'ha d'amagar: si el teu codi viu de fer tauler[i], la llista enllaçada és una mala elecció. Per això no hem implementat __getitem__: donar sintaxi de claudàtors a una operació O(n) convida a fer-la servir en bucles i fabricar O(n²) sense adonar-se'n.

La revenja: `timeit` contra `list` inserint per davant

A 01-05 vam veure que omplir una list amb insert(0, x) era quadràtic. Repetim aquell experiment amb la nostra estructura a la contesa:

import timeit

def omplir_list_per_davant(n):
    llista = []
    for i in range(n):
        llista.insert(0, i)           # desplaça i elements cada vegada
    return llista

def omplir_enllacada_per_davant(n):
    llista = LlistaEnllacada()
    for i in range(n):
        llista.inserir_al_principi(i) # recableja 2 referències cada vegada
    return llista

for n in (10_000, 50_000, 100_000):
    t_list = timeit.timeit(lambda: omplir_list_per_davant(n), number=3)
    t_enll = timeit.timeit(lambda: omplir_enllacada_per_davant(n), number=3)
    print(f"n={n:>7}: list.insert(0) {t_list:8.3f} s | enllaçada {t_enll:8.3f} s")

Resultat típic (els números exactes varien segons la màquina; la forma no):

n=  10000: list.insert(0)    0.050 s | enllaçada    0.012 s
n=  50000: list.insert(0)    1.3   s | enllaçada    0.06  s
n= 100000: list.insert(0)    5.2   s | enllaçada    0.12  s

La lectura importa més que les xifres:

En duplicar n, la list es quadruplica (cada insert(0) és O(n), el total O(n²)); l'enllaçada es duplica (cada inserció O(1), el total O(n)). Són les corbes de 01-04 en viu i en directe.
Amb n petit la diferència és anecdòtica; amb n gran és abismal. L'escalabilitat, com a l'experiment de 01-02, és el que separa una elecció correcta d'una que "funcionava al meu portàtil".
Honestedat experimental: en operacions on la list és forta (recórrer, append, accés per índex), guanyaria ella, i sovint amb avantatge, perquè l'array contigu aprofita la memòria cau i el seu codi intern està escrit en C. Triar estructura és triar segons l'operació dominant, no segons la guanyadora de l'últim benchmark.

TaskFlow v0.2: el tauler com a llista enllaçada

Tanquem posant la peça al seu lloc. El tauler de TaskFlow, on les urgències entren per davant i les tasques es despatxen per davant, troba per fi la seva estructura:

tauler = LlistaEnllacada()

# Les tasques normals entren pel final (ordre d'arribada)
tauler.inserir_al_final({"id": 1, "titol": "Dissenyar el logo",
                         "prioritat": 2, "estat": "pendent"})
tauler.inserir_al_final({"id": 2, "titol": "Configurar el servidor",
                         "prioritat": 2, "estat": "pendent"})

# Urgència! Entra per davant, en O(1)
tauler.inserir_al_principi({"id": 3, "titol": "Hotfix de producció",
                            "prioritat": 1, "estat": "pendent"})

print(tauler)
# [3:Hotfix de producció] -> [1:Dissenyar el logo] -> [2:Configurar el servidor] -> None

# Es completa una tasca: la localitzem i la retirem
feta = tauler.esborrar(lambda t: t["id"] == 3)
print("Completada:", feta["titol"])     # Completada: Hotfix de producció
print(len(tauler))                      # 2

# Informe del tauler: recorregut natural amb for
for t in tauler:
    print(f'- ({t["prioritat"]}) {t["titol"]} [{t["estat"]}]')

Fixa't que el codi client no esmenta nodes ni referències: parla de tasques, tal com mana la separació TAD-implementació de 01-01. I un avançament: aquest patró de "entrar per un extrem i sortir per un extrem" té noms propis —pila i cua— i estructures dedicades que construirem als mòduls 3 i 4, moltes vegades muntades exactament sobre el que acabes d'escriure.

Errors Comuns i Consells

Recablejar en l'ordre equivocat. Assignar self.cap = nou abans de nou.seguent = self.cap deixa el nou node apuntant-se a si mateix i perd la resta de la llista. Regla mnemotècnica: primer el nou agafa, després l'agafen a ell.
Oblidar actualitzar cua (o mida). Cada mètode que toca l'estructura ha de deixar les tres referències coherents. Un esborrar que no endarrereix la cua quan elimina l'últim node farà que el següent inserir_al_final enganxi el node a un fantasma. Escriu un mètode _comprovar_invariants() en depuració si et passa sovint.
Els casos frontera: llista buida i un sol element. Són la font del 80% de les errades: esborrar l'únic node ha de deixar cap i cua a None; inserir en una llista buida ha de fixar totes dues. Prova sempre els teus mètodes amb llistes de 0, 1 i 2 elements abans que amb 100.
Iterar amb índexs per costum. for i in range(len(llista)): fer_alguna_cosa(element_a(llista, i)) seria O(n²) en una llista enllaçada. Recorre sempre amb for dada in llista (el nostre __iter__), que visita cada node una sola vegada.
Consell: davant de qualsevol dubte amb un recablejat, dibuixa l'abans i el després amb caixes i fletxes, numera les assignacions i només llavors escriu el codi. Cinc minuts de paper estalvien una hora de depurador.

Exercicis

Exercici 1 — comptar_si. Afegeix a LlistaEnllacada un mètode comptar_si(condicio) que retorni quantes dades compleixen la condició, i fes-lo servir per comptar quantes tasques del tauler tenen prioritat == 1. Quin és el seu cost Big O i per què no pot ser millor?

Exercici 2 — inserir_ordenat per prioritat. Afegeix un mètode inserir_ordenat(tasca) que insereixi la tasca mantenint el tauler ordenat per prioritat ascendent (prioritat 1 davant). Pista: és una variant d'inserir_a, però en lloc de comptar salts, camines fins a trobar el primer node amb prioritat més gran. Cuida els tres casos: inserir davant, al mig i al final. Indica el Big O.

Exercici 3 — El preu de l'índex. Implementa una funció externa element_a(llista, i) que retorni la dada de la posició i d'una LlistaEnllacada (o None si no existeix). Després escriu imprimir_malament(llista) que imprimeixi tots els elements fent servir element_a en un bucle sobre range(len(llista)), i imprimir_be(llista) fent servir for dada in llista. Mesura totes dues amb timeit per a n = 2.000 i 4.000 elements i explica el resultat amb Big O.

Solucions

Solució 1:

    def comptar_si(self, condicio):
        """Compta les dades que compleixen la condició. Cost: O(n)."""
        comptador = 0
        actual = self.cap
        while actual is not None:
            if condicio(actual.dada):
                comptador += 1
            actual = actual.seguent
        return comptador

# Ús:
urgents = tauler.comptar_si(lambda t: t["prioritat"] == 1)

És O(n) i no pot ser millor: per comptar quantes compleixen alguna cosa cal examinar-les totes; cap recablejat ni referència extra no evita mirar cada dada almenys una vegada.

Solució 2:

    def inserir_ordenat(self, tasca):
        """Insereix mantenint l'ordre ascendent de prioritat. Cost: O(n)."""
        # Cas 1: buida o la nova va davant (prioritat menor o igual que la primera)
        if self.cap is None or tasca["prioritat"] <= self.cap.dada["prioritat"]:
            self.inserir_al_principi(tasca)
            return
        # Casos 2 i 3: caminar fins a l'últim node amb prioritat <= a la nova
        nou = Node(tasca)
        anterior = self.cap
        while (anterior.seguent is not None
               and anterior.seguent.dada["prioritat"] <= tasca["prioritat"]):
            anterior = anterior.seguent
        nou.seguent = anterior.seguent   # recablejat habitual
        anterior.seguent = nou
        if nou.seguent is None:          # ha quedat l'últim: actualitzar la cua
            self.cua = nou
        self.mida += 1

Comentaris: la condició del while mira anterior.seguent (no anterior) perquè ens hem d'aturar al node previ al punt d'inserció — el patró del node anterior una altra vegada. El cas "va al final" es resol sol: el while acaba amb anterior.seguent a None i el recablejat enganxa al final (sense oblidar la cua). Cost O(n): en el pitjor cas es camina tota la llista. Aquest mètode reapareixerà al mòdul 4 quan parlem de cues de prioritat.

Solució 3:

import timeit

def element_a(llista, i):
    """Retorna la dada de la posició i, o None. Cost: O(n)."""
    if i < 0:
        return None
    actual = llista.cap
    for _ in range(i):
        if actual is None:
            return None
        actual = actual.seguent
    return actual.dada if actual is not None else None

def imprimir_malament(llista):
    for i in range(len(llista)):
        _ = element_a(llista, i)     # cada crida camina des del cap

def imprimir_be(llista):
    for dada in llista:              # un únic recorregut
        _ = dada

for n in (2_000, 4_000):
    llista = LlistaEnllacada()
    for i in range(n):
        llista.inserir_al_final(i)
    t_mal = timeit.timeit(lambda: imprimir_malament(llista), number=5)
    t_be = timeit.timeit(lambda: imprimir_be(llista), number=5)
    print(f"n={n}: amb índexs {t_mal:.3f} s | amb iterador {t_be:.4f} s")

Resultat típic: en duplicar n, imprimir_be es duplica (O(n): un recorregut) però imprimir_malament es quadruplica (O(n²): la crida i-èsima camina i salts, total 0+1+...+(n−1) ≈ n²/2). És exactament la mateixa suma que condemnava insert(0) a l'array, ara del costat de la llista enllaçada: cada estructura té la seva pròpia manera de fabricar O(n²) si es fa servir contra la seva naturalesa.

Conclusió

Ja tens la teva primera estructura construïda des de zero i completa: LlistaEnllacada, amb insercions O(1) a tots dos extrems (cap recablejat, cua mantinguda), esborrat amb el patró del node anterior, cerca per predicat, recorregut com a generador i len/print de ciutadà de primera. L'anàlisi Big O va quedar demostrada i timeit va confirmar la revenja: on insert(0) condemnava la list al quadràtic, la nostra estructura escala linealment — a canvi d'haver renunciat a l'accés per índex O(1), com va delatar l'últim exercici. El tauler de TaskFlow ja viu sobre ella. Però li queda una mancança estructural: cada node coneix el següent i ignora completament l'anterior, cosa que ens va obligar al ball de dues referències per esborrar i ens impedeix recórrer cap enrere. A la propera lliçó afegirem la fletxa que falta —anterior— i obtindrem la llista doblement enllaçada: esborrats O(1) tenint el node, recorreguts en tots dos sentits, i per a TaskFlow un historial de tasques navegable cap endavant i cap enrere.

Llistes Enllaçades

Contingut

Les peces: `Node` i l'esquelet de `LlistaEnllacada`

Inserir al principi i al final (i el truc de la cua)

Inserir al principi: el punt fort

Inserir al final: la cua en acció

Recórrer, `len` i `str`

Cercar i inserir en una posició

Cercar

Inserir en una posició

Esborrar: el patró del node anterior

Anàlisi Big O de totes les operacions

La revenja: `timeit` contra `list` inserint per davant

TaskFlow v0.2: el tauler com a llista enllaçada

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Llistes Enllaçades

Contingut

Les peces: Node i l'esquelet de LlistaEnllacada

Inserir al principi i al final (i el truc de la cua)

Inserir al principi: el punt fort

Inserir al final: la cua en acció

Recórrer, __len__ i __str__

Cercar i inserir en una posició

Cercar

Inserir en una posició

Esborrar: el patró del node anterior

Anàlisi Big O de totes les operacions

La revenja: timeit contra list inserint per davant

TaskFlow v0.2: el tauler com a llista enllaçada

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Taules Hash i Diccionaris

Mòdul 6: Arbres

Mòdul 7: Grafs

Mòdul 8: Conclusions i Recursos Addicionals

Les peces: `Node` i l'esquelet de `LlistaEnllacada`

Recórrer, `len` i `str`

La revenja: `timeit` contra `list` inserint per davant