Ja saps què és una estructura de dades i per què triar bé importa. El següent pas natural és conèixer el catàleg: quines estructures existeixen i com es classifiquen? Aquesta lliçó és el mapa del curs: presentarem les grans famílies d'estructures (lineals i no lineals, estàtiques i dinàmiques, homogènies i heterogènies), veurem quin paper jugarà cadascuna a TaskFlow i repassarem les estructures que Python porta de sèrie, que seran el nostre punt de partida. No aprofundirem en cap —cadascuna té el seu propi mòdul—, però en acabar sabràs situar qualsevol estructura al mapa i entendràs l'itinerari que seguirem.

1. Classificació 1: lineals vs no lineals
2. Classificació 2: estàtiques vs dinàmiques
3. Classificació 3: homogènies vs heterogènies
4. El catàleg del curs i el seu paper a TaskFlow
5. Les estructures natives de Python: el nostre punt de partida

La primera pregunta que pots fer a qualsevol estructura és: com es relacionen els seus elements entre si?

• En una estructura lineal, els elements formen una seqüència: cada element té (com a molt) un anterior i un següent. És la relació "l'un darrere l'altre".
• En una estructura no lineal, un element pot relacionar-se amb diversos alhora: jerarquies (un pare amb diversos fills) o xarxes (connexions arbitràries entre nodes).

A TaskFlow apareixen els tres patrons de manera natural:

• El tauler de tasques és lineal: les tasques van en ordre, l'una darrere l'altra.
• Les categories són jeràrquiques: "Feina" conté "Client A", que conté "Factures".
• Les dependències són una xarxa: la tasca D depèn de la B i de la C, que al seu torn depenen de l'A.

Són lineals les llistes, les piles i les cues (mòduls 2 a 4). Són no lineals els arbres (jerarquies, mòdul 6) i els grafs (xarxes, mòdul 7). Les taules hash (mòdul 5) són un cas a part: els seus elements no mantenen cap relació d'ordre entre si —ni seqüència ni jerarquia—; el que les defineix és l'associació directa entre cada clau i el seu valor.

La classificació importa perquè determina com es recorre l'estructura: una seqüència es recorre de principi a fi; una jerarquia o una xarxa exigeixen estratègies de recorregut més elaborades (les veurem als seus mòduls).

La segona pregunta: pot canviar la mida de l'estructura durant l'execució?

• Una estructura estàtica té una mida fixa, decidida en crear-la. Ocupa un bloc de memòria de mida coneguda i no creix ni minva.
• Una estructura dinàmica creix i s'encongeix a mesura que s'insereixen o s'eliminen elements, adaptant el seu ús de memòria en temps d'execució.

L'exemple canònic d'estructura estàtica és l'array de mida fixa, habitual en llenguatges com C o Java: demanes lloc per a exactament 100 elements i això tens. En Python gairebé tot el que faràs servir és dinàmic —una list creix sense que t'hagis de preocupar de res—, però la distinció continua sent crucial per dos motius:

1. Les estructures dinàmiques de Python estan construïdes sobre mecanismes estàtics per sota, i aquest "per sota" explica els seus costos (ho veurem a la lliçó 01-05 amb els arrays i la memòria).
2. Tan bon punt surtis de Python (bases de dades, sistemes encastats, altres llenguatges), les mides fixes tornen a aparèixer.

Per a TaskFlow: el nombre de tasques és imprevisible i canvia constantment, així que necessitarem estructures dinàmiques gairebé sempre. En canvi, una cosa com els tres estats possibles d'una tasca (pendent, en curs, feta) és un conjunt fix que no creix mai: una estructura estàtica i immutable (una tupla, com veurem més avall) el representa millor.

Tercera pregunta: tots els elements són del mateix tipus?

• Una estructura homogènia només admet elements d'un mateix tipus: tots enters, tots cadenes...
• Una estructura heterogènia barreja tipus: un enter al costat d'una cadena al costat d'un objecte.

