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.

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.