Tömbök vs linkelt listák
A tömbök a leggyakrabban használt adatszerkezetek az elemek gyűjteményének tárolására. A legtöbb programozási nyelv módszereket biztosít a tömbök egyszerű deklarálására és a tömbök elemeinek elérésére. A linkelt lista, pontosabban az egyedileg linkelt lista egy olyan adatstruktúra is, amely elemgyűjtemény tárolására használható. Csomópontok sorozatából áll, és minden csomópontnak van hivatkozása a sorozat következő csomópontjára.
Az 1. ábrán látható egy kódrészlet, amelyet általában egy tömb deklarálására és értékek hozzárendelésére használnak. A 2. ábra azt mutatja be, hogyan nézne ki egy tömb a memóriában.
A fenti kód egy tömböt határoz meg, amely 5 egész számot tud tárolni, és ezek 0-tól 4-ig terjedő indexekkel érhetők el. A tömb egyik fontos tulajdonsága, hogy a teljes tömb egyetlen memóriablokkként van lefoglalva, és minden elem saját helyet kap. a tömbben. Ha egy tömb definiálva van, a mérete rögzített. Tehát ha nem biztos a tömb méretében a fordítási időben, akkor elég nagy tömböt kell meghatároznia ahhoz, hogy a biztonságban legyen. De az idő nagy részében valójában kevesebb elemet fogunk használni, mint amennyit kiosztottunk. Tehát jelentős mennyiségű memória vész kárba. Másrészt, ha az „elég nagy tömb” valójában nem elég nagy, a program összeomlik.
A csatolt lista a memóriát külön-külön lefoglalja elemeihez a saját memóriablokkjában, és a teljes szerkezetet úgy kapjuk meg, hogy ezeket az elemeket láncszemként kapcsoljuk össze. A csatolt lista minden elemének két mezője van, amint az a 3. ábrán látható. Az adatmező tartalmazza a ténylegesen tárolt adatokat, a következő mező pedig a lánc következő elemére való hivatkozást. A hivatkozott lista első eleme a hivatkozott lista fejeként kerül tárolásra.
| adatok | következő |
3. ábra: Hivatkozott lista eleme
A 4. ábra egy linkelt listát ábrázol három elemből. Minden elem tárolja az adatait, és az utolsó kivételével minden elem a következő elemre való hivatkozást tárolja. Az utolsó elem a következő mezőjében null értéket tartalmaz. A lista bármely elemét elérheti úgy, hogy a fejléctől kezdi, és követi a következő mutatót, amíg el nem éri a kívánt elemet.
Annak ellenére, hogy a tömbök és a hivatkozott listák hasonlóak abban az értelemben, hogy mindkettő elemgyűjtemény tárolására szolgál, különbségek vannak bennük az elemekhez való memória lefoglalására használt stratégiák miatt. A tömbök egyetlen blokkként foglalják le a memóriát minden eleméhez, és a tömb méretét futás közben kell meghatározni. Ez hatástalanná tenné a tömböket olyan helyzetekben, amikor nem ismeri a tömb méretét a fordítási időben. Mivel egy linkelt lista külön-külön lefoglalja a memóriát az elemeihez, nagyon hatékony lenne olyan helyzetekben, amikor nem ismeri a lista méretét a fordításkor. A linkelt lista elemeinek deklarálása és elérése nem lenne egyszerű ahhoz képest, ahogyan a tömb elemeihez közvetlenül hozzáférne az indexek használatával.
