Razlika između popisa niza i povezanih popisa

Kako se pohranjuju podaci?

Popis niza i povezani popis uobičajeni su pojmovi kada je u pitanju pohrana i preuzimanje podataka. Iako postoji puno uređaja za pohranu, u konačnici ovise o mehanizmu za pohranu. Ova dva mehanizma za pohranu smještaju vaše podatke u uređaje za pohranu i dohvaćaju ih po potrebi. Pogledajmo kako pohranjuju podatke u svoju memoriju. Popis Array koristi uzastopnu pohranu, a dijelovi podataka pohranjuju se jedan za drugim. Ovo je možda jednostavniji oblik pohrane - izbjegava zabune. Da, možemo preuzeti sljedeću stavku ili podatke sa sljedeće memorijske lokacije na popisu polja; međutim, on se pohranjuje uz pomoć pokazivača na Poveznom popisu. Ovdje su nam potrebne dvije memorijske lokacije za pohranu - jedno za podatke, a drugo za pokazivač. Pokazivač adresira memorijsko mjesto sljedećih podataka. Lako možemo shvatiti da Povezani popis nikada ne pohranjuje podatke uzastopno; radije koristi mehanizam slučajnog pohranjivanja. Pokazivači su ključni elementi u pronalaženju mjesta podataka u memoriji.

Dinamički niz i povezani popis

Već smo raspravljali o tome kako oba mehanizma za pohranu unose podatke i možemo dati izraz "dinamički niz" za internu shemu za pohranu popisa Array. Jednostavno stavlja dijelove podataka jedan za drugim - otuda i naziv - dok Povezani popis koristi interni popis uz pomoć pokazivača za praćenje sljedeće stavke. Stoga koristi interni povezani popis, poput pojedinačno ili dvostruko povezanog popisa kako bi nam pokazao sljedeće podatke.

Upotreba memorije

Kako Array popis pohranjuje samo stvarne podatke, potreban nam je prostor samo za podatke koje pohranjujemo. Suprotno tome, na popisu Povezani koristimo i pokazivače. Stoga su potrebna dva mjesta memorije, a možemo reći da povezani popis troši više memorije nego popis Array. Povoljna strana Poveznog popisa je da on nikada ne zahtijeva kontinuirane memorijske lokacije za pohranu naših podataka, za razliku od popisa Array. Pokazivači mogu zadržati poziciju sljedeće lokacije podataka, a mi čak možemo koristiti i manje memorijske utore koji nisu kontinuirani. Kad je riječ o korištenju memorije, pokazivači igraju glavnu ulogu na Povezanom popisu, a tako i njihova učinkovitost.

Veličina popisa početnih nizova i povezane liste

Uz Array popis, čak i prazan popis zahtijeva veličinu 10, ali s povezanim popisom ne treba nam toliko ogroman prostor. Možemo stvoriti prazan popis povezanih veličina veličine 0. Kasnije možemo povećati veličinu prema potrebi.

Dohvaćanje podataka

Dohvaćanje podataka je na popisu Array jednostavnije jer se pohranjuje uzastopno. Sve što treba učiniti je identificirati prvu lokaciju podataka; odatle se sljedećem mjestu pristupa uzastopno kako bi se preuzelo ostalo. Izračunava se kao prvi položaj podataka + 'n', gdje je 'n' redoslijed podataka na popisu Array. Povezani popis odnosi se na početni pokazivač kako bi se pronašlo prvo mjesto podataka, a odatle se upućuje pokazivač povezan sa svakim podacima kako bi pronašao sljedeće mjesto podataka. Proces dohvaćanja uglavnom ovisi o ovdje prikazanim pokazateljima i oni nam učinkovito pokazuju sljedeću lokaciju podataka.

Kraj podataka

Popis Array koristi null vrijednost za označavanje kraja podataka, dok Linked list koristi null pointer za ovu svrhu. Čim sustav prepozna nulane podatke, popis Array zaustavlja sljedeće pretraživanje podataka. Na sličan način nulto pokazivač zaustavlja sustav da prijeđe na sljedeće pretraživanje podataka.

Obrnuti presjek

Popis povezanih stranica omogućava nam kretanje u obrnutim smjerovima uz pomoć descendingiteratora (). Međutim, mi na popisu niza nemamo takav objekt - obrnuti presjek ovdje postaje problem.

Sintaksa

Pogledajmo Java sintaksu oba mehanizma za pohranu.

Izrada popisa nizova:

Popis arraylistsample = novi ArrayList ();

Dodavanje objekata na popis nizova:

Arraylistsample.add ( „NAME1”);

Arraylistsample.add ( „NAME2”);

Ovako će izgledati rezultirajući popis Array - [ime1, ime2].

Izrada povezanih lista:

Popis linkedlistsample = novi linkedList ();

Dodavanje objekata na Povezani popis:

Linkedlistsample.add ( „NAME3”);

Linkedlistsample.add ( „NAME4”);

Ovako će izgledati rezultirajući Povezani popis - [ime3, ime4].

 Što je bolje za operaciju Dohvati ili Traži?

