Razlika med seznamom matic in povezanim seznamom

Kako se shranjujejo podatki?

Seznam matrikov in povezan seznam sta pogosta izraza, ko gre za shranjevanje in iskanje podatkov. Čeprav je shranjevalnih naprav veliko, so na koncu odvisne od mehanizma za shranjevanje. Ta dva mehanizma za shranjevanje položita vaše podatke v naprave za shranjevanje in jih po potrebi pridobite. Oglejmo si, kako shranjujejo podatke v svoj spomin. Seznam Array uporablja zaporedno shranjevanje, kosi podatkov pa se shranijo drug za drugim. To je morda preprostejša oblika shranjevanja - izogne ​​se zmedi. Da, naslednji element ali podatki lahko dobimo z naslednjega pomnilniškega seznama nizov; vendar je shranjena s pomočjo kazalcev na seznamu Povezani. Tu potrebujemo dve pomnilniški lokaciji za shranjevanje - eno za podatke, drugo za kazalec. Kazalec naslovi spominsko lokacijo naslednjih podatkov. Zlahka razumemo, da Povezani seznam nikoli ne shranjuje podatkov zaporedno; raje uporablja naključni mehanizem za shranjevanje. Kazalniki so ključni elementi iskanja lokacij podatkov v pomnilniku.

Dinamični niz in povezani seznam

Že smo razpravljali o tem, kako oba mehanizma za shranjevanje vneseta podatke in lahko damo izraz „dinamična matrika“ za notranjo shemo shranjevanja seznama Array. Podatke poda le eden za drugim - od tod tudi ime - medtem ko seznam Povezanih seznam uporablja notranji seznam s pomočjo kazalcev za sledenje naslednji postavki. Zato za prikaz naslednjih podatkov uporablja notranji povezan seznam, kot je enojni ali dvopovezani seznam.

Uporaba pomnilnika

Ker seznam Array hrani samo dejanske podatke, potrebujemo prostor samo za podatke, ki jih hranimo. Nasprotno pa na seznamu Povezani uporabljamo tudi kazalce. Zato sta potrebni dve lokaciji pomnilnika in lahko rečemo, da povezan seznam porabi več pomnilnika kot seznam Array. Prednost strani povezanega seznama je, da za shranjevanje podatkov nikoli ne potrebuje neprekinjenih pomnilniških lokacij, v nasprotju s seznamom Array. Kazalci lahko zadržijo položaj naslednje podatkovne lokacije, uporabimo pa lahko tudi manjše pomnilniške reže, ki niso neprekinjene. Kar zadeva porabo pomnilnika, kazalci igrajo glavno vlogo na seznamu Povezani in s tem tudi učinkovitost le-teh.

Velikost začetnega seznama matrike in povezanega seznama

Pri seznamu Array je celo prazen seznam potreben velikosti 10, toda s povezanim seznamom ne potrebujemo tako velikega prostora. Ustvarimo lahko prazen seznam z velikostjo 0. Kasneje lahko po potrebi povečamo velikost.

Pridobivanje podatkov

Nalaganje podatkov je na seznamu Array enostavnejše, saj se shranjuje zaporedno. Vse, kar počne, je določiti prvo lokacijo podatkov; od tam do naslednje lokacije dostopate zaporedno, da pridobite preostale. Izračuna kot prvo pozicijo podatkov + 'n', kjer je 'n' vrstni red podatkov na seznamu Array. Seznam Povezani seznam se nanaša na začetni kazalec za iskanje prve lokacije podatkov, od tam pa napoti kazalec, povezan z vsakim podatkom, za iskanje naslednje lokacije podatkov. Postopek iskanja je predvsem odvisen od kazalcev tukaj in nam učinkovito prikazujejo naslednjo lokacijo podatkov.

Konec podatkov

Seznam Array uporablja ničelno vrednost za označevanje konca podatkov, medtem ko Povezani seznam v ta namen uporablja ničelni kazalec. Takoj, ko sistem prepozna ničelne podatke, seznam Array ustavi naslednje iskanje podatkov. Na podoben način ničelni kazalec ustavi sistem, da nadaljuje na naslednje iskanje podatkov.

Povratni prehod

Seznam Povezanih nam omogoča, da s pomočjo descendingiteratorja () prečkate v obratni smeri. Vendar pa na seznamu Array nimamo takšnega objekta - povratna prečkanje tukaj postane težava.

Sintaksa

Poglejmo si Sintaksa Java obeh mehanizmov za shranjevanje.

Ustvarjanje seznama matrike:

Seznam arraylistsample = nov ArrayList ();

Dodajanje predmetov na seznam matrike:

Arraylistsample.add ("ime1");

Arraylistsample.add ("ime2");

Tako bo izgledal rezultat matričnega seznama - [ime1, ime2].

Ustvarjanje povezanega seznama:

Seznam linkedlistsample = nov povezan seznam ();

Dodajanje predmetov na povezan seznam:

Linkedlistsample.add ("ime3");

Linkedlistsample.add ("ime4");

Tako bo izgledal rezultirajoči Povezani seznam - [ime3, ime4].

 Kaj je bolje za operacijo Get ali Search?