En llenguatges amb tipatge estricte (C, Java), els arrays són homogenis per obligació. Python és flexible: una list admet qualsevol barreja. Però que puguis barrejar no vol dir que hagis de fer-ho: en la pràctica professional, les col·leccions solen mantenir-se homogènies ("una llista de tasques", "un conjunt d'ids") i l'heterogeneïtat es reserva per representar registres amb camps amb nom, com el diccionari tasca de l'exemple. Aquesta disciplina fa el codi predictible: si saps que ids_pendents només conté enters, pots operar amb confiança sobre qualsevol dels seus elements.

Fixa't també en l'última línia de l'exemple: "etiquetes" conté una llista dins del diccionari. Les estructures es componen les unes dins de les altres, i les aplicacions reals —TaskFlow inclosa— són sempre composicions: una llista de diccionaris, un diccionari de llistes, un arbre els nodes del qual contenen cues...

Amb les tres classificacions a la mà, ja podem presentar el catàleg complet d'estructures que estudiarem, cadascuna amb la necessitat de TaskFlow que resoldrà:

Dues observacions sobre la taula:

• Els termes LIFO (Last In, First Out) i FIFO (First In, First Out) són l'única "argot" nova: descriu-los mentalment com la pila de plats i la cua del supermercat de la lliçó 01-01, i tindràs el 90 % de la intuïció.
• L'ordre dels mòduls no és casual: va del més simple al més ric. Les piles i les cues es construeixen a partir d'idees de les llistes; els arbres generalitzen la idea d'"element que apunta a d'altres"; els grafs generalitzen els arbres. Cada mòdul es recolza en l'anterior, igual que TaskFlow creixerà peça a peça.

El recorregut complet, vist com a itinerari:

Recorda que aquesta lliçó és només el mapa: la definició precisa de cada estructura, les seves operacions, implementacions i costos es desenvolupen al mòdul corresponent.

Python incorpora de sèrie quatre estructures de dades que farem servir constantment, tant per si mateixes com per construir les estructures del catàleg. Convé tenir clar el paper de cadascuna:

("Mutable" significa que es pot modificar després de creada; "ordenada", que els seus elements mantenen un ordre definit.)

Vegem-les en acció amb dades de TaskFlow:

Punts que convé destacar de l'exemple:

• tauler.append(...) mostra la naturalesa dinàmica de list: creix sense declarar mida.
• ESTATS com a tupla és la tria estàtica i immutable correcta per a dades que no han de canviar; si algú intenta modificar-la, Python llança un error, protegint el programa. La convenció d'escriure-la en majúscules assenyala "això és una constant".
• El set ha eliminat el duplicat "urgent" automàticament: la unicitat forma part del seu contracte.
• Aquestes quatre estructures són, en termes de la lliçó 01-01, implementacions molt polides de certs TAD: list d'una seqüència dinàmica, dict d'una taula associativa, set d'un conjunt matemàtic. En els propers mòduls les farem servir tant directament com de "material de construcció" per implementar piles, cues, arbres i grafs.

I les estructures que Python no porta de sèrie (llistes enllaçades, arbres, grafs)? Les construirem nosaltres amb classes, exactament com vam fer amb PilaAmbLlista a la lliçó 01-01. Aquí hi ha bona part del valor del curs: no només usar estructures, sinó saber fabricar-les.

• Usar list per a tot. És el vici número u del principiant en Python: la llista és tan còmoda que es converteix en martell universal. Abans d'escriure [], pregunta't: necessito ordre? (si no, potser set), hi accedeixo per nom? (potser dict), les dades són fixes? (potser tuple).
• Confondre la sintaxi de dict i set. Tots dos usen claus: {"a": 1} és un diccionari (té clau: valor), {"a", "b"} és un conjunt (només valors). I compte: {} a seques crea un diccionari buit; per a un conjunt buit cal escriure set().
• Creure que les classificacions són compartiments rígids. Són eixos d'anàlisi, no calaixos excloents: una mateixa estructura es pot descriure des dels tres eixos alhora (una list de Python és lineal, dinàmica i potencialment heterogènia), i les taules hash no encaixen del tot en l'eix lineal/no lineal.
• Consell: quan trobis una estructura nova en qualsevol llenguatge o llibreria (un deque, un DataFrame, un TreeMap de Java...), situa-la en els tres eixos d'aquesta lliçó i busca a quin TAD respon. És la manera més ràpida de "llegir" una estructura desconeguda.