Popis Array treba O (1) vrijeme za pokretanje bilo kojeg pretraživanja podataka, dok Povezani popis uzima u O (n) za n^th pretraživanje podataka. Stoga popis Array uvijek koristi stalno vrijeme za bilo kakvu pretragu podataka, ali na Povezanom popisu vrijeme potrebno ovisi o položaju podataka. Stoga su Array popisi uvijek bolji izbor za Get ili Search operacije.

Što je bolje za umetanje ili dodavanje?

I popis Array i Povezani popis uzimaju O (1) vrijeme za dodavanje podataka. Ali ako je niz pun, tada popisu polja treba mnogo vremena da ga promijenite i promijenite veličinu te kopirate stavke u noviju. U takvom je slučaju Povezani popis bolji izbor.

Što je bolje za operaciju uklanjanja?

Operacija uklanjanja traje gotovo jednaku količinu vremena i na popisu Array i na Poveznom popisu. Na popisu Array, ova operacija briše podatke, a zatim pomiče položaj podataka da formira noviji niz - potrebno je O (n) vrijeme. Na Poveznom popisu ova operacija prelazi na određene podatke i mijenja položaje pokazivača kako bi oblikovala noviji popis. Vrijeme prolaska i uklanjanja je i ovdje O (n).

Što je brže?

Znamo da popis Array koristi interni niz za pohranu stvarnih podataka. Stoga, ako se bilo koji podatak izbriše, tada svi sljedeći podaci trebaju promjenu memorije. Očito, za to je potrebno dosta vremena i stvari usporavaju. Ovakav pomak memorije nije potreban na Poveznom popisu, jer sve što radi je promjena mjesta pokazivača. Stoga je Povezani popis brži od popisa Array u bilo kojoj vrsti podataka. Međutim, to čisto ovisi o vrsti operacije, tj. Za operaciju Dobivanje ili pretraživanje, Povezani popis zahtijeva puno više vremena nego popis Array. Kad pogledamo cjelokupnu izvedbu, možemo reći da je Povezani popis brži.

Kada koristiti popis array i povezani popis?

Popis Array najprikladniji je za manje zahtjeve za podacima gdje je dostupna kontinuirana memorija. Ali kad se bavimo ogromnim količinama podataka, dostupnost kontinuirane memorije implementira mehanizme za pohranu podataka, bilo da je mala ili ogromna. Zatim odlučite koga odabrati - popis Array ili Povezani popis. Možete nastaviti s popisom nizova kad samo trebate pohranu i dohvaćanje podataka. Ali popis vam može pomoći osim manipuliranja podacima. Jednom kada odlučite koliko često je potrebna obrada podataka, važno je provjeriti kakvu vrstu podataka najčešće obavljate. Kad je samo Dohvati ili Traži, onda je Popis matrica bolji izbor; za ostale operacije poput umetanja ili brisanja, idite naprijed s popisom povezanih.

Pogledajmo razlike u tabelarnom obliku.

S.No	koncepti	Razlike
		Popis nizova	Povezani popis
1	Moda za pohranu podataka	Koristi uzastopno pohranjivanje podataka	Koristi nekonvencionalno pohranjivanje podataka
2	Shema unutarnjeg skladištenja	Održava interni dinamički niz	Održava povezani popis
3	Upotreba memorije	Zahtijeva memorijski prostor samo za podatke	Zahtijeva memorijski prostor i za podatke i za pokazivače
4	Veličina početnog popisa	Potrebno je prostora za najmanje 10 predmeta	Ne treba prostora i čak možemo stvoriti prazan popis povezanih veličina 0.
5	Dohvaćanje podataka	Izračunava poput prvog položaja podataka + 'n', gdje je 'n' redoslijed podataka na popisu Array	Obilazak od prvog ili posljednjeg do traženih podataka
6	Kraj podataka	Null vrijednosti označavaju kraj	Null Pointer označava kraj
7	Obrnuti presjek	Ne dopušta	Omogućuje to uz pomoć descendingiteratora ()
8	Sintaksa stvaranja popisa	Popis arraylistsample = novi ArrayList ();	Popis linkedlistsample = novi linkedList ();
9	Dodavanje objekata	Arraylistsample.add ( „NAME1”);	Linkedlistsample.add ( „NAME3”);
10	Dohvati ili Potraži	Uzima O (1) vrijeme i bolji je u izvedbi	Traje O (n) vrijeme i učinkovitost ovisi o položaju podataka
11	Umetanje ili dodavanje	Potroši O (1) vrijeme, osim kada je niz pun	Konzumira O (1) vrijeme u svim okolnostima
12	Brisanje ili uklanjanje	Zauzima vrijeme O (n)	Zauzima vrijeme O (n)
13	Kada koristiti?	Kada je uključeno puno operacija Dohvaćanje ili Pretraživanje; dostupnost memorije bi trebala biti veća čak i na početku	Kad postoji puno operacija za umetanje ili brisanje, a raspoloživost memorije ne mora biti kontinuirana