Estructures de dades i algorismes: guia completa per a programadors

Informatec Digital » Recursos » Estructures de dades i algorismes: guia completa per a programadors

Algorismes i estructures de dades són dues peces que encaixen com un puzle: una marca el procediment per resoldre el problema i l'altra determina on i com guardem la informació. Encara que pugui sonar acadèmic, dominar aquesta parella és el que separa un codi que simplement funciona d'un codi que vola i escala sense trencar-se.

Si vols dedicar-te a la programació professional, preparar entrevistes tècniques o simplement deixar de barallar-te amb exercicis tipus LeetCode i Codewars, necessites una bona base de estructura de dades i algorismes. Al llarg d'aquest article veureu què són, per què són tan importants, quins tipus principals existeixen, quines operacions bàsiques realitzen i quines preguntes solen caure en exàmens i processos de selecció.

Què són estructures de dades i algorismes

Una estructura de dades és, bàsicament, una forma concreta d'organitzar i emmagatzemar la informació en memòria per poder operar-hi de manera eficient. Aquesta organització no és aleatòria: condiciona directament quines operacions són ràpides i quines es tornen costoses (inserir, cercar, esborrar, recórrer, etc.).

Quan trieu bé l'estructura de dades, el vostre programa pot gestionar grans volums de dades sense despentinar-se; quan tries malament, fins i tot una aplicació petita pot tornar-se lenta, consumir massa memòria o fer-se impossible de mantenir amb el temps.

un algoritme és una seqüència finita i ordenada de passos ben definits que transforma unes entrades en unes sortides per resoldre un problema concret. És com una recepta de cuina: et diu què fer, en quin ordre i sota quines condicions, però no es preocupa per com guardes els ingredients a la nevera, que seria la part de l'estructura de dades.

En informàtica es dissenya cada algorisme pensant en el tipus de dades amb què treballarà. L'elecció de l'estructura de dades no és cap detall menor: estructura i algoritme van de la mà, i petits canvis en una de les dues parts poden disparar o enfonsar el rendiment.

Des de la perspectiva teòrica, autors com Niklaus Wirth ja als anys 70 van popularitzar la idea que algorismes + estructures de dades = programes. Dècades després, segueix sent igual de cert: tant se val que programes a Java, Python, C++ o que vinguis d'un bootcamp, el que se t'exigirà en entrevistes i projectes seriosos és saber triar i combinar bé tots dos elements.

Per què són tan importants en programació

En qualsevol aplicació real, per molt senzilla que sembli, sempre estàs treballant amb dades: salaris, productes, usuaris, transaccions, rutes, documents, registres de logs, etc. La pregunta no és si manejaràs dades, sinó com els organitzaràs perquè el teu codi sigui ràpid, clar i fàcil de mantenir.

Les estructures de dades serveixen per emmagatzemar la informació de manera ordenada i coherent segons el problema. No és el mateix haver d'accedir sempre al primer element, cercar per clau, recórrer en ordre, inserir al mig o eliminar de forma freqüent; cada patró dús encaixa millor amb una estructura diferent.

Per la seva banda, els algorismes permeten processar aquestes dades de forma eficient: ordenar-los, filtrar-los, cercar elements, trobar rutes òptimes, detectar patrons amb mineria de dades, optimitzar recursos, etc. Molts problemes que semblen difícils es tornen trivials quan dónes amb la combinació adequada d'algorisme i estructura de dades.

En entrevistes tècniques de desenvolupament de programari és estrany que et preguntin alguna cosa que no toqui de front aquests temes. De vegades la pregunta esmenta explícitament l'estructura, com “donat un arbre binari…”, i d'altres vegades és implícita: “volem explicar quants llibres té cada autor”, la qual cosa suggereix fer-ne servir una taula hash o mapa clau-valor.

A més, la formació reglada i professional sol girar força al voltant d'aquest bloc. A moltes universitats i cicles superiors existeix l'assignatura de Estructures de Dades i Algorismes, amb programa oficial, prerequisits, sessions de teoria i pràctiques, exàmens i treballs, perquè es considera una matèria troncal per a qualsevol enginyer de programari.

Prerequisits i bases necessàries

Per treure partit a l'estudi d'estructures de dades i algorismes convé tenir un cert domini d'un llenguatge de programació generalista, com ara Java, Python o C++. No cal ser un guru, però sí manejar amb soltesa conceptes bàsics com a variables, tipus de dades, condicionals, bucles, funcions i pas de paràmetres.

