Llista encadenada
En el context de la informàtica, una llista encadenada és un estructura de dades fonamental que s'utilitza per implementar altres estructures. Consisteix en una seqüència de nodes on cada node conté les dades d'un element de la llista i un o dos apuntadors o enllaços, un enllaç al node següent, i un enllaç al node posterior.
Les llistes encadenades que tenen un sol enllaç per element s'anomenen llistes encadenades simples i permeten recórrer la llista en un sol sentit.
Les llistes encadenades que tenen dos enllaços per element s'anomenen llistes encadenades dobles i permeten recórrer la llista en tots dos sentits.
S'anomenen llistes encadenades circulars si el primer i l'últim node estan enllaçats. Si estan enllaçats mútuament la llista s'anomena llista encadenada circular doble i si només estan enllaçats en un sentit s'anomena llista encadenada circular simple.
La principal diferència d'una llista encadenada respecte als vectors és que l'ordre dels elements enllaçats pot ser diferent de l'ordre en què s'emmagatzemen els elements a la memòria.
Una llista encadenada és una tipus de dades auto-referenciat, ja que contenen enllaços entre dades del mateix tipus. Les llistes encadenades permeten la inserció, modificació i eliminació de nodes en un punt qualsevol amb un cost computacional constant amb independència de la mida de la llista. En canvi les cerques requereixen un cost computacional que incrementa linealment amb la mida de la llista.
Les llistes encadenades poden ser implementades en múltiples llenguatges. Llenguatges com Lisp o Scheme tenen estructures tipus llista preconstruides. Els llenguatges de programació procedimentals i els llenguatges de programació orientats a objecte com el llenguatge de programació C, C++ o Java també proporcionen llistes.
Història
[modifica]Les llistes encadenades van ser desenvolupades per primer cop el 1955-56 per Allen Newell, Cliff Shaw i Herbert Simon a l'empresa RAND Corporation com l'estructura de dades principal del llenguatge de programació Information Processing Language.
Tipus de llistes encadenades
[modifica]Llistes encadenades lineals
[modifica]Llista encadenada simple
[modifica]El tipus més simple de llista encadenada és la llista encadenada simple (també anomenada slist). Cada node té un sol enllaç que pot ser al node precedent o al node posterior depenent del sentit en què es vulgui operar amb la llista. Cal fer notar que l'últim o el primer element de la llista no té cap enllaç (valor nul null).
Una llista encadenada simple amb tres valors
Cada node té dos parts:
- La primera part conté la informació relativa al node.
- La segona part conté l'enllaç al següent node.
Les llistes encadenades simples només es poden recórrer en un sentit.
Llista encadenada doble
[modifica]Una mica més sofisticada és la llista encadenada doble o llista encadenada de dos sentits.
Cada node té 3 parts:
- La primera part conté la informació relativa al node.
- La segona part conté l'enllaç al següent node.
- La tercera part conté l'enllaç al node anterior.
Una llista encadenada doble amb 3 valors enters
El primer element i l'últim tenen cadascun un dels enllaços sense valor (valor null).
Llistes encadenades circulars
[modifica]A les llistes encadenades circulars els nodes primer i últim estan enllaçats. Això es pot fer tant amb les llistes encadenades simples com amb les llistes encadenades dobles. Les llistes encadenades circulars no tenen principi ni final.
Una llista encadenada circular de 3 elements enters
Aplicacions de les llistes encadenades
[modifica]Les llistes encadenades són utilitzades com a estructura de dades bàsica per implementar altres estructures de dades com les piles o cues i les seves variants.
Cada node d'una llista encadenada pot ser una altra llista encadenada, fet que permet implementar estructures de dades més complexes.
A vegades les llistes encadenades s'utilitzen per a implementar vectors associatius i són anomenades en aquest context llistes associatives. Aquest disseny però no és gaire recomanable.
Inconvenients
[modifica]Com acostuma a passar amb els dissenys informàtics, les llistes encadenades no són la solució ideal per a tots els casos.
Llistes encadenades versus Vectors
[modifica]| Vector | Llista encadenada | |
|---|---|---|
| Indexació | O(1) | O(n) |
| Inserint / Esborrant al final | O(1) | O(1) or O(n)[1] |
| Inserint / Esborrant per a meitat (amb un iterador) | O(n) | O(1) |
| Estructura de dades persistent | No | Llistes encadenades simples sí. |
| Localitat | Bona | Dolenta |
L'avantatge principal de les llistes encadenades respecte als vectors és que permeten que la llista creixi de forma infinita sense necessitat de modificar la mida de la llista (normalment els vectors han de definir una mida màxima d'elements i s'han d'implementar mecanismes per redimensionar-los). L'espai s'aprofita millor que un vector, ja que no es reserva memòria i d'aquesta manera no es malgasta memòria com en el cas d'un vector amb pocs elements i el programador no ha de preveure la mida de la llista a priori.
L'avantatge principal dels vectors és que permeten un accés aleatori als elements de la llista, mentre que les llistes només permeten un accés seqüencial. Això fa que les llistes encadenades no siguin adequades per a aplicacions que hagin d'accedir a qualsevol dels nodes de la llista de forma ràpida.
L'altre gran inconvenient de les llistes encadenades és l'espai extra d'emmagatzemament necessari per guardar els enllaços. Per exemple aquest fet no les fa adequades per emmagatzemar caràcters (String) o valors booleans.
Enllaços externs
[modifica]
Referències
[modifica]- ↑ Sí es manté un enllaç a la cua de la llista, el temps és 0(1); Si la llista sencera ha de ser buscada per trobar l'enllaç a la cua aleshores el temps és O(n)