Matrius versus llistes enllaçades
Les matrius són l'estructura de dades més utilitzada per emmagatzemar la col·lecció d'elements. La majoria dels llenguatges de programació ofereixen mètodes per declarar fàcilment matrius i accedir als elements de les matrius. La llista enllaçada, més precisament la llista enllaçada individualment, també és una estructura de dades que es pot utilitzar per emmagatzemar la col·lecció d'elements. Està format per una seqüència de nodes i cada node té una referència al següent node de la seqüència.
A la figura 1, és un fragment de codi que s'utilitza normalment per declarar i assignar valors a una matriu. La figura 2 mostra com es veuria una matriu a la memòria.
El codi anterior defineix una matriu que pot emmagatzemar 5 nombres enters i s'hi accedeix mitjançant els índexs del 0 al 4. Una propietat important d'una matriu és que la matriu sencera s'assigna com un únic bloc de memòria i cada element té el seu propi espai. a la matriu. Un cop definida una matriu, la seva mida es fixa. Per tant, si no esteu segur de la mida de la matriu en el moment de la compilació, haureu de definir una matriu prou gran per estar al costat segur. Però, la majoria de les vegades, en realitat utilitzarem menys nombre d'elements del que hem assignat. Per tant, es malgasta una quantitat considerable de memòria. D' altra banda, si la "matriu prou gran" no és realment prou gran, el programa es bloquejaria.
Una llista enllaçada assigna memòria als seus elements per separat en el seu propi bloc de memòria i l'estructura global s'obté enllaçant aquests elements com a enllaços en una cadena. Cada element d'una llista enllaçada té dos camps, tal com es mostra a la figura 3. El camp de dades conté les dades reals emmagatzemades i el camp següent conté la referència al següent element de la cadena. El primer element de la llista enllaçada s'emmagatzema com a cap de la llista enllaçada.
| dades | següent |
Figura 3: Element d'una llista enllaçada
La figura 4 mostra una llista enllaçada amb tres elements. Cada element emmagatzema les seves dades i tots els elements excepte l'últim emmagatzemen una referència a l'element següent. L'últim element conté un valor nul al seu camp següent. Es pot accedir a qualsevol element de la llista començant per l'encapçalament i seguint el punter següent fins a trobar l'element requerit.
Tot i que les matrius i les llistes enllaçades són similars en el sentit que totes dues s'utilitzen per emmagatzemar la col·lecció d'elements, incorren en diferències a causa de les estratègies que utilitzen per assignar memòria als seus elements. Les matrius assignen memòria a tots els seus elements com un sol bloc i la mida de la matriu s'ha de determinar en temps d'execució. Això faria que les matrius siguin ineficients en situacions en què no coneixeu la mida de la matriu en temps de compilació. Com que una llista enllaçada assigna memòria als seus elements per separat, seria molt eficient en situacions en què no coneixeu la mida de la llista en temps de compilació. La declaració i l'accés als elements d'una llista enllaçada no serien senzills en comparació amb com accediu directament als elements d'una matriu mitjançant els seus índexs.
