Niz i Povezani popis su dva načina organiziranja podataka u memoriji. Prije razumijevanja razlika između Niz i Povezani popis , prvo gledamo u nizu i povezani popis .
skener u Javi
Što je niz?
Struktura podataka koja sadrži elemente istog tipa. Struktura podataka je način organiziranja podataka; niz je struktura podataka jer sekvencijalno organizira podatke. Niz je veliki dio memorije u kojem je memorija podijeljena na male-male blokove, a svaki blok može pohraniti neku vrijednost.
Pretpostavimo da smo kreirali polje koje se sastoji od 10 vrijednosti, tada će svaki blok pohraniti vrijednost cjelobrojnog tipa. Ako pokušamo pohraniti vrijednost u polje različitih tipova, tada to nije ispravno polje i izbacit će pogrešku tijekom kompilacije.
Deklaracija niza
Niz se može deklarirati kao:
data_type name of the array[no of elements]
Da bismo deklarirali polje, prvo moramo odrediti tip polja, a zatim ime polja. Unutar uglatih zagrada trebamo navesti broj elemenata koje naš niz treba sadržavati.
Shvatimo kroz primjer.
int a[5];
U gornjem slučaju, deklarirali smo niz od 5 elemenata s ' a 'ime an cijeli broj tip podataka.
Što je povezani popis?
Povezani popis je zbirka čvorova koji su nasumično pohranjeni. Svaki čvor se sastoji od dva polja, tj. podaci i veza . Ovdje su podaci vrijednost pohranjena na tom određenom čvoru, a veza je pokazivač koji sadrži adresu sljedećeg čvora.
css poravnanje teksta
Razlike između polja i povezanog popisa
Ne možemo reći koja je struktura podataka bolja, tj. polje ili povezani popis . Može postojati mogućnost da je jedna struktura podataka bolja za jednu vrstu zahtjeva, dok je druga struktura podataka bolja za drugu vrstu zahtjeva. Postoje različiti čimbenici kao što su operacije koje se često izvode na podatkovnoj strukturi ili veličina podataka te drugi čimbenici na temelju kojih je odabrana podatkovna struktura. Sada ćemo vidjeti neke razlike između niza i povezane liste na temelju nekih parametara.
1. Trošak pristupa elementu
U slučaju niza, bez obzira na veličinu niza, nizu je potrebno konstantno vrijeme za pristup elementu. U nizu su elementi pohranjeni na kontinuirani način, pa ako znamo osnovnu adresu elementa, tada možemo lako dobiti adresu bilo kojeg elementa u nizu. Moramo izvesti jednostavan izračun kako bismo dobili adresu bilo kojeg elementa u nizu. Dakle, pristup elementu u nizu je O(1) u smislu vremenske složenosti.
Na povezanom popisu elementi nisu pohranjeni na kontinuirani način. Sastoji se od više blokova, a svaki blok je predstavljen kao čvor. Svaki čvor ima dva polja, jedno je za podatkovno polje, a drugo pohranjuje adresu sljedećeg čvora. Da bismo pronašli bilo koji čvor na povezanom popisu, prvo moramo odrediti prvi čvor poznat kao glavni čvor. Ako moramo pronaći drugi čvor na popisu, tada moramo prijeći od prvog čvora, au najgorem slučaju, da bismo pronašli zadnji čvor, proći ćemo sve čvorove. Prosječni slučaj za pristup elementu je O(n).
Zaključujemo da je trošak pristupa elementu u nizu manji od troška pristupa povezanom popisu. Stoga, ako imamo bilo kakav zahtjev za pristup elementima, onda je niz bolji izbor.
2. Trošak umetanja elementa
U umetanju mogu postojati tri scenarija:
U slučaju povezanog popisa, za umetanje elementa na početku povezanog popisa, stvorit ćemo novi čvor, a adresa prvog čvora dodaje se novom čvoru. Na taj način novi čvor postaje prvi čvor. Dakle, vremenska složenost nije proporcionalna veličini popisa. Vremenska složenost bila bi konstantna, tj. O(1).
Ako niz nije pun, tada možemo izravno dodati novi element kroz indeks. U tom bi slučaju vremenska složenost bila konstantna, tj. O(1). Ako je niz pun, prvo ga trebamo kopirati u drugi niz i dodati novi element. U ovom slučaju, vremenska složenost bila bi O(n).
Da bismo umetnuli element na kraj povezane liste, moramo prijeći cijelu listu. Ako se povezana lista sastoji od n elemenata, tada bi vremenska složenost bila O(n).
Pretpostavimo da želimo umetnuti element na ithpoložaj niza; trebamo pomaknuti n/2 elemenata udesno. Stoga je vremenska složenost proporcionalna broju elemenata. Vremenska složenost bila bi O(n) za prosječan slučaj.
proljetna čizma
U slučaju povezane liste, moramo prijeći do te pozicije gdje moramo umetnuti novi element. Iako, ne moramo izvršiti nikakvu vrstu prebacivanja, ali moramo prijeći u n/2 poziciju. Uzeto vrijeme proporcionalno je n broju elemenata, a vremenska složenost za prosječan slučaj bila bi O(n).
Rezultirajući povezani popis je:
Implementacija niza je jednostavna u usporedbi s povezanim popisom. Dok stvarate program pomoću povezanog popisa, program je skloniji pogreškama kao što su pogreška segmentacije ili curenje memorije. Dakle, potrebno je posvetiti puno pažnje prilikom izrade programa na povezanom popisu.
Povezani popis je dinamičke veličine, dok je niz statičan. Ovdje statičnost ne znači da ne možemo odlučiti o veličini u vrijeme izvođenja, ali je ne možemo promijeniti kada se veličina odluči.
3. Memorijski zahtjevi
Budući da se elementi u nizu pohranjuju u jedan kontinuirani blok memorije, niz je fiksne veličine. Pretpostavimo da imamo niz veličine 7, a niz se sastoji od 4 elementa, tada je ostatak prostora neiskorišten. Memorija koju zauzima 7 elemenata:
Memorijski prostor = 7*4 = 28 bajtova
Gdje je 7 broj elemenata u nizu, a 4 broj bajtova cjelobrojnog tipa.
U slučaju povezanog popisa, nema neiskorištene memorije, ali dodatnu memoriju zauzimaju varijable pokazivača. Ako su podaci cjelobrojnog tipa, tada je ukupna memorija koju zauzima jedan čvor 8 bajtova, tj. 4 bajta za podatke i 4 bajta za varijablu pokazivača. Ako se povezana lista sastoji od 4 elementa, tada bi memorijski prostor koji zauzima povezana lista bio:
webdriver
Memorijski prostor = 8*4 = 32 bajta
Povezani popis bio bi bolji izbor ako je podatkovni dio veće veličine. Pretpostavimo da podaci imaju 16 bajtova. Memorijski prostor koji bi zauzimao niz bio bi 16*7=112 bajtova dok bi povezana lista zauzimala 20*4=80, ovdje smo naveli 20 bajtova kao 16 bajtova za veličinu podataka plus 4 bajta za varijablu pokazivača. Ako biramo veću veličinu podataka, onda bi povezani popis trošio manje memorije; inače, to ovisi o čimbenicima koje usvajamo za određivanje veličine.
Pogledajmo razlike između niza i povezanog popisa u tabličnom obliku.
| Niz | Povezani popis |
|---|---|
| Niz je skup elemenata sličnog tipa podataka. | Povezani popis je skup objekata poznatih kao čvor gdje se čvor sastoji od dva dijela, tj. podataka i adrese. |
| Elementi niza pohranjuju se na neprekidnoj memorijskoj lokaciji. | Elementi povezanog popisa mogu se pohraniti bilo gdje u memoriji ili nasumično pohranjeni. |
| Array radi sa statičkom memorijom. Ovdje statička memorija znači da je veličina memorije fiksna i ne može se mijenjati tijekom rada. | Povezani popis radi s dinamičkom memorijom. Ovdje dinamička memorija znači da se veličina memorije može mijenjati u vrijeme izvođenja prema našim zahtjevima. |
| Elementi niza neovisni su jedan o drugome. | Elementi povezanog popisa ovise jedan o drugome. Budući da svaki čvor sadrži adresu sljedećeg čvora, da bismo pristupili sljedećem čvoru, moramo pristupiti njegovom prethodnom čvoru. |
| Nizu je potrebno više vremena za izvođenje bilo koje operacije poput umetanja, brisanja itd. | Povezanom popisu potrebno je manje vremena za izvođenje bilo koje operacije poput umetanja, brisanja itd. |
| Pristup bilo kojem elementu u nizu brži je jer se elementu u nizu može izravno pristupiti putem indeksa. | Pristup elementu na povezanom popisu je sporiji jer počinje obilaziti od prvog elementa povezanog popisa. |
| U slučaju niza, memorija se dodjeljuje tijekom kompajliranja. | U slučaju povezanog popisa, memorija se dodjeljuje tijekom izvođenja. |
| Korištenje memorije u nizu je neučinkovito. Na primjer, ako je veličina niza 6, a niz se sastoji samo od 3 elementa tada će ostatak prostora biti neiskorišten. | Korištenje memorije učinkovito je u slučaju povezanog popisa budući da se memorija može dodijeliti ili osloboditi u vrijeme izvođenja prema našim zahtjevima. |