Llista enllaçada individualment vs Llista enllaçada doble
La llista enllaçada és una estructura de dades lineal que s'utilitza per emmagatzemar una col·lecció de dades. 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. Una llista enllaçada individualment està formada per una seqüència de nodes i cada node té una referència al següent node de la seqüència. Una llista doblement enllaçada conté una seqüència de nodes en què cada node conté una referència al node següent així com al node anterior.
Llista enllaçada individualment
Cada element d'una llista enllaçada individualment té dos camps, tal com es mostra a la figura 1. 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.
La figura 2 mostra una llista enllaçada individualment 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 que trobeu l'element requerit.
Llista doblement enllaçada
Cada element d'una llista doblement enllaçada té tres camps, tal com es mostra a la figura 3. De manera similar a la llista enllaçada individualment, 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. A més, el camp anterior conté la referència a l'element anterior de la cadena. El primer element de la llista enllaçada s'emmagatzema com a cap de la llista enllaçada.
La figura 4 mostra una llista doblement enllaçada amb tres elements. Tots els elements intermedis emmagatzemen referències al primer i als elements anteriors. L'últim element de la llista conté un valor nul al seu camp següent i el primer element de la llista conté un valor nul al seu camp anterior. La llista doblement enllaçada es pot recórrer cap endavant seguint les següents referències de cada element i de la mateixa manera es pot recórrer cap enrere utilitzant les referències anteriors de cada element.
Quina diferència hi ha entre la llista enllaçada individualment i la llista doblement enllaçada?
Cada element de la llista enllaçada individualment conté una referència al següent element de la llista, mentre que cada element de la llista doblement enllaçada conté referències a l'element següent i a l'element anterior de la llista. Les llistes doblement enllaçades requereixen més espai per a cada element de la llista i les operacions elementals com la inserció i la supressió són més complexes ja que s'han de tractar amb dues referències. Però les llistes d'enllaços dobles permeten una manipulació més fàcil, ja que permet recórrer la llista en direccions cap endavant i cap enrere.