Seznam Array vsebuje O (1) čas za začetek kakršnega koli iskanja podatkov, medtem ko Povezani seznam u u (n) za n^th iskanje podatkov. Torej seznam Array vedno uporablja stalen čas za kakršno koli iskanje podatkov, na seznamu Povezani pa je čas, ki je potreben, odvisen od položaja podatkov. Zato so Array seznami vedno boljša izbira za operacije Get ali Search.

Kaj je bolje za vstavljanje ali dodajanje?

Seznam Array in Povezani seznam trajata O (1) za dodajanje podatkov. Če pa je matrika polna, potem seznam Array traja veliko časa, da ga spremenite v velikost in kopirate elemente na novejše. V takšnem primeru je boljši izbor povezan seznam.

Kaj je bolje za odstranjevanje?

Operacija odstranjevanja traja skoraj enako količino časa tako na seznamu Array kot na seznamu Povezani. Na seznamu Array ta operacija izbriše podatke in nato premakne položaj podatkov, da tvori novejši niz - traja O (n) čas. Na seznamu Povezani ta postopek preide na določene podatke in spremeni položaje kazalcev, da oblikuje novejši seznam. Čas za prehod in odstranitev je tudi tukaj O (n).

Kateri je hitrejši?

Vemo, da seznam Array uporablja notranji niz za shranjevanje dejanskih podatkov. Če so torej vsi podatki izbrisani, potem vsi prihodnji podatki potrebujejo premik pomnilnika. Očitno je, da to zahteva precej časa in stvari upočasni. Takšen pomnilnik pomnilnika na seznamu Povezani ni potreben, saj je le sprememba lokacije kazalca. Zato je povezan seznam hitrejši od seznama Array v kateri koli vrsti shranjevanja podatkov. Vendar pa je to povsem odvisno od vrste operacije, tj. Za operacijo Pridobi ali poišči Povezani seznam potrebuje veliko več časa kot seznam Array. Ko pogledamo celotno uspešnost, lahko rečemo, da je seznam povezav hitrejši.

Kdaj uporabljati seznam matic in povezan seznam?

Seznam Array je najprimernejši za manjše potrebe po podatkih, kjer je na voljo neprekinjen pomnilnik. Ko pa imamo opravka z ogromnimi količinami podatkov, razpoložljivost neprekinjenega pomnilnika izvaja mehanizme za shranjevanje podatkov, ne glede na to, ali je majhna ali ogromna. Nato se odločite, katerega izbrati - Array list ali Povezani seznam. S seznamom nizov lahko nadaljujete, ko potrebujete le shranjevanje in iskanje podatkov. Toda seznam vam lahko pomaga manipulirati s podatki. Ko se odločite, kako pogosto je potrebna obdelava podatkov, je pomembno, da preverite, kakšno vrsto podatkov običajno izvajate. Ko je le Get ali Search, potem je Array Seznam boljša izbira; za druge operacije, kot sta vstavljanje ali brisanje, nadaljujte s povezanim seznamom.

Poglejmo razlike v tabeli.

S. št	Koncepti	Razlike
		Seznam matrikov	Povezani seznam
1	Moda za shranjevanje podatkov	Uporablja zaporedno shranjevanje podatkov	Uporablja nedosledno shranjevanje podatkov
2	Shema notranjega skladiščenja	Vzdržuje notranji dinamični niz	Vzdržuje povezan seznam
3	Uporaba pomnilnika	Zahteva pomnilniški prostor samo za podatke	Zahteva pomnilniški prostor za podatke in tudi za kazalce
4	Velikost začetnega seznama	Potrebuje prostora za vsaj 10 predmetov	Ne potrebuje prostora in lahko ustvarimo celo prazen seznam povezanih velikosti 0.
5	Pridobivanje podatkov	Izračuna kot prvo pozicijo podatkov + 'n', kjer je 'n' vrstni red podatkov na seznamu Array	Prehod od prvega ali zadnjega do potrebnih podatkov
6	Konec podatkov	Null vrednosti označujejo konec	Null Pointer označuje konec
7	Povratni prehod	Ne dovoli	Dovoli s pomočjo descendingiterator ()
8	Sintaksa ustvarjanja seznama	Seznam arraylistsample = nov ArrayList ();	Seznam linkedlistsample = nov povezan seznam ();
9	Dodajanje predmetov	Arraylistsample.add ("ime1");	Linkedlistsample.add ("ime3");
10	Pridobi ali poišči	Vzame čas O (1) in je boljši v izvedbi	Traja O (n) čas in uspešnost je odvisna od položaja podatkov
11	Vstavi ali dodaj	Porabi O (1) čas, razen ko je matrika polna	V vseh okoliščinah porabi O (1) čas
12	Brisanje ali odstranitev	Vzame O (n) čas	Vzame O (n) čas
13	Kdaj uporabljati?	Kadar je vključenih veliko operacij pridobivanja ali iskanja; razpoložljivost pomnilnika bi morala biti že na začetku večja	Kadar je veliko operacij za vstavljanje ali brisanje in razpoložljivosti pomnilnika ni treba stalno