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

HOME

La llista enllaçada simple que vam construir a la lliçó anterior té una asimetria incòmoda: cada node sap qui ve després, però ignora completament qui ve abans. Aquesta ceguesa ens va obligar al ball de dues referències (anterior i actual) per esborrar, i fa directament impossible recórrer la llista cap enrere. En aquesta lliçó afegim la fletxa que falta: cada node portarà dues referències, anterior i seguent, i obtindrem la llista doblement enllaçada, amb esborrats i insercions O(1) quan ja tenim el node a la mà i recorreguts en tots dos sentits. El preu, com sempre, existeix i el posarem a la balança. Per a TaskFlow, aquesta estructura és la peça perfecta per a un historial de tasques navegable: avançar i retrocedir per les tasques treballades, com els botons "enrere" i "endavant" d'un navegador.

Contingut

El node doble: dues fletxes per node
Cap i cua: l'estructura i els seus invariants
Inserir per tots dos extrems
Inserir i esborrar O(1) donat el node
Recórrer en tots dos sentits
Simple vs doble: la balança completa
TaskFlow: l'historial de tasques navegable
Un pont cap a collections.deque

El node doble: dues fletxes per node

La modificació és petita d'escriure i gran de conseqüències:

class NodeDoble:
    """Una dada i dues referències: al node anterior i al següent."""
    def __init__(self, dada):
        self.dada = dada
        self.anterior = None    # referència al node previ (None = és el primer)
        self.seguent = None     # referència al node posterior (None = és l'últim)

graph LR
    H[cap] --> A
    A["tasca 1"] -- seguent --> B["tasca 2"]
    B -- anterior --> A
    B -- seguent --> C["tasca 3"]
    C -- anterior --> B
    T[cua] --> C

Cada parella de nodes veïns està unida per dues fletxes, una en cada sentit. D'aquí es deriven les dues propietats noves:

Des de qualsevol node es pot caminar cap enrere (actual = actual.anterior), no només cap endavant.
Qualsevol node coneix el seu veí previ sense cercar-lo: el patró del node anterior de 02-02 deixa de ser necessari.

I la servitud nova: cada operació ha de mantenir coherents el doble de fletxes. On la llista simple recablejava 2 referències, la doble en recableja fins a 4. Cap operació no canvia de classe de cost per això (recablejar continua sent O(1)), però el codi té més punts on equivocar-se, i ho veurem.

Cap i cua: l'estructura i els seus invariants

class LlistaDoblementEnllacada:
    """Llista doblement enllaçada: es pot recórrer en tots dos sentits."""
    def __init__(self):
        self.cap = None    # primer node
        self.cua = None    # últim node
        self.mida = 0

A la llista simple, la cua era un truc opcional per abaratir inserir_al_final. Aquí és part essencial del disseny: sense ella no hi hauria per on començar el recorregut cap enrere. Convé fixar per escrit els invariants — les condicions que tot mètode ha de deixar certes en acabar:

self.cap.anterior és sempre None (ningú no precedeix el primer).
self.cua.seguent és sempre None (ningú no segueix l'últim).
Si la llista és buida, cap i cua són totes dues None; si té un element, totes dues apunten al mateix node.
Per a tot node interior n: n.seguent.anterior is n i n.anterior.seguent is n (les fletxes d'anada i tornada es corresponen).

Quan un mètode deixa les fletxes incoherents, els símptomes apareixen lluny del culpable (un recorregut cap enrere que es talla, un esborrat que ressuscita nodes). Comprovar mentalment els invariants després d'escriure cada mètode és la millor assegurança.

Inserir per tots dos extrems

La simetria de l'estructura es reflecteix en el codi: els dos mètodes són mirall l'un de l'altre.

    def inserir_al_principi(self, dada):
        """Cost: O(1)."""
        nou = NodeDoble(dada)
        if self.cap is None:             # llista buida
            self.cap = nou
            self.cua = nou
        else:
            nou.seguent = self.cap           # 1: el nou mira l'antic primer
            self.cap.anterior = nou          # 2: l'antic primer mira el nou
            self.cap = nou                   # 3: el cap es muda
        self.mida += 1

    def inserir_al_final(self, dada):
        """Cost: O(1)."""
        nou = NodeDoble(dada)
        if self.cua is None:             # llista buida
            self.cap = nou
            self.cua = nou
        else:
            nou.anterior = self.cua          # mirall exacte del mètode anterior
            self.cua.seguent = nou
            self.cua = nou
        self.mida += 1

Fixa't en el pas 2 d'inserir_al_principi, que no existia a la llista simple: l'antic primer node ha de tornar la mirada al nou (self.cap.anterior = nou). És l'assignació extra que manté l'invariant de les fletxes correspostes. Oblidar-la no trenca el recorregut cap endavant —l'errada queda amagada— però talla el recorregut cap enrere just en aquell punt: el tipus d'error silenciós més difícil de depurar.

Inserir i esborrar O(1) donat el node

Aquí hi ha el titular de la lliçó, i cal llegir-lo amb la seva lletra petita: tenint una referència al node, esborrar (o inserir al seu costat) és O(1) pur, sense caminar la llista ni cercar l'anterior — el node ja el porta amb ell.

    def esborrar_node(self, node):
        """Desenganxa el node donat. Cost: O(1) — no cerca, recableja."""
        if node.anterior is not None:
            node.anterior.seguent = node.seguent   # pont cap endavant
        else:
            self.cap = node.seguent                # era el primer
        if node.seguent is not None:
            node.seguent.anterior = node.anterior  # pont cap enrere
        else:
            self.cua = node.anterior               # era l'últim
        node.anterior = None      # higiene: el node solt no reté la llista
        node.seguent = None
        self.mida -= 1
        return node.dada

    def inserir_despres(self, node, dada):
        """Insereix una dada just després del node donat. Cost: O(1)."""
        if node is self.cua:
            self.inserir_al_final(dada)
            return
        nou = NodeDoble(dada)
        nou.anterior = node                # 1: el nou mira a banda i banda
        nou.seguent = node.seguent
        node.seguent.anterior = nou        # 2: els veïns li tornen la mirada
        node.seguent = nou
        self.mida += 1

graph LR
    A["anterior"] -- "pont seguent" --> C["seguent"]
    C -- "pont anterior" --> A
    A -.-> B["node esborrat"]
    B -.-> C

Detalls que marquen la diferència:

esborrar_node construeix dos ponts, un per sentit, i cadascun té el seu cas frontera (primer/últim). Quatre branques, totes necessàries.
Les dues línies d'"higiene" (node.anterior = None, etc.) eviten que un node ja retirat continuï retenint referències a la llista viva — i de passada, que algú el faci servir com a punt de partida d'un recorregut fantasma.
Compara amb la llista simple: allà, esborrar exigia haver arribat amb la parella anterior/actual (O(n) de cerca prèvia llevat del cap). Aquí, si has guardat la referència al node (per exemple, el node de l'historial on ets situat), l'esborrat és instantani. L'avantatge només es materialitza si conserves referències a nodes; si sempre comences cercant des del cap, la llista doble no t'estalvia la cerca O(n).

Recórrer en tots dos sentits

    def __iter__(self):
        """Recorregut cap endavant: for dada in llista. Cost: O(n)."""
        actual = self.cap
        while actual is not None:
            yield actual.dada
            actual = actual.seguent

    def __reversed__(self):
        """Recorregut cap enrere: for dada in reversed(llista). Cost: O(n)."""
        actual = self.cua
        while actual is not None:
            yield actual.dada
            actual = actual.anterior

    def __len__(self):
        return self.mida

    def __str__(self):
        textos = [f'[{d["id"]}:{d["titol"]}]' if isinstance(d, dict) and "titol" in d
                  else f"[{d}]" for d in self]
        return " <-> ".join(textos) if textos else "(buida)"

__reversed__ és el mètode màgic que Python invoca en escriure reversed(llista): comencem per la cua i caminem per les fletxes anterior. A la llista simple aquest mètode era senzillament impossible d'escriure amb un cost raonable (caldria anar a buscar l'anterior de cada node, O(n²), o copiar la llista sencera). El separador <-> de __str__ recorda que ara les fletxes van en tots dos sentits.

Simple vs doble: la balança completa

Criteri	Llista enllaçada simple	Llista doblement enllaçada
Referències per node	1 (`seguent`)	2 (`anterior` i `seguent`)
Memòria extra per node	Una fletxa	Dues fletxes (~un 30-50% més de sobrecost per node)
Recorregut cap endavant	O(n)	O(n)
Recorregut cap enrere	Impracticable	O(n)
Esborrar tenint el node	O(n) — cal localitzar l'anterior	O(1)
Inserir al costat d'un node donat	O(1) només després; abans exigeix cercar	O(1) a banda i banda
Inserir/esborrar als extrems	O(1) (amb cua)	O(1)
Fletxes a mantenir per operació	2	Fins a 4 (més casos frontera)
Complexitat del codi	Menor	Major (més punts d'error)

Quan triar cadascuna?

Simple: quan només s'avança en un sentit i les modificacions es concentren als extrems o durant un recorregut cap endavant. Menys memòria, menys codi, menys errors possibles.
Doble: quan cal navegar cap enrere, o esborrar/moure elements a partir de referències guardades als seus nodes. L'historial que ve ara és el cas canònic.

TaskFlow: l'historial de tasques navegable

Cada vegada que un membre de l'equip obre una tasca, TaskFlow l'anota al seu historial. L'usuari vol moure's per aquest historial com per les pàgines d'un navegador: enrere i endavant. Amb la llista doble, l'historial és l'estructura i la posició actual és simplement una referència a un node:

class HistorialTasques:
    """Historial navegable de tasques visitades, sobre una llista doble."""
    def __init__(self):
        self.llista = LlistaDoblementEnllacada()
        self.actual = None                    # node on estem situats

    def visitar(self, tasca):
        """L'usuari obre una tasca: s'anota al final i ens hi situem."""
        self.llista.inserir_al_final(tasca)
        self.actual = self.llista.cua         # el node acabat de crear

    def enrere(self):
        """Retrocedeix una posició, si es pot. Cost: O(1)."""
        if self.actual is not None and self.actual.anterior is not None:
            self.actual = self.actual.anterior
        return self.actual.dada if self.actual else None

    def endavant(self):
        """Avança una posició, si es pot. Cost: O(1)."""
        if self.actual is not None and self.actual.seguent is not None:
            self.actual = self.actual.seguent
        return self.actual.dada if self.actual else None


historial = HistorialTasques()
historial.visitar({"id": 1, "titol": "Dissenyar el logo", "prioritat": 2, "estat": "en curs"})
historial.visitar({"id": 2, "titol": "Configurar el servidor", "prioritat": 2, "estat": "en curs"})
historial.visitar({"id": 3, "titol": "Hotfix de producció", "prioritat": 1, "estat": "en curs"})

print(historial.enrere()["titol"])      # Configurar el servidor
print(historial.enrere()["titol"])      # Dissenyar el logo
print(historial.endavant()["titol"])    # Configurar el servidor

Punts per assaborir:

enrere() i endavant() són O(1) purs: moure una referència per una fletxa. Amb una llista simple, enrere() hauria exigit recórrer des del cap fins al node previ — O(n) per pulsació de botó.
self.actual és la materialització de "l'avantatge només val si conserves referències a nodes": l'historial viu precisament de guardar-ne una.
Les comprovacions is not None en cadena eviten tant l'historial buit com sortir-se pels extrems: a la primera i l'última tasca, els botons simplement no es mouen.

A 02-05 completaràs aquest historial amb un matís clàssic dels navegadors: què passa amb les tasques "endavant" quan en visites una de nova des de mig historial.

Un pont cap a `collections.deque`

Al mòdul 1 va quedar sembrada la menció a collections.deque, i ara ja pots entendre el seu carnet d'identitat: deque està implementada en C com una estructura doblement enllaçada per blocs — no un node per element, sinó nodes que són blocs de 64 forats enllaçats entre ells en tots dos sentits. Aquesta hibridació li dona insercions i esborrats O(1) per tots dos extrems amb molt menys sobrecost de memòria per element que la nostra llista doble artesanal. És la resposta professional de Python al patró "entrar i sortir pels dos extrems", i serà protagonista al mòdul 4 quan construïm cues i deques; aquí en tenim prou de saber que existeix i que, per dins, és parenta directa del que acabes de programar.

Errors Comuns i Consells

Actualitzar una fletxa i oblidar la de tornada. L'error estrella: després de a.seguent = b, gairebé sempre falta b.anterior = a. El símptoma és traïdor perquè el recorregut cap endavant funciona i l'errada només aflora en anar cap enrere. Verifica cada mètode contra l'invariant n.seguent.anterior is n.
Els quatre casos frontera d'esborrar_node. Primer, últim, únic element i node interior toquen branques diferents. Esborrar l'únic node ha de deixar cap i cua a None alhora; prova sempre aquest cas.
Fer servir un node ja esborrat. Si vas guardar una referència a un node i després algú el va esborrar, les teves fletxes apunten al buit (o a None, gràcies a la higiene del mètode). En dissenys amb referències vives, defineix qui és responsable d'invalidar-les — com fa HistorialTasques movent self.actual només a través dels seus mètodes.
Pagar la llista doble sense fer-la servir. Si el teu codi no recorre mai cap enrere ni guarda referències a nodes, estàs pagant una fletxa extra per node i el doble de recablejats a canvi de res: torna a la llista simple. Triar l'estructura mínima suficient també és optimitzar.
Consell: en depurar, imprimeix la llista en tots dos sentits (list(llista) i list(reversed(llista))) i compara: han de ser exactament inverses. Si no ho són, hi ha una fletxa anterior traïda, i el punt on divergeixen et diu quina.

Exercicis

Exercici 1 — cercar_node i esborrat per id. Afegeix a LlistaDoblementEnllacada un mètode cercar_node(condicio) que retorni el node (no la dada) que compleixi la condició, o None. Fes-lo servir juntament amb esborrar_node per eliminar de l'historial la tasca amb id 2. Quin és el cost total de l'operació combinada i en quina part es concentra?

Exercici 2 — inserir_abans. Escriu el mètode inserir_abans(node, dada), simètric d'inserir_despres, amb cost O(1). Compte amb el cas en què node sigui el cap. Comprova amb un exemple que els invariants es mantenen imprimint la llista en tots dos sentits.

Exercici 3 — Detectar la fletxa traïda. Escriu una funció verificar(llista) que retorni True si la llista compleix els invariants de la lliçó (cap sense anterior, cua sense següent, i fletxes correspostes a tots els nodes) i False en cas contrari. Després trenca expressament una fletxa anterior d'una llista de prova i comprova que verificar la detecta.

Solucions

Solució 1:

    def cercar_node(self, condicio):
        """Retorna el primer NODE la dada del qual compleix la condició. Cost: O(n)."""
        actual = self.cap
        while actual is not None:
            if condicio(actual.dada):
                return actual
            actual = actual.seguent
        return None

# Operació combinada:
node = historial.llista.cercar_node(lambda t: t["id"] == 2)   # O(n)
if node is not None:
    if historial.actual is node:                 # no deixar 'actual' penjant
        historial.actual = node.anterior or node.seguent
    historial.llista.esborrar_node(node)         # O(1)

El cost total és O(n), però tot el cost és a la cerca; l'esborrat en si és O(1). Aquesta separació és la moralitat de la lliçó: la llista doble abarateix el modificar, no el trobar. Per abaratir el trobar farà falta l'índex per id del mòdul 5 — que, combinat amb aquesta llista (un dict d'id → node), donarà esborrats totals en O(1). Fixa't en el detall de recol·locar historial.actual si era sobre el node esborrat: és l'error "fer servir un node ja esborrat" tallat d'arrel.

Solució 2:

    def inserir_abans(self, node, dada):
        """Insereix una dada just abans del node donat. Cost: O(1)."""
        if node is self.cap:
            self.inserir_al_principi(dada)
            return
        nou = NodeDoble(dada)
        nou.seguent = node                # el nou mira a banda i banda
        nou.anterior = node.anterior
        node.anterior.seguent = nou       # els veïns li tornen la mirada
        node.anterior = nou
        self.mida += 1

# Comprovació d'invariants:
llista = LlistaDoblementEnllacada()
for x in ("A", "B", "D"):
    llista.inserir_al_final(x)
node_d = llista.cercar_node(lambda d: d == "D")
llista.inserir_abans(node_d, "C")
print(list(llista))             # ['A', 'B', 'C', 'D']
print(list(reversed(llista)))   # ['D', 'C', 'B', 'A']  ← exactament inversa: fletxes sanes

L'ordre de les quatre assignacions segueix la regla de sempre ampliada: primer el nou mira a banda i banda, després els veïns li tornen la mirada. I dins de la segona part, node.anterior.seguent = nou ha d'anar abans de node.anterior = nou, perquè la primera línia encara necessita el valor antic de node.anterior.

Solució 3:

def verificar(llista):
    """Comprova els invariants de la llista doble. Cost: O(n)."""
    if llista.cap is None or llista.cua is None:
        return llista.cap is None and llista.cua is None   # buida: totes dues a None
    if llista.cap.anterior is not None or llista.cua.seguent is not None:
        return False
    actual = llista.cap
    while actual.seguent is not None:
        if actual.seguent.anterior is not actual:   # fletxa de tornada correcta?
            return False
        actual = actual.seguent
    return actual is llista.cua    # el recorregut ha d'acabar exactament a la cua

# Sabotatge controlat:
llista = LlistaDoblementEnllacada()
for x in (1, 2, 3):
    llista.inserir_al_final(x)
print(verificar(llista))            # True
llista.cap.seguent.anterior = None  # trenquem una fletxa de tornada
print(verificar(llista))            # False

Comprovem les fletxes amb is (identitat de nodes, no igualtat de dades) i rematem verificant que el recorregut mor a llista.cua — així cacem també cues fantasma. Una funció com aquesta, cridada després de cada operació als tests, converteix els errors silenciosos de fletxes en fallades sorolloses i immediates: exactament el que vols mentre desenvolupes.

Conclusió

Amb una segona fletxa per node, la llista doblement enllaçada elimina les dues limitacions de la simple: ja es pot recórrer cap enrere (__reversed__ des de la cua) i, tenint el node, esborrar o inserir al seu costat és O(1) sense cercar ningú — a canvi de més memòria per node i fins a quatre fletxes que cal mantenir coherents a cada operació, amb els seus invariants i els seus casos frontera. L'historial navegable de TaskFlow va demostrar on brilla: enrere() i endavant() com a simples moviments d'una referència. I collections.deque va quedar presentada com la versió professional i híbrida d'aquesta idea, esperant-nos al mòdul 4. Ara bé, totes les nostres llistes —simples o dobles— comparteixen un tret: tenen un final, aquell None que atura els recorreguts. A la propera lliçó l'eliminarem deliberadament: farem que l'últim node apunti al primer i obtindrem les llistes circulars, perfectes per als torns rotatoris — a TaskFlow, el repartiment cíclic de tasques entre els membres de l'equip — sempre que aprenguem a recórrer-les sense caure en el bucle infinit.

Llistes Doblement Enllaçades

Contingut

El node doble: dues fletxes per node

Cap i cua: l'estructura i els seus invariants

Inserir per tots dos extrems

Inserir i esborrar O(1) donat el node

Recórrer en tots dos sentits

Simple vs doble: la balança completa

TaskFlow: l'historial de tasques navegable

Un pont cap a `collections.deque`

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 Doblement Enllaçades

Contingut

El node doble: dues fletxes per node

Cap i cua: l'estructura i els seus invariants

Inserir per tots dos extrems

Inserir i esborrar O(1) donat el node

Recórrer en tots dos sentits

Simple vs doble: la balança completa

TaskFlow: l'historial de tasques navegable

Un pont cap a collections.deque

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

Un pont cap a `collections.deque`