Classifica cada escenari segons els eixos vistos (lineal/no lineal; i on tingui sentit, estàtica/dinàmica i homogènia/heterogènia):

1. Els mesos de l'any en una aplicació de calendari.
2. L'organigrama d'una empresa.
3. La cua d'impressió d'una oficina.
4. Les connexions d'amistat d'una xarxa social.

Per a cada necessitat de TaskFlow, tria l'estructura nativa de Python més adequada (list, tuple, dict o set) i justifica-ho en una frase:

1. Els dies de la setmana en què es poden programar recordatoris (de dilluns a diumenge, fixos).
2. Els ids de les tasques que l'usuari ha marcat com a preferides (sense repetits, sense ordre rellevant).
3. La correspondència entre cada usuari i la seva llista de projectes.
4. L'historial de títols de tasques consultades, en ordre, amb possibles repeticions.

Escriu en Python la representació d'un minitauler de TaskFlow amb aquests requisits: hi ha d'haver tres columnes fixes d'estat (pendent, en curs, feta); cada columna conté les seves tasques en ordre; cada tasca té id, titol i un conjunt d'etiquetes sense duplicats. Crea el tauler amb almenys dues tasques i escriu una línia de codi que afegeixi una etiqueta a una tasca existent. Indica quina estructura nativa has usat per a cada nivell i per què.

Solució 1:

1. Mesos de l'any: lineal (seqüència amb ordre), estàtica (sempre són 12) i homogènia (tots cadenes). En Python, una tupla seria el més natural.
2. Organigrama: no lineal, jeràrquic (cada persona té un responsable i pot tenir diversos subordinats): la forma d'un arbre. Dinàmica (la plantilla canvia).
3. Cua d'impressió: lineal i dinàmica; l'ordre d'arribada és la relació essencial (FIFO). Homogènia (tot són treballs d'impressió).
4. Amistats: no lineal, en xarxa (cada persona es connecta amb moltes altres sense jerarquia): la forma d'un graf. Dinàmica.

Solució 2:

1. tuple: col·lecció fixa i ordenada que no s'ha de modificar: DIES = ("dilluns", ..., "diumenge").
2. set: unicitat garantida i pertinença ràpida; l'ordre no importa: preferides = {4, 8, 15}.
3. dict: associació clau → valor, amb l'usuari com a clau i la seva llista de projectes com a valor: {"anna": ["web", "app"]} (fixa-t'hi: un dict que conté list, composició d'estructures).
4. list: seqüència ordenada, dinàmica i amb duplicats permesos: exactament el contracte de la llista.

Solució 3:

Justificació per nivells: un dict per a les columnes (accés per nom d'estat); una list per columna (les tasques mantenen un ordre i la col·lecció creix i minva); un dict per tasca (registre heterogeni amb camps amb nom); un set per a les etiquetes (unicitat automàtica). Quatre estructures natives component-se per modelar un domini real. Nota: les tres claus d'estat són fixes, però un dict és l'opció pràctica per accedir per nom; la immutabilitat de "només hi ha tres estats" la reforçarem amb altres tècniques més endavant.

Ja tens el mapa complet: les estructures es classifiquen segons com es relacionen els seus elements (lineals com llistes, piles i cues; no lineals com arbres i grafs; associatives com les taules hash), segons si la seva mida és fixa o variable (estàtiques vs dinàmiques) i segons si barregen tipus (homogènies vs heterogènies). Saps quin paper jugarà cadascuna a TaskFlow i comptes amb les quatre estructures natives de Python —list, tuple, dict, set— com a material de partida i de construcció.

Però al mapa li falta una dimensió: els números. Hem dit que la taula hash cerca "a l'instant" i que la llista "ho recorre tot"... com s'expressa això amb precisió, de manera que puguem comparar estructures rigorosament? Aquest és el propòsit de la propera lliçó: la notació Big O, el llenguatge universal per parlar d'eficiència que farem servir durant tota la resta del curs.