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

Introducció a les Llistes

Següent ►
►

En tancar el mòdul anterior vam deixar una promesa a l'aire: existeix "una altra aposta" diferent de la de l'array, una estructura que renuncia a la contigüitat en memòria precisament per fer barates les insercions i els esborrats allà on l'array fluixeja. Aquesta aposta és la llista enllaçada, i aquest mòdul sencer està dedicat a ella i a les seves variants. Però abans d'escriure ni una sola classe hem de fer un pas enrere i repetir el que vam fer amb la pila a la lliçó 01-01: separar el què (el TAD llista, un contracte d'operacions) del com (array contigu o nodes dispersos). En aquesta lliçó definim aquest contracte, entenem la peça fonamental de la nova aposta —el node amb la seva referència seguent— i posem cara a cara els costos de les dues implementacions, per decidir amb criteri quina convé a cada racó de TaskFlow.

Contingut

  1. El TAD llista: un contracte, dues implementacions
  2. L'aposta de l'array: contigüitat (repàs estratègic)
  3. L'altra aposta: nodes dispersos i referències
  4. Anatomia d'un node en Python
  5. Taula comparativa de costos: array dinàmic vs llista enllaçada
  6. Quina convé a TaskFlow?

El TAD llista: un contracte, dues implementacions

A la lliçó 01-01 vam veure que un Tipus Abstracte de Dades (TAD) defineix quines operacions ofereix una estructura sense comprometre's amb com s'implementen per dins: les nostres classes PilaAmbLlista i PilaAmbDiccionari complien el mateix contracte amb interiors completament diferents. Amb les llistes passa exactament el mateix.

El TAD llista és una seqüència ordenada d'elements on cada element ocupa una posició, i que ofereix com a mínim aquestes operacions:

  • Inserir un element (al principi, al final o en una posició intermèdia).
  • Esborrar un element (per posició o per valor).
  • Cercar un element (hi és? a quina posició?).
  • Recórrer la seqüència de principi a fi, visitant cada element en ordre.
  • Consultar l'element d'una posició donada i conèixer la longitud de la seqüència.

Fixa't que el contracte no diu ni una paraula sobre memòria, caselles o referències. I això és deliberat, perquè hi ha (almenys) dues maneres radicalment diferents de complir-lo:

Implementació A Implementació B
Nom Array dinàmic (la list de Python) Llista enllaçada (la construirem a 02-02)
Estratègia Elements contigus en memòria Nodes dispersos, units per referències
Com troba l'element i Fórmula base + i × mida Saltant de node en node des del primer
El seu punt fort Accés per índex instantani Inserir/esborrar sense desplaçar ningú

Una advertència terminològica important: en Python, la paraula list anomena la implementació A. És un nom una mica desafortunat, perquè en la literatura d'estructures de dades "llista" sol referir-se al TAD, i "llista enllaçada" (linked list) a la implementació B. En aquest curs direm list de Python o array dinàmic per a la A, i llista enllaçada per a la B.

L'aposta de l'array: contigüitat (repàs estratègic)

No repetirem la lliçó 01-05, però sí que la condensarem en allò que ens importa per a la comparació. L'array ho aposta tot a la contigüitat:

  • Guanya: accés per índex O(1) gràcies a la fórmula base + i × mida; recorreguts molt ràpids (la memòria contigua és amiga de la memòria cau del processador); append O(1) amortitzat.
  • Perd: inserir o esborrar al principi o al mig obliga a desplaçar tots els elements posteriors, un cost O(n) que vam mesurar amb timeit i que es tornava quadràtic en repetir-lo en bucle (la trampa de insert(0) que vam veure en tancar el mòdul 1).

La pregunta que queda flotant és: i si poguéssim inserir un element al mig de la seqüència sense tocar els altres? Per aconseguir-ho cal abandonar la idea que la posició en memòria codifica la posició en la seqüència.

L'altra aposta: nodes dispersos i referències

La llista enllaçada inverteix l'aposta. En lloc d'exigir que els elements visquin en caselles consecutives, permet que cadascun visqui on vulgui dins la memòria. Però llavors sorgeix un problema: si els elements estan dispersos, com sabem quin va després de quin? La fórmula de l'array ja no serveix, perquè no hi ha contigüitat per explotar.

La solució és que cada element porti amb ell l'adreça del següent. A aquest paquet —la dada més la referència al següent— l'anomenem node:

graph LR
    subgraph "Llista enllaçada: l'ordre el dicten les fletxes, no la memòria"
    A["dada: tasca 1<br>seguent ─→"] --> B["dada: tasca 2<br>seguent ─→"]
    B --> C["dada: tasca 3<br>seguent: None"]
    end
    H[cap] --> A

Tres observacions clau sobre aquest diagrama:

  • La llista només necessita "agafar" el primer node (l'anomenarem el cap, en anglès head). A partir d'ell, les fletxes permeten arribar a tots els altres.
  • L'últim node apunta a None: és el senyal de "aquí s'acaba la seqüència".
  • Les fletxes són la seqüència. Si en memòria el node de la tasca 3 fos físicament abans que el de la tasca 1, tant se valdria: l'ordre lògic el defineixen les referències, no les adreces.

I aquí hi ha la jugada mestra. Per inserir una tasca nova entre la 1 i la 2, no cal desplaçar res: n'hi ha prou amb recablejar dues fletxes.

graph LR
    H[cap] --> A["tasca 1"]
    A -. "fletxa antiga (s'elimina)" .-> B["tasca 2"]
    A -- "1: ara apunta a la nova" --> N["tasca nova"]
    N -- "2: la nova apunta a la 2" --> B
    B --> C["tasca 3<br>seguent: None"]

Tant és que la llista tingui 3 elements o 3 milions: el recablejat en si són dues assignacions, cost O(1). Aquesta és l'essència de la promesa "insercions i esborrats barats". (Compte: arribar fins al punt d'inserció pot tenir el seu propi cost; ho analitzarem amb rigor a la propera lliçó. No et volem vendre la moto sense la lletra petita.)

Anatomia d'un node en Python

En Python no manipulem adreces de memòria a mà: manipulem referències, que és exactament el que passa cada cop que assignes un objecte a una variable. Un node és simplement un objecte amb dos atributs:

class Node:
    """Una peça de la llista enllaçada: una dada i la referència al següent."""
    def __init__(self, dada):
        self.dada = dada          # el contingut: a TaskFlow, una tasca (dict)
        self.seguent = None       # referència al pròxim node (None = no n'hi ha més)

Explicació detallada per a qui ho veu per primera vegada:

  • self.dada guarda l'element en si. Com que Python treballa amb referències, aquí hi pot viure qualsevol cosa: un nombre, una cadena o —en el nostre cas— la tasca-com-a-dict que vam fixar al mòdul 1.
  • self.seguent guarda una altra referència, aquest cop a un altre objecte Node (o None si és l'últim). No hi ha màgia: és la mateixa mecànica d'assignació que fas servir cada dia, posada al servei d'encadenar objectes.

Podem encadenar tres tasques de TaskFlow a mà, sense cap classe contenidora encara:

# Tres tasques de TaskFlow (el dict fixat al mòdul 1)
t1 = {"id": 1, "titol": "Dissenyar el logo", "prioritat": 2, "estat": "pendent"}
t2 = {"id": 2, "titol": "Configurar el servidor", "prioritat": 1, "estat": "pendent"}
t3 = {"id": 3, "titol": "Escriure la documentació", "prioritat": 3, "estat": "pendent"}

# Creem els nodes i els enllacem a mà
cap = Node(t1)
cap.seguent = Node(t2)
cap.seguent.seguent = Node(t3)

# Recorrem seguint les fletxes fins a trobar None
actual = cap
while actual is not None:
    print(actual.dada["titol"])
    actual = actual.seguent   # "avançar" = seguir la referència

Sortida:

Dissenyar el logo
Configurar el servidor
Escriure la documentació

El bucle while de dalt és el gest més important de tot el mòdul: avançar per una llista enllaçada és reassignar actual = actual.seguent fins a topar amb None. Tot el que construirem a les properes lliçons —inserir, esborrar, cercar— són variacions d'aquest gest.

Encadenar nodes a mà és instructiu però impracticable. A 02-02 encapsularem tota aquesta mecànica en una classe LlistaEnllacada amb les operacions del TAD; avui en tenim prou d'entendre la peça.

Taula comparativa de costos: array dinàmic vs llista enllaçada

Aquesta taula és el mapa del mòdul. La columna de l'array la vam demostrar a 01-05; la columna de la llista enllaçada és, de moment, un avançament que la lliçó 02-02 demostrarà operació per operació (i verificarà amb timeit, com manen els nostres costums):

Operació Array dinàmic (list) Llista enllaçada simple Per què?
Accés per índex [i] O(1) O(n) Fórmula directa vs caminar i salts des del cap
Inserir al principi O(n) O(1) Desplaçar-ho tot vs recablejar el cap
Inserir al final O(1) amortitzat O(n) — o O(1) amb truc* append amb forat vs caminar fins a l'últim node
Inserir al mig (ja situats) O(n) O(1) Desplaçar la meitat vs recablejar dues fletxes
Esborrar al principi O(n) O(1) La trampa de pop(0) vs moure el cap
Cercar per valor O(n) O(n) En totes dues cal mirar element a element
Recórrer sencera O(n) O(n) Totes dues ho visiten tot, però l'array és més amic de la memòria cau
Memòria per element Només la referència a la dada Referència a la dada + referència seguent El node paga un extra per cada fletxa

* El "truc" consisteix que la llista guardi també una referència a l'últim node (la cua); el veurem a 02-02.

Lectures importants de la taula:

  • No hi ha guanyador absolut. Cada estructura guanya just on l'altra perd: és un intercanvi (trade-off), el pa de cada dia en estructures de dades.
  • La llista enllaçada perd el superpoder de l'array: ja no hi ha cap fórmula que porti a l'element i d'un salt. Demanar "l'element 500.000" vol dir fer 500.000 salts.
  • Cercar per valor és O(n) en totes dues: cap de les dues no resol el problema de "trobar la tasca amb id 42" que vam plantejar a 01-02. Per a això continuarà fent falta l'índex per id que arribarà al mòdul 5.
  • La llista enllaçada paga un sobrecost de memòria: cada dada carrega amb una fletxa extra. La dispersió no surt gratis.

Quina convé a TaskFlow?

Baixem la taula a terra amb els escenaris reals de la nostra aplicació:

Escenari a TaskFlow Operació dominant Estructura guanyadora
Mostrar el tauler complet en pantalla Recórrer Empat (lleuger avantatge de l'array per memòria cau)
"Dona'm la tasca de la posició 7 de la vista" Accés per índex Array
Les tasques urgents entren sempre per davant Inserir al principi Llista enllaçada
Despatxar tasques retirant-les per davant Esborrar al principi Llista enllaçada
Reordenar: moure una tasca entre dues altres Inserir/esborrar al mig Llista enllaçada (si ja hi estem situats)
Afegir tasques sempre pel final Inserir al final Array (append amortitzat) o enllaçada amb cua

La conclusió per a TaskFlow és matisada, com gairebé tot en enginyeria: mentre el tauler només creixia pel final i es llegia en ordre, la list de Python era imbatible. Però el tauler real d'un equip no funciona així: les urgències entren per davant, les tasques es despatxen per davant i es reordenen pel mig constantment. Aquest patró d'ús —moltes insercions i esborrats en posicions incòmodes— és exactament el terreny on la llista enllaçada brilla, i per això l'escollim com a base del tauler definitiu.

Errors Comuns i Consells

  • Confondre la list de Python amb una llista enllaçada. És l'error terminològic número u. La list de Python és un array dinàmic (lliçó 01-05); si en una entrevista et demanen "implementa una llista enllaçada", respondre llista = [] és respondre una altra pregunta.
  • Creure que la llista enllaçada és "millor" que l'array. No ho és; és millor per a certes operacions i pitjor per a d'altres. Qui memoritza "llista enllaçada = ràpida" sense la taula de costos acaba triant malament. Guarda la taula d'aquesta lliçó al costat de la de costos de list/dict/set de 01-04.
  • Oblidar que seguent pot ser None. Escriure actual.seguent.dada sense comprovar abans que actual.seguent no és None provoca el clàssic AttributeError: 'NoneType' object has no attribute 'dada'. Acostuma't des d'ara a preguntar-te a cada línia: "i si aquí ja no hi ha node?".
  • Perdre el cap de la llista. Si reassignes la variable que apunta al primer node (cap = cap.seguent sense voler), el node anterior es torna inabastable i el recol·lector de brossa de Python l'elimina. El cap és l'únic fil del qual penja tota l'estructura: tracta'l amb respecte.
  • Consell: quan dubtis d'un recablejat de referències, dibuixa els nodes i les fletxes en paper abans d'escriure codi. És la tècnica que fan servir fins i tot els enginyers veterans, i a les lliçons següents la practicarem amb diagrames mermaid a cada pas.

Exercicis

Exercici 1 — El contracte i les seves implementacions. Sense mirar la taula, classifica aquestes quatre frases com a pròpies del TAD llista, de l'array dinàmic o de la llista enllaçada: (a) "inserir un element a la posició i"; (b) "els elements ocupen caselles contigües de memòria"; (c) "cada element guarda una referència al següent"; (d) "recórrer els elements en ordre". Justifica cada resposta en una línia.

Exercici 2 — Encadenar i recórrer a mà. Fent servir només la classe Node d'aquesta lliçó (sense cap classe contenidora), construeix una cadena amb aquestes quatre tasques de TaskFlow: "Revisar el disseny" (id 10), "Corregir el bug del login" (id 11), "Desplegar la versió" (id 12) i "Tancar l'esprint" (id 13), totes amb prioritat 2 i estat "pendent". Després escriu: (a) un bucle que imprimeixi id - titol de cada tasca; (b) un bucle que compti quants nodes hi ha, sense fer servir len de cap estructura auxiliar.

Exercici 3 — Recablejar sense desplaçar. Partint de la cadena de l'exercici 2, insereix la tasca "Hotfix de producció" (id 14, prioritat 1) entre "Corregir el bug del login" i "Desplegar la versió", sense crear cap cadena nova: només creant un node i reassignant les referències necessàries. Quantes assignacions de seguent has necessitat? Dependria aquest nombre que la cadena tingués un milió de nodes?

Solucions

Solució 1:

  • (a) TAD llista: descriu una operació del contracte, sense dir com s'aconsegueix per dins.
  • (b) Array dinàmic: la contigüitat és la decisió d'implementació que dona l'accés O(1) per fórmula.
  • (c) Llista enllaçada: la referència al següent és la decisió d'implementació que permet la dispersió.
  • (d) TAD llista: recórrer forma part del contracte; totes dues implementacions ho ofereixen (amb interiors diferents).

Solució 2:

class Node:
    def __init__(self, dada):
        self.dada = dada
        self.seguent = None

def tasca(id_, titol):
    return {"id": id_, "titol": titol, "prioritat": 2, "estat": "pendent"}

# (Construcció) Creem els nodes i els enllacem un a un
cap = Node(tasca(10, "Revisar el disseny"))
cap.seguent = Node(tasca(11, "Corregir el bug del login"))
cap.seguent.seguent = Node(tasca(12, "Desplegar la versió"))
cap.seguent.seguent.seguent = Node(tasca(13, "Tancar l'esprint"))

# (a) Imprimir id - titol seguint les fletxes
actual = cap
while actual is not None:
    print(f'{actual.dada["id"]} - {actual.dada["titol"]}')
    actual = actual.seguent

# (b) Comptar nodes: mateix recorregut, amb un comptador
comptador = 0
actual = cap
while actual is not None:
    comptador += 1
    actual = actual.seguent
print("Nodes:", comptador)   # Nodes: 4

Observa que tots dos apartats fan servir el mateix patró de recorregut; només canvia què fem en visitar cada node. Aquest patró és el cor de la classe que construirem a 02-02. I sí: les cadenes cap.seguent.seguent.seguent = ... són horribles — exactament per això necessitem encapsular tot això en una classe.

Solució 3:

# 1. Localitzem el node darrere del qual hem d'inserir (el d'id 11)
node_bug = cap.seguent          # "Corregir el bug del login"

# 2. Creem el node nou
nou = Node({"id": 14, "titol": "Hotfix de producció",
            "prioritat": 1, "estat": "pendent"})

# 3. Recablejat: primer el nou apunta al que venia després...
nou.seguent = node_bug.seguent   # assignació 1
# ...i després l'anterior apunta al nou. L'ordre importa!
node_bug.seguent = nou           # assignació 2

N'hi ha hagut prou amb 2 assignacions de seguent, i aquest nombre seria idèntic amb un milió de nodes: el recablejat en si és O(1). Fixa't en l'ordre de les dues línies: si féssim primer node_bug.seguent = nou, perdríem la referència a "Desplegar la versió" i la resta de la cadena quedaria despenjada. Aquest detall —l'ordre del recablejat— serà protagonista a la propera lliçó.

Conclusió

Hem separat el contracte dels seus complidors: el TAD llista és una seqüència ordenada amb operacions d'inserir, esborrar, cercar i recórrer, i tant l'array dinàmic com la llista enllaçada l'implementen amb apostes oposades — contigüitat amb accés O(1) per fórmula davant de nodes dispersos units per referències seguent, on inserir és recablejar dues fletxes en lloc de desplaçar mitja memòria. La taula de costos ens va deixar clar que no hi ha guanyador absolut, i el patró d'ús del tauler de TaskFlow (urgències per davant, reordenacions pel mig) va inclinar la balança cap a la llista enllaçada. Però fins ara només hem encadenat nodes a mà, amb aquell incòmode cap.seguent.seguent. A la propera lliçó farem les coses bé: construirem la classe LlistaEnllacada completa —inserir, esborrar, cercar, recórrer, __len__, __str__—, analitzarem el Big O de cada operació, i posarem la criatura davant de timeit per comprovar que la promesa de les insercions barates es compleix allà on l'array queia: inserint per davant.

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