També ajuda moltíssim entendre la idea de complexitat algorítmica i la notació Big O: com creix el temps dexecució o lús de memòria quan augmenta la mida de les dades (n). Saber distingir entre O(1), O(log n), O(n), O(n log n) i O(n²) us permet comparar alternatives amb criteri i justificar les vostres decisions.

Un altre aspecte important és haver-se barallat una mica amb la resolució de problemes: exercicis de programació estructurada, petits reptes de lògica, kata senzilles, etc. Com més entrenis l'olfacte per descompondre un problema en passos, més fàcil et resultarà veure quina estructura de dades encaixa amb cada cas.

En alguns plans d‟estudis s‟estableixen explícitament prerequisits o correquisits per a l'assignatura d'Estructures de Dades i Algorismes, com tenir aprovada la matèria de Fonaments de Programació, Programació I o Matemàtiques Discretes. És lògic: sense una base sòlida en programació bàsica i una mica de lògica és fàcil frustrar-se amb aquesta matèria.

Finalment, tenir certa familiaritat amb entorns pràctics reals (com petits projectes web, scripts o aplicacions de consola) t'ajuda a visualitzar millor per a què utilitzaràs cada estructura, en lloc de veure'l com una cosa purament acadèmica.

Estructures de dades més utilitzades

En informàtica hi ha moltes estructures de dades, però hi ha un grup de “bàsiques” que es repeteixen una vegada i una altra: arranjaments (vectors), piles, cues, llistes enllaçades, arbres, grafs, tries i taules hash. Entendre com funcionen, quines operacions ofereixen i els seus costos típics és clau per moure's amb facilitat en programació.

A continuació anem a repassar cadascuna, amb la seva idea principal, operacions típiques i exemples de problemes que solen aparèixer a classes, exercicis i entrevistes de treball per a desenvolupadors.

Arranjaments o arrays

L'arranjament (array) és l'estructura de dades lineal més senzilla i una de les més utilitzades. Consisteix en un bloc contigu de memòria que emmagatzema una col·lecció d'elements del mateix tipus, accessibles mitjançant un índex sencer, normalment començant per zero.

Imagina un array de mida 4 que conté els valors 1, 2, 3 i 4. Cada posició té un índex (0, 1, 2, 3) i podeu accedir directament a qualsevol element amb el vostre índex en temps constant O(1). Això fa que els arrays siguin molt eficients per a lectura aleatòria.

Hi ha dues categories principals: arrays unidimensionals (una sola fila d'elements) i arrays multidimensionals (per exemple, matrius, que són arrays d'arrays). Molts llenguatges de programació ofereixen ambdues variants de forma nativa o amb lleugeres diferències de sintaxi i rendiment.

Les operacions bàsiques sobre un array solen ser:

• Inserir (insert): col·locar un element en una posició concreta, cosa que en arrays estàtics pot implicar desplaçar altres elements.
• Obtenir (get): accedir a l'element d'un índex donat, típic O(1).
• Eliminar (delete): esborrar o marcar com a buit l'element d'una posició concreta, normalment desplaçant elements a l'esquerra.
• Mida (size): consultar quants elements s'emmagatzemen o la capacitat màxima de l'array.

En entrevistes i exàmens són molt habituals exercicis com cercar el segon mínim d'un array, trobar el primer sencer no repetit, fusionar dos arrays ja ordenats, o reordenar positius i negatius mantenint certes propietats. Tot això es recolza en laccés per índex i en recorreguts lineals o dobles.

Piles (Stacks)

la pila és una estructura de dades lineal que segueix el principi LIFO: Last In, First Out (en castellà, UEPS: Últim a Entrar, Primer a Sortir). Imagina una pila de llibres col·locats un a sobre de l'altre: només pots agafar o deixar llibres per la part de dalt.

Aquest comportament es tradueix que només accedim a l'element que està al cim de la pila. No podem treure l'element del medi sense retirar abans els que hi ha a sobre. Això la converteix en una estructura ideal per modelar l'historial d'accions (desfer/un), trucades imbricades de funcions, navegadors (endarrere/avanç), etc.

Les operacions típiques d'una pila són:

• Empenta: inserir un nou element al cim.
• Pop: extreure i tornar l'element que és al cim, reduint la mida de la pila.
• Top o peek: consulteu l'element superior sense eliminar-lo.
• està buit: comprovar si la pila és buida.

