Llista enllaçada
En la informàtica, una llista enllaçada és una de les estructures de dades fonamentals, i pot ser usada per a implementar altres estructures de dades. Consisteix en una seqüència de nodes, en els quals es guarden camps de dades arbitràries i una o dues referències (punters) al node anterior i/o posterior. El principal benefici de les llistes enllaçades respecte als array convencionals és que l'ordre dels elements enllaçats pot ser diferent de l'ordre d'emmagatzematge en la memòria o el disc, permetent que l'ordre de recorregut de la llista siga diferent del d'emmagatzematge.
Una llista enllaçada és un tipus de dada acte-referenciat perquè contenen un punter o link (enllaç) a altra dada del mateix tipus. Les llistes enllaçades permeten insercions i eliminació de nodes en qualsevol punt de la llista en temps constant (suposant que aquest punt està prèviament identificat o localitzat), però no permeten un accés aleatori. Existeixen diferents tipus de llistes enllaçades: Llista Enllaçades Simples, Llistes Doblement Enllaçades, Llistes Enllaçades Circulars i Llistes Enllaçades Doblement Circulars.
Les llistes enllaçades poden ser implementades en molts llenguatges. Llenguatges tals com Lisp i Scheme té estructures de dades ja construïdes, juntament amb operacions per a accedir a les llistes enllaçades. Llenguatges imperatius o orientats a objectes tals com C o C++ i Java, respectivament, disposen de referències per a crear llistes enllaçades.
Història
[modifica]Les llistes enllaçades foren desenvolupades en 1955-56 per Cliff Shaw i Herbert Simon en RAND Corporation com la principal estructura de dades per a la seua Llenguatge de Processament de la Informació (IPL). IPL fou usat pels autors per a desenvolupar diversos programes relacionats amb la intel·ligència artificial, inclosa la Màquina de la Teoria General, el Solucionador de Problemes Generals, i un programa informàtic d'escacs. Es va publicar en IRE Transactions on Information Theory en 1956, i en diferents conferències entre 1957-1959, inclosa Proceedings of the Western Joint Computer en 1957 i 1958, i en Information Processing (Procendents de la primera conferència internacional del processament de la informació de la Unesco) en 1959. El diagrama clàssic actual, que consisteix en blocs que representen nodes de la llista amb fletxes apuntant als successius nodes de la llista, va aparèixer en Programming the Logic Theory Machine, de Newell i Shaw. Newell i Simon foren reconeguts pel ACM Turing Award en 1975 per “fer contribucions bàsiques a la intel·ligència artificial, a la psicologia del coneixement humà i al processament de les llistes”.
El problema dels traductors del processament natural del llenguatge conduí a Victor Yngve de l'Institut Tecnològic de Massachusetts (MIT) a usar llistes enllaçades com estructura de dades en la seua COMIT, llenguatge de programació per a computadors, que va investigar en el camp de la Lingüística computacional. Un informe d'aquest llenguatge, titulat “A programming language for mechanical translation” aparegué en Mechanical Translation en 1958.
LISP, el principal processador de llistes, va ser creat en 1958. Una de les majors estructures de dades de LISP és la llista enllaçada.
Entorn dels 60, la utilitat de les llistes enllaçades i els llenguatges que utilitzaven aquestes estructures com la seua principal representació de dades estava bé establida. Bert Green del MIT Lincoln Laboratory, va publicar un estudi titulat Computer languages for symbol manipulation en IRE Transaction on Human Factors in Electronics al març de 1961 que resumia els avantatges de les llistes enllaçades. Un posterior article, A Comparison of list-processing computer languages de Bobrow and Raphael, apareixia en Communications of the ACM a l'abril de 1964.
Molts sistemes operatius desenvolupats per Technical Systems Consultants (originalment de West Lafayette Indiana i després de Raleigh, Carolina del Nord) van usar llistes enllaçades simples com estructures de fitxers. Un directori d'entrada apuntava al primer sector d'un fitxer i donava com a resultat porcions de la localització del fitxer mitjançant punters. Els sistemes que utilitzaven aquesta tècnica incloïen Flex (per al Motorola 6800 CPU), mini-Flex (la mateixa CPU) i Flex9 (per al Motorola 6809 CPU). Una variant desenvolupada per TSC es va comercialitzar a Smoke Signal Broadcasting a Califòrnia, usant llistes doblement enllaçades de la mateixa manera.
El sistema operatiu TSS, desenvolupat per IBM per a les màquines System 360/370, usava una llista doblement enllaçada per al seu catàleg de fitxers de sistema. L'estructura del directori era similar a Unix, on un directori podia contenir fitxers i/o altres directoris que es podien estendre a qualsevol profunditat. Una utilitat va ser creada per a arreglar problemes del sistema després d'una fallada des de les porcions modificades del catàleg de fitxers que estaven de vegades en memòria quan ocorria la fallada. Els problemes eren detectats per comparança dels links posterior i anterior per consistència. Si el següent enllaç (link) era corrupte i l'anterior enllaç del node infectat era trobat, el posterior link era assignat al node amb el link de l'anterior.
Tipus de Llistes Enllaçades
[modifica]Llistes enllaçades lineals
[modifica]Llistes simplement encadenades
[modifica]La llista enllaçada bàsica és la llista simplement encadenada la qual té una dada i un enllaç a un node. Aquest enllaç apunta al següent node en la llista, o al valor Nul si la llista està buida o si és l'últim node.
Una llista simplement encadenada conté dos valors: el valor del node i un enllaç al següent node
Llista Doblement Enllaçada
[modifica]Un tipus de llista enllaçada més sofisticat és la llista doblement enllaçada o llista enllaçada de dues vies. Cada node té dos enllaços: un apunta al node anterior, o apunta al valor NULL o a la llista buida si és el primer node; i altre que apunta al node següent, o apunta al valor NULL o a la llista buida si és l'últim node.
Una llista doblement enllaçada conté tres valors: el valor, l'enllaç al node següent, i l'enllaç a l'anterior
En algun llenguatge de molt baix nivell, una llista enllaçada XOR ofereix una via per a implementar llistes doblement enllaçades, fent servir una sola paraula per a ambdós enllaços, encara que l'ús d'aquesta tècnica no se sol utilitzar.
Llistes enllaçades circulars
[modifica]En una llista enllaçada circular, el primer i l'últim node estan units junts. Açò es pot fer tant per a llistes enllaçades simples com per a les doblement enllaçades. Per a recórrer una llista enllaçada circular podem començar per qualsevol node i seguir la llista en qualsevol adreça fins que es regresse fins al node original. Des d'altre punt de vista, les llistes enllaçades circulars poden ser vistes com a llistes sense començament ni fi. Aquest tipus de llistes és el més usat per a dirigir buffers per a “ingerir” dades, i per a visitar tots els nodes d'una llista a partir d'un dau.
Una llista enllaçada circular que conté tres valors sencers
Llistes enllaçades circulars simples
[modifica]Cada node té un enllaç, similar al de les llistes enllaçades simples, excepte que el següent node de l'últim apunta al primer. Com en una llista enllaçada simple, els nous nodes poden ser solament eficientment inserits després d'un que ja tinguem referenciat. Per aquesta raó, és usual quedar-se amb una referència solament a l'últim element en una llista enllaçada circular simple, açò ens permet ràpides insercions al principi, i també permet accessos al primer node des del punter de l'últim node. [1]
Llista Enllaçada Doblement Circular
[modifica]En una llista enllaçada doblement circular, cada node té dos enllaços, similars als de la llista doblement enllaçada, excepte que l'enllaç anterior del primer node apunta a l'últim i l'enllaç següent de l'últim node, apunta al primer. Com en una llista doblement enllaçada, les insercions i eliminacions poden ser fetes des de qualsevol punt amb accés a algun node proper. Encara que estructuralment una llista circular doblement enllaçada no té ni principi ni fi, un punter d'accés extern pot establir el node apuntat que està en el cap o al node cua, i així mantenir l'ordre tan bé com en una llista doblement enllaçada.
Nodes Sentinelles
[modifica]De vegades les llistes enllaçades tenen un node sentinella (també anomenat fals node o node fictici) al principi i/o al final de la llista, el qual no és usat per a guardar dades. El seu propòsit és simplificar o agilitar algunes operacions, assegurant que qualsevol node té altre anterior o posterior, i que tota la llista (fins i tot alguna que no continga dades) sempre tinga un “primer i últim” node.
Aplicacions de les llistes enllaçades
[modifica]Les llistes enllaçades són usades com mòduls per a moltes altres estructures de dades, tals com piles, cues i les seues variacions.
El camp de dades d'un node pot ser altra llista enllaçada. Mitjançant aquest mecanisme, podem construir moltes estructures de dades enllaçades amb llistes; aquesta pràctica té el seu origen en el llenguatge de programació Lisp, on les llistes enllaçades són una estructura de dades primària (encara que no l'única), i ara és una característica comuna en l'estil de programació funcional.
De vegades, les llistes enllaçades són usades per a implementar arrays associatius, i aquestes en el context de les cridades llistes associatives. Hi ha pocs avantatges en aquest ús de les llistes enllaçades; hi ha millors formes d'implementar aquestes estructures, per exemple amb arbres binaris de recerca equilibrats. No obstant això, de vegades una llista enllaçada és dinàmicament creada fora d'un subconjunt propi de nodes semblant a un arbre, i són usades més eficientment per a recórrer aquesta sèrie de dades
Avantatges
[modifica]Com moltes opcions en programació i desenvolupament, no existeix un únic mètode correcte per a resoldre un problema. Una estructura de llista enllaçada pot treballar bé en un cas però causar problemes en uns altres. Heus ací una llista amb un alguns dels avantatges més comuns que impliquen les estructures de tipus llesta. En general, tenint una col·lecció dinàmica on els elements estan sent afegits i eliminats freqüentment i importa la localització dels nous elements introduïts s'incrementa el benefici de les llistes enllaçades.
Llistes Enllaçades vs. Arrays
[modifica]| Array | Llista Enllaçada | |
|---|---|---|
| Indexat | O(1) | O(n) |
| Inserció / Eliminació al final | O(1) | O(1) or O(n)[2] |
| Inserció / Eliminació en la meitat | O(n) | O(1) |
| Persistència | No | Simples sí |
| Localització | Bona | Dolenta |
Les llistes enllaçades posseeixen molts avantatges sobre els arrays. Els elements es poden inserir en una llista indefinidament mentre que un array tard o d'hora s'omplirà o necessitarà ser redimensionat, una costosa operació que fins i tot pot no ser possible si la memòria es troba fragmentada.
En alguns casos es poden assolir estalvis de memòria emmagatzemant la mateixa ‘cua’ d'elements entre dos o més llestes – és a dir, la llista acaba en la mateixa seqüència d'elements. D'aquesta manera, un pot afegir nous elements al capdavant de la llista mantenint una referència tant al nou com als vells elements - un exemple simple d'una estructura de dades persistent.
Per altra banda, els arrays permeten accés aleatori mentre que les llistes enllaçades només permeten accés seqüencial als elements. Les llistes enllaçades simples, de fet, solament poden ser recorregudes en una adreça. Açò fa que les llistes siguen inadequades per a aquells casos en els quals és útil cercar un element pel seu índex ràpidament, com el heapsort. L'accés seqüencial en els arrays també és més ràpid que en les llistes enllaçades.
Altre desavantatge de les llistes enllaçades és l'emmagatzematge extra necessari per a les referències, que a menuts les fan poc pràctiques per a llistes de menudes dades com caràcters o valors booleans.
També pot resultar lent i abusiu assignar memòria per a cada nou element.
Existeix una varietat de llistes enllaçades que inclouen els problemes anteriors per a resoldre'ls.
Un bon exemple que mostra els pros i contres de l'ús de arrays sobre llistes enllaçades és la implementació d'un programa que resolga el problema de Josephus. Aquest problema consisteix en un grup de persones amatents en forma de cercle. Es comença a partir d'una persona predeterminada i es conta n vegades, la persona n-èsima es trau del cercle i es torna a tancar el grup. Aquest procés es repeteix fins que queda una sola persona, que és la qual gana. Aquest exemple mostra les forces i debilitats de les llistes enllaçades enfront dels arrays, ja que veient a la gent com nodes connectats entre si en una llista circular s'observa com és més fàcil suprimir aquests nodes. No obstant això, es veu com la llista perdrà utilitat quan calga trobar la següent persona a esborrar. D'altra banda, en un array suprimir els nodes serà costós, ja que no es pot llevar un element sense reorganitzar la resta. Però en la recerca de la n-èsima persona tan sols n'hi ha prou amb indicar l'índex n per a accedir a ell resultant molt més eficient.
Doblement Enllaçades vs. Simples Enllaçades
[modifica]Les llistes doblement enllaçades requereixen més espai per node i les seues operacions bàsiques resulten més costoses però ofereixen una major facilitat per a manipular, ja que permeten l'accés seqüencial a llista en ambdues adreces. En particular, un pot inserir o esborrar un node en un nombre fix d'operacions donant únicament l'adreça d'aquest node (Les llistes simples requereixen l'adreça del node anterior per a inserir o suprimir correctament). Alguns algorismes requereixen l'accés en ambdues adreces.
Circulars Enllaçades vs. Lineals Enllaçades
[modifica]Les llistes circulars són més útils per a descriure estructures circulars i tenen l'avantatge de poder recórrer la llista des de qualsevol punt. També permeten l'accés ràpid al primer i últim element per mitjà d'un punter simple.
Nodes Sentinelles (header nodes)
[modifica]La recerca comuna i els algorismes d'ordenació són menys complicats si s'usen els cridats Nodes Sentinelles o Nodes Ficticis, on cada element apunta a altre element i mai a nul. El Node Sentinella o Punter Cap conté, com un altre, un punter següent que apunta al que es considera com primer element de la llista. També conté un punter previ que fa el mateix amb l'últim element.
El Node Sentinella és definit com a altre node en una llista doblement enllaçada, l'assignació del punter front no és necessària i els punters anterior i següent estaran apuntant a si mateix en aqueix moment.
Si els punters anterior i següent apunten al Node Sentinella la llista es considera buida. En altre cas, si a la llista se li afigen elements ambdós punters apuntaran a altres nodes.
Aquests Nodes Sentinelles simplifiquen molts les operacions però cal assegurar-se que els punters anterior i següent existeixen a cada moment.
Com a avantatge eliminen la necessitat de guardar la referència al punter del principi de la llista i la possibilitat d'assignacions accidentals. Per contra, usen massa emmagatzematge extra i resulten complicats en algunes operacions.
Operacions sobre llistes enllaçades
[modifica]Quan es manipulen llistes enllaçades, cal anar amb compte amb no usar valors que hàgem d'invalidar en assignacions anteriors. Açò fa que els algorismes d'inserir i esborrar nodes en les llistes siguen una mica especials. A continuació s'exposa el pseudocodi per a afegir i esborrar nodes en llistes enllaçades simples, dobles i circulars.
Llistes Enllaçades Lineals
[modifica]Llistes simplement encadenades
[modifica]La nostra estructura de dades (node) tindrà dos camps, dada i següent. Cada node formarà part d'una Llista que contindrà una referència al primer node (o Nul en cas d'estar buida).
record Node {
dada //La dada emmagatzemada en el node
seguent //Una referència al següent node, nul per a l'últim node
}
record Llista {
Node inici //Apunta al primer node de la llista; nul en cas de ser una llista buida
}
Per realitzar un recorregut en una llista simplement encadenada, s'ha de començar per inici i anar iterant fins a arribar a l'últim node.
node := llista.inici
mentre node ≠ Nul {
node := node.seguent
}
El següent codi insereix un element a continuació d'un altre en una llista simple. El diagrama mostra com funciona.
funcio AfegirAbans(Node node, Node p) {
p.seguent := node.seguent
node.seguent := p
}
En inserir a l'inici un nou node, requereix que s'hagi d'actualitzar la primera referencia (inici).
funcio AfegirInici(Llista llista, Node p) {
p.seguent := llista.inici
llista.inici := p
}
De manera similar, tenim funcions per a esborrar un node donat o per esborrar el node inicial de la llista. Veure diagrama.
funcio EliminarDespres(Node p) { //Elimina el node següent
q := p.seguent
p.seguent := p.seguent.seguent
destruir q
}
funcio EliminarInici(Llista llista) {
q := llista.inici
llist.inici := llista.inici.seguent //En cas de ser l'últim element es posa a Nul
destruir q
}
Adjuntar una llista enllaçada a una altra pot resultar ineficient llevat que es guarde una referència a la cua de la llista, perquè si no hauríem de recórrer la llista en ordre fins a arribar a la cua i després afegir la segona llista.
Llistes Doblement Enllaçades
[modifica]Amb aquestes llistes és necessari actualitzar molts més punters però també es necessita menys informació perquè podem usar un punter per a recórrer cap arrere i consultar elements. Es creen noves operacions i elimina alguns casos especials. Afegim el camp anterior als nostres nodes, apuntant a l'element anterior, i UltimoNode a la nostra estructura, el qual sempre apunta a l'últim element de la llista. PrimerNode i UltimoNode sempre estan a nul en la llista buida.
record Node {
data // La dada emmagatzemada en el node
next // Una referència al node següent, nul per a l'últim node
prev // Una referència al node anterior, nul per al primer node
}
record List {
Node firstNode // apunta al primer node de la llista; nul per a la llista buida
Node lastNode // apunta al últim node de la llista; nul per a la llista buida
}
Formes de recórrer la llista:
Cap avant
node := list.firstNode while node ≠ null <do something with node.data> node := node.next
Cap arrere
node := list.lastNode while node ≠ null <do something with node.data> node := node.prev
Aquestes funcions simètriques afigen un node després o abans d'un dau, com el diagrama mostra:
function insertAfter(List list, Node node, Node newNode) newNode.prev := node newNode.next := node.next if node.next = null node.next := newNode list.lastNode := newNode else node.next.prev := newNode node.next := newNode
function insertBefore(List list, Node node, Node newNode) newNode.prev := node.prev newNode.next := node if node.prev is null node.prev := newNode list.firstNode := newNode else node.prev.next := newNode node.prev := newNode
També necessitem una funció per a inserir un node al començament d'una llista possiblement buida.
function insertBeginning(List list, Node newNode) if list.firstNode = null list.firstNode := newNode list.lastNode := newNode newNode.prev := null newNode.next := null else insertBefore (list, list.firstNode, newNode)
Una funció simètrica que insereix al final:
function insertEnd(List list, Node newNode) if list.lastNode = null insertBeginning (list, newNode) else insertAfter (list, list.lastNode, newNode)
Esborrar un node és fàcil, solament requereix usar amb cura firstNode i lastNode.
function remove(List list, Node node) if node.prev = null list.firstNode := node.next else node.prev.next := node.next if node.next = null list.lastNode := node.prev else node.next.prev := node.prev destroy node
Una conseqüència especial d'aquest procediment és que esborrant l'últim element d'una llista es posen PrimerNode i UltimNode a nul, havent-hi llavors un problema en una llista que tinga un únic element.
Llistes Enllaçades Circulars
[modifica]Aquestes poden ser simples o doblement enllaçades. En una llista circular tots els nodes estan enllaçats com un cercle, sense usar nul. Per a llistes amb front i final (com una cua), es guarda una referència a l'últim node de la llista. El següent node després de l'últim seria el primer de la llista. Els elements es poden afegir pel final i esborrar-se pel principi en tot moment.
Ambdós tipus de llistes circulars tenen l'avantatge de poder-se recórrer completament començant des de qualsevol node. Açò ens permet normalment evitar l'ús de PrimerNode i UltimNode, encara que si la llista estiguera buida, necessitaríem un cas especial, com una variable UltimNode que apunte a algun node en la llista o nul si està buida.
Les operacions per a aquestes llistes simplifiquen inserir i esborrar nodes en una llista buida però introdueixen casos especials en la llista buida.
Llistes Enllaçades Doblement Circulars
[modifica]Assumint que someNode és algun node en una llista no buida, aquesta llista presenta el començament d'una llista amb someNode.
Cap avant
node := someNode do do something with node.value node := node.next while node != someNode
Cap arrere
node := someNode do do something with node.value node := node.prev while node != someNode
Aquesta funció insereix un node en una llista enllaçada doblement circular després d'un element donat:
function insertAfter(Node node, Node newNode) newNode.next := node.next newNode.prev := node node.next.prev := newNode node.next := newNode
Per fer "insertBefore", podem simplificar "insertAfter (node.prev, newNode)". Inserir un element en una llista que pot estar buida requereix una funció especial.
function insertEnd(List list, Node node) if list.lastNode = null node.prev := node node.next := node else insertAfter (list.lastNode, node) list.lastNode := node
Per a inserir al principi simplifiquem "insertAfter (list.lastNode, node)".
function remove(List list, Node node) if node.next = node list.lastNode := null else node.next.prev := node.prev node.prev.next := node.next if node = list.lastNode list.lastNode := node.prev; destroy node
Com una llista doblement enllaçada, "removeAfter" i "removeBefore" pot ser implementada amb "remove (list, node.prev)" i "remove (list, node.next)".
Llistes enllaçades usant Arrays de Nodes
[modifica]Els llenguatges que no accepten qualsevol tipus de referència poden crear unions reemplaçant els punters per índexs d'un array. L'avantatge és de mantenir un array d'entrades, on cada entrada té camps sencers indicant l'índex del següent element de l'array. Pot haver-hi nodes sense usar-se. Si no hi ha suficient espai, poden usar-se arrays paral·lels.
Ací un exemple:
record Entry {
integer next; // índex de la nova entrada en l'array
integer prev; // entrada prèvia
string name;
real balance;
}
Creat un array amb aquesta estructura, i una variable sencera per a emmagatzemar l'índex del primer element, una llista enllaçada pot ser construïda:
integer listHead; Entry Records[1000];
Les utilitats d'aquesta proposta són:
- La llista enllaçada pot ser moguda sobre la memòria i també ser ràpidament serialitzada per a emmagatzemar-la en un disc o transferir-la sobre una xarxa.
- Especialment per a una llista menuda, els arrays indexats poden ocupar molt menys espai que un conjunt de punters.
- La localitat de referència pot ser millorada guardant els nodes junts en memòria i sent reordenats periòdicament.
Alguns desavantatges són:
- Incrementa la complexitat de la implementació.
- Usar un fons general de memòria deixa més memòria per a altres dades si la llista és més menuda de l'esperat o si molts nodes són alliberats.
- El creixement d'un array quan està ple no pot donar-se lloc (o caldria redimensionar-lo) mentre que trobar espai per a un nou node en una llesta resulta possible i més fàcil.
Per aquestes raons, la proposta s'usa principalment per a llenguatges que no suporten assignació de memòria dinàmica. Aquests desavantatges s'atenuen també si la grandària màxima de la llista es coneix en el moment en el qual l'array es crea.
Llenguatges suportats
[modifica]Molts llenguatges de programació tals com Lisp i Scheme tenen llistes enllaçades simples ja construïdes. En molts llenguatges de programació, aquestes llistes estan construïdes per nodes, cadascun anomenat cons o cel·la cons. Les cel·les cons tenen dos camps: el car, una referència de la dada al node, i el cdr, una referència al següent node. Encara que les cel·les cons poden ser usades per a construir altres estructures de dades, aquest és el seu principal objectiu.
En llenguatges que suporten tipus abstractes de dades o plantilles, les llistes enllaçades ADTs o plantilles estan disponibles per a construir llistes enllaçades. En altres llenguatges, les llistes enllaçades són típicament construïdes usant referències juntament amb el tipus de dada *record. Ací tenim un exemple complet en C:
#include <stdio.h> /* for printf */
#include <stdlib.h> /* for malloc */
typedef struct ns {
int data;
struct ns *next;
} node;
node *list_add(node **p, int i) {
/* alguns compiladors no requereixen un càsting del valor de la tornada per a malloc */
node *n = (node *)malloc(sizeof(node));
if (n == NULL)
return NULL;
n->next = *p;
*p = n;
n->data = i;
return n;
}
void list_remove(node **p) { /* esborrar cap*/
if (*p != NULL) {
node *n = *p;
*p = (*p)->next;
free(n);
}
}
node **list_search(node **n, int i) {
while (*n != NULL) {
if ((*n)->data == i) {
return n;
}
n = &(*n)->next;
}
return NULL;
}
void list_print(node *n) {
if (n == NULL) {
printf("lista esta vacía\n");
}
while (n != NULL) {
printf("print %p %p %d\n", n, n->next, n->data);
n = n->next;
}
}
int main(void) {
node *n = NULL;
list_add(&n, 0); /* llista: 0 */
list_add(&n, 1); /* llista: 1 0 */
list_add(&n, 2); /* llista: 2 1 0 */
list_add(&n, 3); /* llista: 3 2 1 0 */
list_add(&n, 4); /* llista: 4 3 2 1 0 */
list_print(n);
list_remove(&n); /* esborrar primer(4) */
list_remove(&n->next); /* esborrar nou segon (2) */
list_remove(list_search(&n, 1)); /* eliminar la cel·la que conté el 1 (primera) */
list_remove(&n->next); /* eliminar segon node del final(0)*/
list_remove(&n); /* eliminar últim node (3) */
list_print(n);
return 0;
}
I ara una possible especificació de Llistes Enllaçades en Maude
fmod LISTA-GENERICA {X :: TRIV} is
protecting NAT .
*** tipus
sorts ListaGenNV{X} ListaGen{X} .
subsort ListaGenNV{X} < ListaGen{X} .
*** generadors
op crear : -> ListaGen{X} [ctor].
op cons : X$Elt ListaGen{X} -> ListaGenNV{X} [ctor].
*** constructors
op _::_ : ListaGen{X} ListaGen{X} -> ListaGen{X} [assoc id: crear ]. *** concatenació
op invertir : ListaGen{X} -> ListaGen{X} .
op resto : ListaGenNV{X} -> ListaGen{X} .
*** selectors
op primero : ListaGenNV{X} -> X$Elt.
op esVacia? : ListaGen{X} -> Bool.
op longitud : ListaGen{X} -> Nat.
*** variables
vars L L1 L2 : ListaGen{X} .
vars E E1 E2 : X$Elt.
*** equacions
eq esVacia?(crear) = true.
eq esVacia?(cons(E, L)) = false.
eq primero(cons(E, L)) = E .
eq resto(cons(E, L)) = L .
eq longitud(crear) = 0.
eq longitud(cons(E, L)) = 1 + longitud(L).
eq cons(E1, L1) :: cons(E2, L2) = cons(E1, L1 :: cons(E2, L2)).
eq invertir(crear) = crear.
eq invertir(cons(E, L)) = invertir(L) :: cons(E, crear).
endfm
Emmagatzematge intern i extern
[modifica]Quan es construeix una llista enllaçada, ens enfrontem a l'elecció de si emmagatzemar les dades de la llista directament en els nodes enllaçats de la llista, cridat emmagatzematge intern, o simplement emmagatzemar una referència a la dada, cridat emmagatzematge extern. L'emmagatzematge intern té l'avantatge de fer accessos a les dades més eficients, requerint menys emmagatzematge global, tenint millor referència de localitat, i simplifica la gestió de memòria per a la llista (les dades són allotjats i desallotjats al mateix temps que els nodes de la llista).
L'emmagatzematge extern, d'altra banda, té l'avantatge de ser més genèric, en la mateixa estructura de dades i codi màquina pot ser usat per a una llista enllaçada, no importa com siga la seua grandària o les dades. Açò fa que siga més fàcil col·locar la mateixa dada en múltiples llistes enllaçades. Encara que amb l'emmagatzematge intern les mateixes dades poden ser col·locats en múltiples llistes incloent múltiples referències següents en l'estructura de dades del node, açò podria ser llavors necessari per a crear rutines separades per a afegir o esborrar cel·les basades en cada camp. Açò és possible creant llistes enllaçades d'elements addicionals que usen emmagatzematge intern usant emmagatzematge extern, i tenint les cel·les de les llistes enllaçades addicionals emmagatzemades les referències als nodes de les llistes enllaçades que contenen les dades.
En general, si una sèrie d'estructures de dades necessita ser inclosa en múltiples llistes enllaçades, l'emmagatzematge extern és el millor enfocament. Si una sèrie d'estructures de dades necessiten ser incloses en una sola llista enllaçada, llavors l'emmagatzematge intern és lleugerament millor, llevat que un paquet genèric de llistes genèriques que use emmagatzematge extern estiga disponible. Així mateix, si diferents sèries de dades que poden ser emmagatzemats en la mateixa estructura de dades són inclosos en una llista enllaçada simple, llavors l'emmagatzematge intern pot ser millor.
Altre enfocament que pot ser usat amb alguns llenguatges implica tenir diferents estructures de dades, però totes tenen els camps inicials, incloent la següent (i anterior si és una llista doblement enllaçada) referència en la mateixa localització. Després de definir estructures distintes per a cada tipus de dada, una estructura genèrica pot ser definida perquè continga la mínima quantitat de dades compartides per totes les estructures i continguts al principi de les estructures. Llavors les rutines genèriques poden ser creades usant les mínimes estructures per a portar a terme les operacions dels tipus de les llistes enllaçades, però separant les rutines que poden manejar les dades específiques. Aquest enfocament és usat sovint en rutines d'anàlisis de missatges, on diversos tipus de missatges són rebuts, però tots comencen amb la mateixa sèrie de camps, generalment incloent un camp per al tipus de missatge. Les rutines genèriques són usades per a afegir nous missatges a una cua quan són rebuts, i eliminar-los de la cua en ordre per a processar-los. El camp de tipus de missatge és usat per a cridar a la rutina correcta per a processar el tipus específic de missatge.
Exemples d'emmagatzematge intern i extern
[modifica]Suposant que volem crear una llista enllaçada de famílies i els seus membres. Usant emmagatzematge intern, l'estructura podria ser com la següent:
record member { // membre d'una família
member next
string firstName
integer age
}
record family { // //la pròpia família
family next
string lastName
string address
member members //de la llista de membres de la família
}
Per a mostrar una llista completa de famílies i els seus membres usant emmagatzematge intern podríem escriure alguna cosa com açò:
aFamily := Families //començament de la llista de famílies
while aFamily ≠ null { // bucle a través de la llista de famílies
print information about family
aMember := aFamily.members // agafar cap d'aquesta llista de membres d'aquesta família
while aMember ≠ null { //bucle per a recórrer la llista de membres
print information about member
aMember := aMember.next
}
aFamily := aFamily.next
}
Usant emmagatzematge extern, nosaltres podríem crear les següents estructures:
record node { // estructura genèrica d'enllaç
node next
pointer data // punter genèric de la dada al node
}
record member { // estructura d'una família
string firstName
integer age
}
record family { // estructura d'una família
string lastName
string address
node members // cap de la llista de membres d'aquesta família
}
Per a mostrar una llista completa de famílies i els seus membres usant emmagatzematge extern, podríem escriure:
famNode := Families // comienzo de la cabeza de una lista de familias
while famNode ≠ null { // bucle de llista de famílies
aFamily = (family) famNode.data // extraure família del node
print information about family
memNode := aFamily.members // agafar llista de membres de família
while memNode ≠ null { bucle de llista de membres
aMember := (member) memNode.data // extraure membre del node
print information about member
memNode := memNode.next
}
famNode := famNode.next
}
Cal fixar-se que quan usem emmagatzematge extern, es necessita fer un pas extra per a extraure la informació del node i fer un càsting dins del propi tipus de la dada. Açò és perquè ambdues llistes, de famílies i membres, són emmagatzemades en dues llistes enllaçades usant la mateixa estructura de dades (node), i aquest llenguatge no té tipus paramètrics.
Si coneixem el nombre de famílies a les quals un membre pot pertànyer en temps de compilació, l'emmagatzematge intern treballa millor. Si, no obstant això, un membre necessita ser inclòs en un nombre arbitrari de famílies, sabent el nombre específic de famílies sol en temps d'execució, l'emmagatzematge extern serà necessari.
Agilització de la recerca
[modifica]Cercant un element específic en una llista enllaçada, fins i tot si aquesta és ordenada, normalment requereixen temps O (n) (recerca lineal). Aquesta és un dels principals desavantatges de les llistes enllaçades respecte a altres estructures. A més algunes de les variants exposades en la secció anterior, hi ha nombroses vies simples per a millorar el temps de recerca.
En una llista desordenada, una forma simple per abaixar el temps de recerca mig és el moure al capdavant de forma heurística, que simplement mou un element al principi de la llista una vegada que és oposat.
Aquesta idea, útil per a crear caches simples, assegura que l'ítem usat més recentment és també el més ràpid a ser trobat altra vegada.
Altre enfocament comú és indexitzar una llista enllaçada usant una estructura de dades externa més eficient. Per exemple, podem construir un arbre roig-negre o una taula hash els elements de la qual estan referenciats pels nodes de les llistes enllaçades. Poden ser construïts múltiples índexs en una llista simple. El desavantatge és que aquests índexs pot necessitar ser actualitzats cada vegada que un node és afegit o eliminat (o almenys, abans que l'índex siga utilitzat altra vegada).
Estructures de dades relacionades
[modifica]Tant les piles com les cues són sovint implementades usant llistes enllaçades, i simplement restringint el tipus d'operacions que són suportades.
La skip list, o llista per salts, és una llista enllaçada augmentada amb capes de punters per a salts ràpids sobre grans nombres d'elements, i descendint feia la següent capa. Aquest procés continua fins a arribar a la capa inferior, la qual és la llista actual.
Un arbre binari pot ser vist com un tipus de llista enllaçada on els elements estan enllaçats entre ells mateixos de la mateixa forma. El resultat és que cada node pot incloure una referència al primer node d'una o dues llistes enllaçades, cadascú amb el seu contingut, formant així els subarbres sota el node.
Una llista enllaçada desenrotllada és una llista enllaçada els nodes de la qual conté un array de dades. Açò millora l'execució de la caché, sempre que les llistes d'elements estiguen contigües en memòria, i redueixen la sobrecàrrega de la memòria, perquè necessites menys metadades per a guardar cada element de la llista.
Una taula hash pot usar llistes enllaçades per a guardar cadenes d'ítems en la mateixa posició de la taula hash.
Referències
[modifica]- ↑ Preiss, Bruno R. Data Structures and Algorithms with Object-Oriented Design Patterns in Java. Wiley, 1999, page 97, 165. ISBN 0471-34613-6.
- ↑ Si mantenint un enllaç a la cua de la llista, time is O(1); if the entire list must be searched to locate the tail link, O(n)
Bibliografia
[modifica]- National Institute of Standards and Technology (16 d'agost del 2004). Definition of a linked list. Retrieved 14 de desembre del 2004.
- Antonakos, James L. and Mansfield, Kenneth C., Jr. Practical Data Structures Using C/C++ (1999). Prentice-Hall. ISBN 0-13-280843-9, pp. 165–190
- Collins, William J. Data Structures and the Java Collections Framework (2002,2005) New York, NY: McGraw Hill. ISBN 0-07-282379-8, pp. 239–303
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introductions to Algorithms (2003). MIT Press. ISBN 0-262-03293-7, pp. 205–213, 501–505
- Green, Bert F. Jr. (1961). Computer Languages for Symbol Manipulation. IRE Transactions on Human Factors in Electronics. 2 pp. 3-8.
- McCarthy, John (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM. «Enllaç». HTML DVI PDF PostScript
- Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Sections 2.2.3–2.2.5, pp.254–298.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.2: Linked lists, pp.204–209.
- Newell, Allen and Shaw, F. C. (1957). Programming the Logic Theory Machine. Proceedings of the Western Joint Computer Conference. pp. 230-240.
- Parlante, Nick (2001). Linked list basics. Stanford University. PDF
- Sedgewick, Robert Algorithms in C (1998). Addison Wesley. ISBN 0-201-31452-5, pp. 90–109
- Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis (1998). NJ: Prentice Hall. ISBN 0-13-660911-2, pp. 77–102
- Wilkes, Maurice Vincent (1964). An Experiment with a Self-compiling Compiler for a Simple List-Processing Language. Annual Review in Automatic Programming 4, 1. Published by Pergamon Press.
- Wilkes, Maurice Vincent (1964). Lists and Why They are Useful. Proceeds of the ACM National Conference, Philadelphia 1964 (ACM Publication P-64 page F1-1); Also Computer Journal 7, 278 (1965).
- Kulesh Shanmugasundaram (4 d'abril del 2005). Linux Kernel Linked List Explained Arxivat 2009-09-25 a Wayback Machine..
Enllaços externs
[modifica]- Descripció del Diccionari d'Algoritmes i Estructures de Dades
- Alguns materials de llistes enllaçades són disponibles des del Departament de Ciència Informàtica de la Universitat Stanford: Introducció a Les Llistes Enllaçades