Lista (számítástechnika)

Az informatikában a lista ( angol  lista ) egy elvont adattípus , amely értékek rendezett halmaza , amelyben egy bizonyos érték többször is előfordulhat. A lista egy példánya a véges sorozat matematikai koncepciójának számítógépes megvalósítása . A listában szereplő értékek előfordulását a lista elemeinek nevezzük ( angol nyelvű elem, bejegyzés vagy elem ); ha az érték többször előfordul, minden előfordulás külön elemnek minősül.  

A lista kifejezés több konkrét adatszerkezetre is utal, amelyeket az absztrakt listák, különösen a linkelt listák megvalósításában használnak .

Definíció

C. Hoare szintaktikai orientált szerkesztési módszerének jelölésével a lista definíciója a következőképpen írható fel:

Ennek a definíciónak az első sora azt jelenti, hogy a típus elemeinek listája (mondjuk: "lista vége ") az üres lista és a típus atomjának Descartes szorzatának megkülönböztetett uniója a listával . Listák létrehozásához két konstruktort használnak (a definíció második sora), amelyek közül az első üres listát hoz létre, a második pedig egy nem üres listát. Teljesen világos, hogy a második konstruktor bemenetként kap valamilyen atomot és egy listát paraméterként, és egy listát ad vissza, melynek első eleme az eredeti atom, a többi pedig az eredeti lista elemei. Vagyis az atom a lista előtagjaként szerepel, ami az oka a konstruktor ilyen elnevezésének. Az üres lista nem atom, ezért nem lehet előtaggal ellátni. Másrészt az üres lista a null elem a listák összeállításához, így minden lista a legvégén tartalmaz egy üres listát - az építés ezzel kezdődik.

A harmadik sor a lista választóit határozza meg , vagyis a listán belüli elemek eléréséhez szükséges műveleteket. A kiválasztó bemenetként egy listát vesz, és ennek a lista első elemét adja vissza, vagyis az eredmény típusa type . Ez a választó nem fogadhat üres listát bemenetként - ebben az esetben a művelet eredménye nem definiálható. A szelektor a bemenetből kapott listát adja vissza a fej levágása (az első elem) eredményeként. Ez a választó szintén nem fogadhat be üres listát, mivel ebben az esetben a művelet eredménye nem definiálható. Ezzel a két művelettel bármely elemet lekérhet a listából. Például a lista harmadik elemének (ha van ilyen) lekéréséhez egymás után kétszer kell alkalmazni a választót , majd alkalmaznia kell a választót . Más szóval, ahhoz, hogy a listában a pozícióban lévő elemet megkapjuk (az első elemnél kezdődően , ahogy az a programozásban megszokott), egyszer alkalmazni kell a kiválasztót , majd alkalmazni kell a választót .

A definíció negyedik sora a lista predikátumokat írja le , vagyis azokat a függvényeket, amelyek bizonyos feltételektől függően logikai értéket adnak vissza. Az első predikátum értéket ad vissza, ha az adott lista üres. A második predikátum fordítva működik. Végül az ötödik sor a lista részeit írja le, amelyek, mint már említettük, az üres és nem üres listák.

Tulajdonságok

Az így meghatározott adatszerkezetnek van néhány tulajdonsága:

• A lista mérete a  benne lévő elemek száma, kivéve az utolsó "null" elemet, amely definíció szerint egy üres lista.
• Az elemek  típusa ugyanaz , mint amelyre a lista épül; a lista minden elemének ilyen típusúnak kell lennie.
• Rendezett  - a lista bizonyos rendezési feltételek szerint rendezhető (például növekvő egész számok, ha a lista egész számokból áll).
• Hozzáférhetőség  – Egyes listák, a megvalósítástól függően, választókkal látják el a programozót a számozott elem közvetlen eléréséhez.
• Összehasonlíthatóság  - a listák egymással összevethetők levelezés céljából, és a megvalósítástól függően a lista-összehasonlítás művelete különböző technológiákat alkalmazhat.

A listák az azonos típusú elemkészletek tárolására szolgálnak. Az ilyen elemek a keresési funkciókhoz vagy az új elemek listába való gyors beszúrásához szükséges funkciókhoz rendezhetők.

Listák programozási nyelveken

Funkcionális nyelvek

A funkcionális nyelvek listája alapvető struktúra. A legtöbb funkcionális nyelv rendelkezik beépített lehetőségekkel a listákkal való munkavégzéshez, mint például a lista hosszának lekérése, a fej (a lista első eleme), a farok (a lista első elemét követő része), függvény alkalmazása a lista minden elemére ( Map ), a lista összehajtása stb.