Llista (estructura de dades): diferència entre les revisions

Contingut suprimit Contingut afegit
m neteja i estandardització de codi
m neteja i estandardització de codi
Línia 33:
*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 (programació)|vector]] o utilitzant una [[llista encadenada]].
 
Línia 39:
 
==Característiques==
 
Les llistes tenen les següents propietats:
 
Linha 51 ⟶ 50:
 
== 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 (programació)|Vector]]: Alguns llenguatges de programació implementen les llistes utilitzant vectors.
 
Les llistes poden ser manipulades utilitzant dos mètodes:
Linha 66 ⟶ 63:
*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 [[conjunt]]s. 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]].
Linha 73 ⟶ 70:
 
==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();
 
}
 
Linha 101 ⟶ 97:
 
Java a través de la [http://java.sun.com/j2se/1.4.2/docs/guide/collections/index.html Java Collections Framework] ofereix una interfície [http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html Llista].
 
== Vegeu també ==
* [[Node sentinella]].
* [[Llista enllaçada]]
 
== Enllaços externs ==
* [http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html Interfície List Java]
* [http://java.sun.com/j2se/1.4.2/docs/guide/collections/index.html Java ''Collections Framework'']
{{Autoritat}}
{{Viccionari-lateral|llista}}