Különbség a tömbök és a kapcsolt listák között

Tömbök és kapcsolt listák

Az elemek gyűjtésének tárolására a tömbök a leggyakrabban használt adatszerkezetek. A legtöbb programozási nyelv módszereket biztosít a tömbök és a tömbökhez való hozzáférési elemek könnyű deklarálására. A kapcsolt lista, pontosabban külön-külön összekapcsolt lista, szintén egy adatszerkezet, amely felhasználható az elemek gyűjteményének tárolására. Ez egy csomópont-sorozatból áll, és minden csomópont hivatkozik a sorozat következő csomópontjára.

Az 1. ábrán látható kódrészlet, amelyet általában egy tömb értékének deklarálására és hozzárendelésére használnak. A 2. ábra azt mutatja be, hogy egy tömb hogyan nézne ki a memóriában.

A fenti kód egy olyan tömböt határoz meg, amely 5 egész számot tárolhat, és a 0–4 indexekkel érhető el. A tömb egyik fontos tulajdonsága, hogy a teljes tömböt egyetlen memória blokkként osztják el, és minden elem saját helyet kap a tömbben. Miután egy tömb meghatározásra került, rögzítik annak méretét. Tehát ha nem biztos a tömb méretében a fordításkor, akkor elég nagy tömböt kell definiálnia ahhoz, hogy biztonságban legyen. De általában a ténylegesen kevesebb elemet fogunk használni, mint amennyit kiosztunk. Tehát jelentős mennyiségű memória pazarlik el. Másrészt, ha a „elég nagy tömb” valójában nem elég nagy, akkor a program összeomlik.

Egy összekapcsolt lista a memóriát külön-külön osztja el az elemekhez a saját memória blokkjában, és a teljes struktúrát úgy kapjuk, hogy ezeket az elemeket láncként összekötik. A csatolt listában minden elemnek két mezője van, ahogy a 3. ábrán látható. Az adatmező a ténylegesen tárolt adatokat tartalmazza, a következő mező pedig a lánc következő elemére utal. A csatolt lista első elemét a csatolt lista fejében tárolja.

3. ábra: A kapcsolt lista eleme

A 4. ábra egy összekapcsolt listát ábrázol három elemmel. Minden elem tárolja az adatait, és az összes elem, kivéve az utóbbi, a következő elemre való hivatkozást. Az utolsó elem null értékű a következő mezőben. A lista bármely eleméhez hozzáférhet a fejjel indítással és a következõ mutató követésével, amíg el nem éri a kívánt elemet.

Annak ellenére, hogy a tömbök és a csatolt 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 az azoknak a stratégiáknak köszönhetően, amelyeket az elemek memóriájának elosztására használnak. A tömbök a memóriát minden elemére egyetlen blokkként osztják el, és a tömb méretét futási időben kell meghatározni. Ez a tömbök hatékonyságát csökkentené olyan helyzetekben, amikor nem ismeri a tömb méretét fordításkor. Mivel a csatolt lista külön osztja el a memóriát az elemeinek, sokkal hatékonyabb lenne olyan helyzetekben, amikor nem ismeri a lista méretét a fordítás idején. A csatolt listában szereplő nyilatkozatok és elemek elérése nem lenne egyenes előrehaladás ahhoz képest, hogy hogyan töltse el közvetlenül a tömb elemeit annak indexei segítségével.