Tömbök vs összekapcsolt listák
A tömbök a leggyakrabban használt adatstruktúra az elemek gyűjtésének tárolására. A legtöbb programozási nyelv módszereket kínál a tömbök egyszerű deklarálására és a tömbökben található elemek elérésére. A kapcsolt lista, pontosabban az egyesével összekapcsolt lista szintén egy adatstruktúra, amely felhasználható az elemek gyűjteményének tárolására. Csomópontok sorozatából áll, és mindegyik csomópont hivatkozik a sorozat következő csomópontjára.
Az 1. ábra egy olyan kódrészlet, amelyet általában egy tömb deklarálásához és értékeinek hozzárendeléséhez használnak. A 2. ábra azt ábrázolja, hogyan néz 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 képes tárolni, és ezekhez 0 és 4 közötti indexek férnek hozzá. A tömb egyik fontos tulajdonsága, hogy a teljes tömböt egyetlen memóriablokkként osztják ki, és minden elem saját teret kap a tömbben. Miután meghatároztuk a tömböt, annak mérete rögzül. Tehát, ha nem biztos a tömb méretében a fordítás idején, akkor elég nagy tömböt kell meghatároznia ahhoz, hogy a biztonságos oldalon lehessen. De legtöbbször valójában kevesebb elemet fogunk használni, mint amennyit kiosztottunk. Tehát a memória jelentős része elpazarolható. Másrészt, ha az „elég nagy tömb” valójában nem elég nagy, akkor a program összeomlik.
Egy összekapcsolt lista külön memóriát oszt elemeihez a saját memóriablokkjában, és a teljes struktúrát úgy kapjuk meg, hogy ezeket az elemeket összekapcsoljuk egy láncban. Az összekapcsolt lista minden elemének két mezője van, amint azt a 3. ábra mutatja. Az adatmező tartalmazza a tényleges tárolt adatokat, a következő mező pedig a lánc következő elemére való hivatkozást tartalmazza. A csatolt lista első elemét a csatolt lista fejeként tárolja.
3. ábra: Összekapcsolt lista eleme
A 4. ábra három elemű összekapcsolt listát ábrázol. Minden elem tárolja az adatait, az utolsó kivételével minden elem hivatkozást tárol a következő elemre. Az utolsó elem null értéket tartalmaz a következő mezőjében. A lista bármely eleméhez úgy lehet hozzáférni, hogy az elejétől kezdve a következő mutatót követi, amíg meg nem felel a szükséges elemnek.
Annak ellenére, hogy a tömbök és a kapcsolt listák hasonlóak abban az értelemben, hogy mindkettőt az elemek gyűjteményének tárolására használják, eltérések merülnek fel a stratégiák miatt, amelyeket a memória elemeihez rendelnek. A tömbök minden elemhez egyetlen blokkként osztják a memóriát, és a tömb méretét futás közben kell meghatározni. Ez a tömböket hatástalanná tenné olyan helyzetekben, amikor nem ismeri a tömb méretét fordításkor. Mivel egy összekapcsolt lista külön osztja ki a memóriát az elemei számára, sokkal hatékonyabb lenne olyan helyzetekben, amikor a fordítás idején nem ismeri a lista méretét. A deklarálás és az összekapcsolt lista elemeihez való hozzáférés nem lenne egyenesen előrébb ahhoz képest, ahogyan egy tömb elemeihez közvetlenül hozzáférhet az indexei segítségével.
