Array in Povezan seznam sta dva načina organiziranja podatkov v pomnilniku. Preden razumete razlike med Array in Povezan seznam , najprej pogledamo pri nizu in povezan seznam .
bash dolžina niza
Kaj je niz?
Podatkovna struktura, ki vsebuje elemente iste vrste. Podatkovna struktura je način organiziranja podatkov; matrika je podatkovna struktura, ker zaporedno organizira podatke. Niz je velik kos pomnilnika, v katerem je pomnilnik razdeljen na majhne-majhne bloke in vsak blok lahko shrani neko vrednost.
Recimo, da smo ustvarili matriko, ki je sestavljena iz 10 vrednosti, potem bo vsak blok shranil vrednost celega tipa. Če poskušamo vrednost shraniti v matriko različnih vrst, potem to ni pravilna matrika in bo povzročila napako med prevajanjem.
Deklaracija matrike
Matriko lahko deklariramo kot:
data_type name of the array[no of elements]
Za deklaracijo matrike moramo najprej določiti vrsto matrike in nato ime matrike. Znotraj oglatih oklepajev moramo določiti število elementov, ki naj jih vsebuje naša matrika.
Razumejmo skozi primer.
int a[5];
V zgornjem primeru smo razglasili niz 5 elementov z ' a ' ime an celo število tip podatkov.
Kaj je povezan seznam?
Povezani seznam je zbirka vozlišč, ki so naključno shranjena. Vsako vozlišče je sestavljeno iz dveh polj, tj. podatke in povezava . Tukaj so podatki vrednost, shranjena v tem vozlišču, povezava pa je kazalec, ki vsebuje naslov naslednjega vozlišča.
Razlike med nizom in povezanim seznamom
Ne moremo reči, katera podatkovna struktura je boljša, npr povezan seznam . Obstaja možnost, da je ena podatkovna struktura boljša za eno vrsto zahtev, medtem ko je druga podatkovna struktura boljša za drugo vrsto zahtev. Obstajajo različni dejavniki, kot so pogoste operacije, ki se izvajajo na podatkovni strukturi ali velikost podatkov, in drugi dejavniki, na podlagi katerih je izbrana podatkovna struktura. Zdaj bomo videli nekaj razlik med matriko in povezanim seznamom na podlagi nekaterih parametrov.
prvi prenosnik
1. Stroški dostopa do elementa
V primeru matrike, ne glede na velikost matrike, matrika potrebuje konstanten čas za dostop do elementa. V matriki so elementi shranjeni na sosednji način, tako da če poznamo osnovni naslov elementa, lahko zlahka dobimo naslov katerega koli elementa v matriki. Izvesti moramo preprost izračun, da dobimo naslov katerega koli elementa v matriki. Torej je dostop do elementa v matriki O(1) glede na časovno zahtevnost.
Na povezanem seznamu elementi niso shranjeni na neprekinjen način. Sestavljen je iz več blokov, vsak blok pa je predstavljen kot vozlišče. Vsako vozlišče ima dve polji, eno je za podatkovno polje, drugo pa shranjuje naslov naslednjega vozlišča. Če želite najti katero koli vozlišče na povezanem seznamu, moramo najprej določiti prvo vozlišče, znano kot glavno vozlišče. Če moramo najti drugo vozlišče na seznamu, potem moramo prečkati od prvega vozlišča, v najslabšem primeru, da bi našli zadnje vozlišče, pa bomo prečkali vsa vozlišča. Povprečni primer za dostop do elementa je O(n).
Sklepamo, da je strošek dostopa do elementa v matriki nižji kot do povezanega seznama. Torej, če imamo kakršno koli zahtevo za dostop do elementov, potem je array boljša izbira.
2. Strošek vstavitve elementa
Pri vstavljanju so lahko trije scenariji:
V primeru povezanega seznama bomo za vstavljanje elementa na začetek povezanega seznama ustvarili novo vozlišče in naslov prvega vozlišča bo dodan novemu vozlišču. Na ta način novo vozlišče postane prvo vozlišče. Torej časovna zahtevnost ni sorazmerna z velikostjo seznama. Časovna kompleksnost bi bila konstantna, tj. O(1).
Če matrika ni polna, lahko dodamo nov element neposredno prek indeksa. V tem primeru bi bila časovna kompleksnost konstantna, tj. O(1). Če je matrika polna, jo moramo najprej prekopirati v drugo matriko in dodati nov element. V tem primeru bi bila časovna kompleksnost O(n).
Da vstavimo element na konec povezanega seznama, moramo prehoditi celoten seznam. Če je povezan seznam sestavljen iz n elementov, bi bila časovna kompleksnost O(n).
Recimo, da želimo vstaviti element na ithpoložaj niza; premakniti moramo n/2 elementa v desno. Zato je časovna zahtevnost sorazmerna s številom elementov. Časovna kompleksnost bi bila O(n) za povprečen primer.
amisha patel
V primeru povezanega seznama se moramo pomakniti do tistega položaja, kjer moramo vstaviti nov element. Kljub temu nam ni treba izvesti nikakršnega prestavljanja, ampak moramo prestaviti v položaj n/2. Porabljeni čas je sorazmeren z n številom elementov, časovna kompleksnost za povprečen primer pa bi bila O(n).
Nastali povezani seznam je:
Implementacija matrike je enostavna v primerjavi s povezanim seznamom. Med ustvarjanjem programa s povezanim seznamom je program bolj nagnjen k napakam, kot je napaka segmentacije ali uhajanje pomnilnika. Zato je treba biti pri ustvarjanju programa na povezanem seznamu zelo previden.
Povezani seznam je dinamične velikosti, medtem ko je niz statičen. Tukaj statičnost ne pomeni, da ne moremo določiti velikosti med izvajanjem, vendar je ne moremo spremeniti, ko je velikost določena.
3. Zahteve po pomnilniku
Ker so elementi v matriki shranjeni v enem sosednjem bloku pomnilnika, je matrika fiksne velikosti. Recimo, da imamo matriko velikosti 7 in je matrika sestavljena iz 4 elementov, potem je preostali prostor neuporabljen. Pomnilnik, ki ga zaseda 7 elementov:
Pomnilniški prostor = 7*4 = 28 bajtov
Kjer je 7 število elementov v matriki, 4 pa število bajtov celega tipa.
V primeru povezanega seznama ni neuporabljenega pomnilnika, vendar dodatni pomnilnik zasedejo spremenljivke kazalca. Če so podatki celoštevilskega tipa, je skupni pomnilnik, ki ga zasede eno vozlišče, 8 bajtov, tj. 4 bajti za podatke in 4 bajti za spremenljivko kazalca. Če je povezan seznam sestavljen iz 4 elementov, bi bil pomnilniški prostor, ki bi ga zasedel povezan seznam:
spletni gonilnik
Pomnilniški prostor = 8*4 = 32 bajtov
Povezan seznam bi bil boljša izbira, če je podatkovni del večji. Recimo, da so podatki 16 bajtov. Pomnilniški prostor, ki bi ga zasedel niz, bi bil 16*7=112 bajtov, medtem ko bi povezani seznam zasedel 20*4=80, tukaj smo določili 20 bajtov kot 16 bajtov za velikost podatkov in 4 bajte za spremenljivko kazalca. Če izberemo večjo velikost podatkov, potem bi povezan seznam porabil manj pomnilnika; sicer pa je odvisno od dejavnikov, ki jih sprejmemo za določitev velikosti.
Oglejmo si razlike med matriko in povezanim seznamom v obliki tabele.
| Array | Povezan seznam |
|---|---|
| Matrika je zbirka elementov podobne vrste podatkov. | Povezani seznam je zbirka predmetov, znanih kot vozlišče, kjer je vozlišče sestavljeno iz dveh delov, tj. podatkov in naslova. |
| Elementi niza so shranjeni na sosednji pomnilniški lokaciji. | Elemente povezanega seznama lahko shranite kamor koli v pomnilnik ali jih naključno shranite. |
| Array deluje s statičnim pomnilnikom. Tukaj statični pomnilnik pomeni, da je velikost pomnilnika fiksna in je ni mogoče spremeniti med izvajanjem. | Povezani seznam deluje z dinamičnim pomnilnikom. Tukaj dinamični pomnilnik pomeni, da je velikost pomnilnika mogoče spremeniti med izvajanjem v skladu z našimi zahtevami. |
| Elementi niza so neodvisni drug od drugega. | Elementi povezanega seznama so odvisni drug od drugega. Ker vsako vozlišče vsebuje naslov naslednjega vozlišča, moramo za dostop do naslednjega vozlišča dostopati do prejšnjega vozlišča. |
| Matrika vzame več časa med izvajanjem katere koli operacije, kot je vstavljanje, brisanje itd. | Povezani seznam traja manj časa pri izvajanju katere koli operacije, kot je vstavljanje, brisanje itd. |
| Dostop do katerega koli elementa v matriki je hitrejši, saj je do elementa v matriki mogoče neposredno dostopati prek indeksa. | Dostop do elementa na povezanem seznamu je počasnejši, saj se začne premikati od prvega elementa povezanega seznama. |
| V primeru matrike se pomnilnik dodeli v času prevajanja. | V primeru povezanega seznama se pomnilnik dodeli med izvajanjem. |
| Uporaba pomnilnika je v polju neučinkovita. Na primer, če je velikost matrike 6 in je matrika sestavljena samo iz 3 elementov, bo preostali prostor neuporabljen. | Uporaba pomnilnika je učinkovita v primeru povezanega seznama, saj je pomnilnik mogoče dodeliti ali sprostiti med izvajanjem v skladu z našimi zahtevami. |