Sor és Linkelt lista kétféle módon rendezheti az adatokat a memóriában. Mielőtt megértené a különbségeket a Sor és a Linkelt lista , először nézzük meg egy tömbnél és egy linkelt lista .
dfs algoritmus
Mi az a tömb?
Azonos típusú elemeket tartalmazó adatstruktúra. Az adatstruktúra az adatok rendszerezésének egyik módja; a tömb egy adatstruktúra, mert szekvenciálisan rendszerezi az adatokat. A tömb egy nagy memóriadarab, amelyben a memória kis-kis blokkokra van felosztva, és mindegyik blokk képes valamilyen értéket tárolni.
Tegyük fel, hogy létrehoztunk egy 10 értékből álló tömböt, akkor minden blokk egy egész típusú értéket tárol. Ha megpróbáljuk az értéket különböző típusú tömbben tárolni, akkor az nem megfelelő tömb, és fordítási idejű hibát fog kiütni.
A tömb nyilatkozata
Egy tömb a következőképpen deklarálható:
data_type name of the array[no of elements]
Egy tömb deklarálásához először meg kell adnunk a tömb típusát, majd a tömb nevét. A szögletes zárójelben meg kell adnunk, hogy a tömbünk hány elemet tartalmazzon.
Értsük meg egy példán keresztül.
int a[5];
A fenti esetben egy 5 elemből álló tömböt deklaráltunk a ' egy neve egész szám adattípus.
Mi az a linkelt lista?
A linkelt lista a véletlenszerűen tárolt csomópontok gyűjteménye. Minden csomópont két mezőből áll, azaz adat és link . Itt az adat az adott csomóponton tárolt érték, a hivatkozás pedig a mutató, amely a következő csomópont címét tartalmazza.
A tömb és a linkelt lista közötti különbségek
Nem tudjuk megmondani, hogy melyik adatstruktúra a jobb, azaz a tömb ill linkelt lista . Előfordulhat, hogy az egyik adatstruktúra jobb egyfajta követelményhez, míg a másik adatstruktúra egy másik típusú követelményhez. Különböző tényezők vannak, mint például, hogy milyen gyakori műveleteket hajtanak végre az adatstruktúrán, vagy az adatok mérete, és más tényezők is, amelyek alapján az adatszerkezetet kiválasztják. Most látni fogunk néhány különbséget a tömb és a hivatkozott lista között néhány paraméter alapján.
1. Egy elem elérésének költsége
Egy tömb esetén, függetlenül a tömb méretétől, egy tömbnek állandó időre van szüksége az elem eléréséhez. Egy tömbben az elemek összefüggő módon tárolódnak, így ha ismerjük az elem alapcímét, akkor könnyen megkaphatjuk a tömb bármely elemének címét. Egy egyszerű számítást kell végrehajtanunk, hogy megkapjuk a tömb bármely elemének címét. Tehát egy tömb elemének elérése az O(1) az idő bonyolultsága szempontjából.
mi az a myspace
A linkelt listában az elemek nem egymás mellett tárolódnak. Több blokkból áll, és mindegyik blokk csomópontként jelenik meg. Minden csomópontnak két mezője van, azaz az egyik az adatmezőhöz, a másik pedig a következő csomópont címét tárolja. Ha bármelyik csomópontot meg akarjuk találni a hivatkozott listában, először meg kell határoznunk az első csomópontot, amely főcsomópontként ismert. Ha meg kell találnunk a második csomópontot a listában, akkor az első csomóponttól kell bejárnunk, és a legrosszabb esetben az utolsó csomópont megtalálásához az összes csomópontot bejárjuk. Az elemhez való hozzáférés átlagos esete O(n).
Arra a következtetésre jutottunk, hogy a tömb egy eleméhez való hozzáférés költsége alacsonyabb, mint a hivatkozott listaé. Ezért, ha bármilyen követelményünk van az elemek eléréséhez, akkor a tömb jobb választás.
2. Egy elem beillesztésének költsége
A beillesztésben három forgatókönyv szerepelhet:
Hivatkozott lista esetén egy elem beszúrásához a linkelt lista elejére egy új csomópontot hozunk létre, és az első csomópont címét hozzáadjuk az új csomóponthoz. Ily módon az új csomópont lesz az első csomópont. Tehát az időbonyolultság nem arányos a lista méretével. Az időbonyolultság állandó lenne, azaz O(1).
Ha a tömb nem tele van, akkor az indexen keresztül közvetlenül hozzáadhatjuk az új elemet. Ebben az esetben az időbonyolultság állandó, azaz O(1). Ha a tömb megtelt, először át kell másolnunk a tömböt egy másik tömbbe, és hozzá kell adni egy új elemet. Ebben az esetben az időbonyolultság O(n) lenne.
Ahhoz, hogy egy elemet beszúrhassunk a hivatkozott lista végére, be kell járnunk a teljes listát. Ha a linkelt lista n elemből áll, akkor az időbonyolultság O(n) lenne.
Tegyük fel, hogy az elemet az i-be szeretnénk beszúrnitha tömb pozíciója; az n/2 elemet jobbra kell tolnunk. Ezért az időbonyolultság arányos az elemek számával. Az időbonyolultság O(n) lenne az átlagos esetre.
karaktert karakterláncra java-ban
Hivatkozott lista esetén arra a pozícióra kell áthaladnunk, ahol be kell illesztenünk az új elemet. Ennek ellenére semmiféle eltolást nem kell végrehajtanunk, hanem n/2-es pozícióba kell haladnunk. A szükséges idő arányos n elemszámmal, és az időbonyolultság átlagos esetre O(n) lenne.
Az eredményül kapott linkelt lista a következő:
Egy tömb megvalósítása egyszerű a hivatkozott listához képest. Amikor egy csatolt listát használó programot hoz létre, a program hajlamosabb az olyan hibákra, mint a szegmentálási hiba vagy a memóriaszivárgás. Tehát nagyon körültekintően kell eljárni, amikor egy programot hoz létre a hivatkozott listában.
A hivatkozott lista dinamikus méretű, míg a tömb statikus. Itt a statikus nem azt jelenti, hogy nem tudjuk eldönteni a méretet futási időben, de nem tudjuk megváltoztatni, ha a méret eldöntött.
3. Memóriakövetelmények
Ahogy a tömb elemei egy összefüggő memóriablokkban tárolódnak, a tömb fix méretű. Tegyük fel, hogy van egy 7-es méretű tömbünk, és a tömb 4 elemből áll, akkor a hely többi része kihasználatlan. A 7 elem által elfoglalt memória:
Memóriaterület = 7*4 = 28 bájt
Ahol 7 egy tömb elemeinek száma, 4 pedig egy egész típusú bájtok száma.
Hivatkozott lista esetén nincs kihasználatlan memória, de a plusz memóriát a mutatóváltozók foglalják el. Ha az adatok egész típusúak, akkor az egy csomópont által elfoglalt teljes memória 8 bájt, azaz 4 bájt az adatoknál és 4 bájt a mutatóváltozónál. Ha a linkelt lista 4 elemből áll, akkor a csatolt lista által elfoglalt memóriaterület a következő lesz:
webdriver
Memóriaterület = 8*4 = 32 bájt
A linkelt lista jobb választás lenne, ha az adatrész nagyobb méretű. Tegyük fel, hogy az adatok 16 bájtból állnak. A tömb által elfoglalt memóriaterület 16*7=112 bájt lenne, míg a linkelt lista 20*4=80-at, itt 20 bájtot adtunk meg 16 bájtként az adatok méretéhez, plusz 4 bájtot a mutatóváltozóhoz. Ha nagyobb adatméretet választunk, akkor a linkelt lista kevesebb memóriát fogyasztana; egyébként a méret meghatározásakor figyelembe vett tényezőktől függ.
Nézzük meg táblázatos formában a tömb és a hivatkozott lista közötti különbségeket.
| Sor | Linkelt lista |
|---|---|
| A tömb hasonló adattípusú elemek gyűjteménye. | A linkelt lista csomópontként ismert objektumok gyűjteménye, ahol a csomópont két részből áll, azaz adatokból és címekből. |
| A tömbelemek egy összefüggő memóriahelyen tárolódnak. | A csatolt listaelemek bárhol eltárolhatók a memóriában, vagy véletlenszerűen tárolhatók. |
| A tömb statikus memóriával működik. Itt a statikus memória azt jelenti, hogy a memória mérete rögzített, és futási időben nem módosítható. | A csatolt lista dinamikus memóriával működik. Itt a dinamikus memória azt jelenti, hogy a memória mérete futási időben változtatható az igényeinknek megfelelően. |
| A tömb elemei függetlenek egymástól. | A linkelt listaelemek egymástól függenek. Mivel minden csomópont tartalmazza a következő csomópont címét, így a következő csomópont eléréséhez el kell érnünk az előző csomópontot. |
| A tömb több időt vesz igénybe bármilyen művelet végrehajtása során, például beszúrás, törlés stb. | A linkelt lista kevesebb időt vesz igénybe bármilyen művelet, például beillesztés, törlés stb. végrehajtása során. |
| A tömb bármely elemének elérése gyorsabb, mivel a tömb elemei közvetlenül elérhetők az indexen keresztül. | A hivatkozott lista elemeinek elérése lassabb, mivel az a csatolt lista első elemétől kezdi meg a bejárást. |
| Tömb esetén a memória lefoglalása fordítási időben történik. | Hivatkozott lista esetén a memória lefoglalása futási időben történik. |
| A memória kihasználása nem hatékony a tömbben. Például, ha a tömb mérete 6, és a tömb csak 3 elemből áll, akkor a többi hely kihasználatlan lesz. | A memóriakihasználás hatékony egy linkelt lista esetén, mivel a memória igényünk szerint futási időben allokálható vagy felszabadítható. |