En el context d'entrevistes es veuen problemes com ara avaluar expressions en notació postfixa (RPN), ordenar elements usant només piles, o verificar si una cadena de parèntesis (i altres símbols) està correctament balancejada mitjançant push i pop.

A la pràctica, moltes implementacions internes dels llenguatges (per exemple, la pila de trucades del sistema) funcionen seguint aquests mateixos principis, encara que no les vegem directament.

Cues (Queues)

la cua és una altra estructura de dades lineal, però en lloc de seguir el principi LIFO, aplica el model FIFO: First In, First Out (PEPS: Primer a Entrar, Primer a Sortir). L'analogia més clara és una fila de gent esperant a la taquilla del cinema.

En una cua estàndard, els elements es afegeixen pel final i es retiren pel principi. El primer que arriba és el primer que s'atén, cosa que la fa ideal per gestionar tasques pendents, processos en un sistema operatiu, peticions a un servidor, cues d'impressió, etc.

Les operacions bàsiques d'una cua inclouen:

• Cua: inserir un nou element al final de la cua.
• Retireu la cua: eliminar i tornar l'element situat a l'inici.
• Front o top: consultar el primer element sense retirar-lo.
• està buit: comprovar si la cua és buida.

En reptes de programació és freqüent que us demanin, per exemple, implementar una pila usant dues cues, invertir els primers k elements d'una cua sense alterar-ne la resta, o generar nombres binaris de l'1 al n usant el comportament FIFO de la cua.

A més de la cua bàsica, hi ha variants com la cua circular, la cua de prioritat o les cues dobles (deque), que ofereixen operacions addicionals i milloren el rendiment en determinats escenaris.

Llistes enllaçades

La llista enllaçada (linked list) és també una estructura lineal, però internament és molt diferent dels arrays. En lloc de fer servir un bloc contigu de memòria, està formada per nodes dispersos que es connecten entre si mitjançant referències o punters.

