Mire jók a listák? Tudnátok gyakorlati alkalmazásukra példát mondani? Használják programokban?
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.
No, ezt értve a lista alatt, nyelvfüggő. A referencia alapú nyelvekben csak ilyen lista van, adatot érték szerint tároló nincs is. Egyébként meg akkor van értelme, ha nem akarod másolgatni az elemeket, ezért csak a címüket tárolod.
Amúgy az egy népszerű tévképzet, hogy a rendezés gyorsabb ilyenen, a beszúrás meg láncolt listán. Ki kell mérni, gyakran az érték szerint tárolt lista (C++ vector) mindenben gyorsabb, mint akármelyik másik STL adatszerkezet, a dereferálás hiánya és a kevesebb cache miss miatt. Ilyen ez az optimalizálás: mérni kell, nem hasraütni :)
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!