Llista (estructura de dades)

Aquest article és sobre la paraula llista utilitzada en el context de la informàtica. Per altres usos, vegeu Llista (desambiguació).

En informàtica, una llista és una estructura de dades seqüencial que conté una col·lecció d'elements ordenats. Una llista es diferencia d'altres estructures de dades com la pila o la cua en què a diferència d'aquestes s'hi pot modificar qualsevol element de la llista i no només algun dels extrems.

En el context de la programació orientada a objectes, una llista es defineix com una instància d'un tipus abstracte de dades (TAD) i formalitza el concepte d'una col·lecció ordenada d'entitats o objectes. Una llista és un contenidor seqüencial.

Un exemple de llista encadenada simple amb 3 valors enters

Les operacions habituals que ha d'implementar una llista són:

Les habituals dels contenidors (vegeu l'article contenidor):

Una operació per comprovar quan una llista està buida.
Una operació per obtenir el nombre d'elements de la llista
Un mètode que retorni un objecte de tipus iterador

Les específiques d'una llista:

Un constructor que crea una llista buida
Una operació per afegir un element abans o després d'una posició concreta
Una operació per eliminar un element abans o després d'una posició concreta
Una operació que ens permeti recórrer la llista

Operacions opcionals:

Una operació per afegir un element al principi
Una operació per afegir un element al final
Una operació per afegir un element després d'una posició concreta
Una operació per afegir un element abans d'una posició concreta
Una operació per eliminar un element al principi
Una operació per eliminar un element al final
Una operació per eliminar un element després d'una posició concreta
Una operació per eliminar un element abans d'una posició concreta
Una operació per reemplaçar un element per un altre
Una operació per intercanviar un element per un altre
Una operació per obtenir el primer component de la llista.
Una operació (sovint anomenada cua) per obtenir una llista formada per tots els elements de la llista excepte el primer

Hi ha dos aproximacions a l'hora d'implementar una llista, utilitzant un vector o utilitzant una llista encadenada.

Un altre nom utilitzat sovint per a llista és seqüència. Aquest mot emfatitza la idea d'ordre.

Característiques

Les llistes tenen les següents propietats:

La mida de la llista. Indica quants elements conté la llista.
Cada element de la llista té un índex o posició. Normalment el primer element de la llista té l'índex 0. Cada element subsegüent de la llista té un índex que és +1 respecte a l'anterior. Normalment l'últim element de la llista té com a índex la mida de la llista -1.
- És possible obtenir un element de la llista a partir del seu índex.
- És possible recórrer la llista incrementant l'índex.
- És possible modificar un element de la llista en una posició concreta de la llista per un altre valor, sense afectar la resta d'elements.
- És possible inserir un element en una posició concreta de la llista. Els índexs dels elements ens posicions posteriors s'han d'incrementar en +1.
- És possible eliminar un element en una posició concreta de la llista. Els índexs dels elements ens posicions anteriors s'han de decrementar en -1.

Aplicacions

En el món real podem trobar multitud d'exemples de llista (llista de la compra, llista telefònica, etc.) i concretament en informàtica s'utilitzen per emmagatzemar una llista de registres i s'utilitzen per ordenar elements.

Implementacions

Com ha hem comentat hi ha dos formes d'implementar una llista:

Llista encadenada: Cada element de la llista conté el valor de l'element i un apuntador al següent element de la llista. Va ser el primer sistema utilitzat per implementar llistes amb llenguatge Lisp. Els encadenaments poden ser simples o dobles.
Vector: Alguns llenguatges de programació implementen les llistes utilitzant vectors.

Les llistes poden ser manipulades utilitzant dos mètodes:

Iteració:. La iteració és un concepte molt lligat a la Programació imperativa.
Recursivitat:. És el sistema més utilitzat en llenguatges funcionals.

Alguns llenguatges de programació no ofereixen una estructura de dades llista però ofereixen vectors associatius o alguns tipus de taula per emular llistes.

En informàtica les llistes són més fàcils d'implementar que els conjunts. Per aquesta raó, sovint els conjunts se solen implementar com a llistes amb restriccions, com per exemple, no permetre elements duplicats i que l'ordre sigui irrellevant. Cal dir però, que les implementacions més eficients de conjunts es realitzen utilitzant taules de hash.

Si una llista està ordenada és més ràpid determinar si un element concret està o no està a la llista però a canvi és més costos manipular la llista (afegir o treure elements) quan es vol mantenir l'ordre.

Exemple d'especificació d'una llista en Java

public interface Llista<E> extends Contenidor<E>
{
public void afegirAlPrincipi(E element);

public void afegirAlFinal(E element);

public void afegirAbansDe(index, E element);

public void afegirDespresDe(index, E elem);

public void esborrarPrimer();

public void esborrar(index);

public void esborrarSeguent(index);

public void reemplacar(index, E element);

public void intercanviar(index1,index2);

public Iterador<E> elements();

La classe Iterador és un tipus de dades abstracte utilitzant freqüentment en contenidors que permet recórrer col·leccions en un cert ordre.

Java a través de la Java Collections Framework ofereix una interfície Llista.

Vegeu també

Enllaços externs

Viccionari