Cada node sol contenir dues parts: les dades que es volen emmagatzemar i un punter (o diversos) que apunta al següent node de la seqüència (i, en el cas de llistes doblement enllaçades, també a l'anterior). La llista es maneja a través d'una referència al cap, que apunta al primer node, i en llistes més complexes també es manté una referència a la cua.

Hi ha dues variants principals:

• Llista simplement enllaçada: cada node apunta només al següent; el recorregut sol ser en una única adreça.
• Llista doblement enllaçada: cada node apunta al següent ia l'anterior, facilitant recorreguts bidireccionals i operacions d'esborrament més eficients.

Les operacions típiques sobre llistes enllaçades inclouen:

• InsertAtHead: inserir un nou node al principi de la llista.
• InsertAtEnd: afegir un node al final, actualitzant la cua si n'hi ha.
• Esborrar: eliminar un node concret, ajustant els punters dels nodes veïns.
• DeleteAtHead: esborrar el primer node i moure el cap al següent.
• Cerca: recórrer la llista cercant un valor concret.
• està buit: comprovar si el cap és nul i, per tant, la llista no té elements.

A classes i entrevistes abunden problemes com invertir una llista enllaçada, detectar si hi ha un cicle (normalment usant l'algorisme de “tortuga i llebre”), obtenir el node N comptant des del final, o eliminar nodes duplicats, sempre manipulant punters amb cura.

Les llistes enllaçades s'utilitzen molt per implementar taules hash amb encadenament, llistes d'adjacència en grafs, i estructures de dades dinàmiques on s'insereixen i eliminen elements amb freqüència.

arbres

un arbre és una estructura de dades jeràrquica formada per nodes connectats mitjançant arestes. A diferència dels grafs generals, en un arbre no hi ha cicles: sempre hi ha una arrel, fills, pares, germans, fulles, nivells i subarbres, amb una organització tipus “família” o “organigrama”.

Els arbres són molt útils quan volem representar relacions jeràrquiques o dividir un problema en subproblemes més petits: sistemes de fitxers, menús, estructures DOM en navegadors, arbres de decisió en intel·ligència artificial, etc.

Hi ha moltes variants d'arbres, entre les quals hi ha:

• Arbre N-ari: cada node pot tenir un nombre variable (i possiblement gran) de fills.
• Arbre equilibrat: manté les branques a una profunditat similar per evitar degradacions de rendiment.
• Arbre binari: cada node té com a màxim dos fills (esquerra i dret).
• Arbre de cerca binària (BST): arbre binari amb la propietat que tot el que està a lesquerra dun node és menor i tot el que està a la dreta és major (segons algun criteri dordre).
• Arbre AVL, vermell-negre, 2‑3 i altres variants: són arbres de cerca balancejats que garanteixen bones cotes de complexitat en operacions d'inserció, esborrat i cerca.

A la pràctica, els més freqüents en exercicis són el arbre binari i arbre de cerca binària. Els problemes típics inclouen calcular l'altura de l'arbre, trobar el valor màxim en un BST, llistar els nodes a certa distància de l'arrel o determinar els ancestres d'un node concret.

A més, els algorismes de recorregut (preordre, ordre, postordre, nivell per nivell) són fonamentals per a molts processos posteriors: impressió ordenada, avaluació d'expressions, serialització i deserialització d'arbres, etc.

Grafs

Un graf generalitza el concepte d'arbre permetent cicles i múltiples connexions arbitràries entre nosaltres. Està format per un conjunt de vèrtexs (nodes) i un conjunt d'arestes que connecten parells de vèrtexs, de vegades amb un pes o un cost associat.

Hi ha diversos tipus de grafs: no dirigits (les arestes no tenen sentit de direcció, la relació és bidireccional) i dirigits (les arestes tenen un origen i una destinació). També es poden classificar com a ponderats o no ponderats, connexos o no, amb cicles o sense, etc.

En codi, els grafs solen representar-se de dues maneres bàsiques:

• Matriu d'adjacència: una matriu on la cel·la indica si hi ha aresta entre el vèrtex ii el j (i possiblement el pes de la connexió).
• Llista d'adjacència: per a cada vèrtex s'emmagatzema una llista dels seus veïns, cosa que estalvia memòria en grafs dispersos.

Els algorismes de recorregut més clàssics són la cerca en amplada (BFS) i la cerca en profunditat (DFS). Tots dos es fan servir com a blocs bàsics per a multitud de problemes: comprovar si un graf és connex, detectar cicles, trobar components connectades, etc.

En proves tècniques és habitual que et demanin implementar BFS i DFS, comprovar si un graf forma un arbre, comptar el nombre d'arestes o cercar camins més curts entre dos nodes (per exemple, en un mapa de ciutats) usant variants com Dijkstra o BFS en grafs no ponderats.

Tries o arbres de prefixos

El trie (o arbre de prefixos) és una estructura de dades en forma d'arbre optimitzada per manejar cadenes de caràcters, especialment útil quan treballem amb diccionaris de paraules, sistemes d'autocompletat o cerques per prefix.

En un trie, cada node sol representar un caràcter, i els camins des de l'arrel fins a determinats nodes marquen paraules completes. Els nodes finals de paraula se solen marcar d'alguna manera (per exemple, amb un indicador booleà) per distingir-los de simples prefixos.

Si emmagatzemem les paraules “top”, “thus” i “their” en un trie, compartirem part del camí inicial per a totes aquelles que comencen amb les mateixes lletres, cosa que permet fer cerques i suggeriments per prefix a temps molt eficient, proporcional a la longitud de la paraula que busquem i no al nombre total de paraules emmagatzemades.

Entre les operacions i problemes freqüents amb tries hi ha: comptar quantes paraules hi ha emmagatzemades, imprimir totes les paraules en ordre lexicogràfic, ordenar elements d'un array mitjançant inserció en un trie, generar paraules vàlides a partir d'un conjunt de lletres o construir estructures semblants a un diccionari T9.

En contextos d'entrevistes, no és l'estructura més bàsica que et demanaran, però sí que apareix amb regularitat en companyies que treballen amb cerques, processament de text o sistemes de suggeriments.

Taules hash i hashing

El hashing és una tècnica per assignar a cada dada una clau numèrica (hash) de manera determinista, de manera que puguem emmagatzemar i recuperar elements en temps gairebé constant, usant aquesta clau com a índex en una estructura interna, normalment un array.

La taula hash és lestructura de dades que aprofita aquest mecanisme. Cada element es desa com un parell clau-valor: la clau es transforma mitjançant una funció hash en un índex de la taula, i s'hi emmagatzema el valor (o una referència a ell). Posteriorment, per buscar, només cal refer el hash de la clau i accedir a la posició corresponent.

El rendiment d'una taula hash depèn crucialment de tres factors: la funció hash escollida (ha de repartir bé les claus per evitar concentracions), el mida de la taula (una mida insuficient provoca moltes col·lisions) i el mètode per gestionar col·lisions (encadenament amb llistes enllaçades, adreçament obert, etc.). Això és similar a un índex en base de dades, on decidir lestructura adequada millora cerques i accessos.

En exercicis típics de programació amb hash se sol demanar, per exemple, trobar parells simètrics en un array, reconstruir l'itinerari complet d'un viatge a partir de vols solts, comprovar ràpid si un array és subconjunt d'un altre, o verificar si dos arrays són disjunts, tot aprofitant les cerques O(1) aproximades de la taula hash.

En la majoria de llenguatges moderns, les estructures tipus map, dictionary, hash map o hash set es recolzen internament en taules hash, encara que s'ofereixi una interfície d'alt nivell al programador.

Com es relacionen algorismes i estructures de dades

L'elecció de l'estructura de dades condiciona directament quins algoritmes tenen sentit i quina serà la complexitat. Un algorisme de cerca lineal sobre una llista desordenada recorre elements un a un; si canviem l'estructura a un arbre de cerca equilibrat o una taula hash, passem a tenir temps molt millors.

Per exemple, si vols cercar repetidament claus en una col·lecció gran, emmagatzemar les dades en una taula hash o un arbre de cerca binària et permet dissenyar algorismes de cerca molt més ràpids que si uses un simple array sense ordenar. El mateix passa amb les cues de prioritat i els monticles (heaps) per a algoritmes de planificació o de camins mínims.

En sentit invers, en dissenyar un algorisme sovint t'adones que necessites certes propietats: accessos per índex, insercions ràpides al principi, recorreguts jeràrquics, cerques per prefix, etc. Aquestes necessitats són les que us guien a escollir l'estructura: arrays, llistes, arbres, grafs, taules hash, tries...

Aquesta combinació adequada d'algorisme i estructura de dades és el que fa possible que les aplicacions complexes siguin eficients i escalables. Sense una bona base, les solucions tendeixen a tornar-se lentes, difícils d'entendre i mantenir, o impossibles d'adaptar quan creix el volum d'informació.

Per tot això, dominar algorismes i estructures de dades no és un requisit gairebé imprescindible per a qui aspiri a convertir-se en un programador solvent i competitiu al mercat laboral actual.

Com aprendre estructures de dades i algorismes

Molta gent se sent bloquejada quan intenta aprendre pel seu compte amb plataformes com LeetCode o Codewars. És habitual començar per exercicis “fàcils” i tot i així no saber per on atacar el problema, acabar mirant la solució i no tenir clar com reproduir-la després.

Un enfocament pràctic sol combinar diversos ingredients: una bona explicació teòrica de cada estructura i algorisme, exemples visuals, molta pràctica guiada i, si és possible, acompanyament d'algú amb experiència que t'ajudi a polir la teva manera de pensar els problemes.

A l'àmbit hispanoparlant hi ha professionals amb una llarga trajectòria que han contribuït a facilitar aquest aprenentatge. Un exemple és el treball de docents amb experiència en empresa i en educació que han publicat llibres i cursos sobre fonaments de programació, Java, estructures de dades i reptes de programació amb jocs, apropant aquests conceptes de manera amena i aplicable a projectes reals.

També és habitual que les acadèmies i els centres de formació incloguin mòduls específics d'estructures de dades i algorismes dins d'itineraris per a desenvolupadors web o programadors d'aplicacions. En molts casos s'insisteix en un enfocament molt pràctic i basat en projectes, amb exercicis de dificultat creixent i simulació de problemes típics dentrevistes tècniques.

Si estàs encallat, et pot ajudar seguir una ruta estructurada: començar per arrays i llistes, passar per piles i cues, després arbres i grafs bàsics, i finalment taules hash i tries, sempre alternant explicació teòrica, petits exemples de codi i molta pràctica individual.

Amb vista a entrevistes convé repassar, a més de les estructures, els algorismes de força bruta i els algorismes clàssics associats (recorreguts, cerques, ordenacions, backtracking senzill, programació dinàmica bàsica) i assegurar-se de poder explicar en veu alta per què has triat una estructura concreta i quina és la complexitat de la teva solució.

Amb el temps i una mica de constància, el que al principi sembla un mur acaba convertint-se en un conjunt d'eines familiars que fas servir gairebé de forma instintiva quan t'enfrontes a nous problemes.

Entendre bé què són els algorismes, com funcionen les estructures de dades principals i com es relacionen entre si et permetrà escriure programes més ràpids, clars i robustos, t'obrirà portes en processos de selecció exigents i farà que els teus projectes, tant acadèmics com professionals, es donin suport en una base sòlida i amb futur.