Lista (adatszerkezet)

A Programozás Wiki wikiből

A lista (vagy egyszerű lista) egy a tömbhöz hasonló elemi adatszerkezet, adatelemek - egy adott szempont szerint - rendezett formában történő tárolására. Ugyanakkor a lista - szemben a tömbbel - az elemeket magukat nem, csak a rájuk mutató hivatkozásokat (pointer) gyűjti és tárolja szekvenciálisan, míg a magát a listát alkotó elemek a memóriában tetszőleges szétszórva helyezkedhetnek el. A lista ugyanebből kifolyólag - és szintén szembben a tömbbel - nem csak azonos, de eltérő típusú elemek tárolására is alkalmas, amelyek mindegyike a listában elfoglalt pozíciója alapján címezhető meg, indexén keresztül.

Technikailag a listát tipikusan egy tömb segítségével valósítják meg, amelyet a lista által befoglalt elemekre hivatkozó mutatók (pointerek) tárolására használnak fel. A lista tényleges elemeinek elérése ezen mutatók feloldásán keresztül lehetséges. A lista ebből adódóan ugyanazt az egy adatelemet többször is tartalmazhatja, hiszen több index alatt is tárolható hivatkozás ugyanarra az elemre. Az ilyen adatelemen tetszőleges index alatt végrehajtott változásokat minden más index amelyen az adott elem elérhető azonnal tükrözni fogja, hiszen végső soron a memória ugyanazon területére hivatkoznak. Ugyanezen okból kifolyólag lehetőség van ugyanazon adatelemek több különböző listában történő szerepeltetésére is, amelyekben sorrendjeik eltérhetnek, így lehetőséget adva különböző rendezési elv mentén történő sorbaállításukra redundáns kópiák létrehozása és tárolása nélkül is.

A listákban a néhány bájtot meghaladó elemek effektívebben rendezhetők, mint a tömbben, hiszen elegendő csak az elemekre hivatkozó mutatókat mozgatni, maguk az elemek adattartalmának mozgatására a memóriában azonban nincs szükség. Ugyanakkor az elemek véletlenszerű beszúrása vagy törlése nagy elemszám esetén csak jóval lassabban hajtható végre, mint a láncolt listák esetében, hiszen továbbra is jelentős mennyiségű mutatóelem mozgatása vagy másolása szükséges a listán belül, ha csak nem mindig a lista végére/ről kerülnek az elemek beszúrásra/törlésre.