Massiiviloendi ja lingitud loendi erinevus

Kuidas andmeid hoitakse??

Massiiviloend ja lingitud loend on andmete salvestamise ja hankimise levinud mõisted. Kuigi salvestusseadmeid on palju, sõltuvad need lõppkokkuvõttes salvestusmehhanismist. Need kaks salvestusmehhanismi paigutavad teie andmed salvestusseadmetesse ja hangivad need vajadusel üles. Vaatame, kuidas nad andmeid oma mällu talletavad. Massiivide loend kasutab järjestikust salvestust ja andmeid tükki hoitakse üksteise järel. See on võib-olla lihtsam ladustamisviis - see hoiab ära segaduse. Jah, me saame järgmise elemendi või andmed massiivi nimekirja järgmisest mälukohast; siiski salvestatakse see osutite abil lingitud loendisse. Siin on meil vaja kahte mälukohta ladustamiseks - üks andmete jaoks, teine ​​osuti jaoks. Kursor näitab järgmiste andmete mälukohta. Saame hõlpsasti aru, et lingitud loend ei salvesta andmeid kunagi järjestikku; pigem kasutab see juhuslikku salvestusmehhanismi. Osutused on võtmeelemendid mälu andmete asukohtade leidmisel.

Dünaamiline massiiv ja lingitud loend

Oleme juba arutanud, kuidas mõlemad salvestusmehhanismid andmeid sisestavad ja massiivi loendi sisemise salvestusskeemi jaoks võime anda termini „dünaamiline massiiv”. See paneb lihtsalt andmeühikud üksteise järel - siis nime järgi -, samas kui lingitud loend kasutab järgmise üksuse jälgimiseks osutite abil sisemist loendit. Seetõttu kasutab ta järgmiste andmete kuvamiseks sisemist lingitud nimekirja, nagu üksikult või kahekordselt lingitud loetelu.

Mälu kasutamine

Kuna massiiviloend salvestab ainult tegelikke andmeid, vajame ruumi ainult meie salvestatud andmete jaoks. Vastupidiselt, lingitud loendis kasutame ka viiteid. Seetõttu on vaja kahte mälupesa ja võime öelda, et lingitud loend kulutab rohkem mälu kui massiivide loend. Lingitud nimekirja eeliseks on see, et see ei eelda kunagi meie andmete salvestamiseks pidevat mälukohta, erinevalt massiivi loendist. Osutid on võimelised hoidma järgmise andmekoha positsiooni ja võime kasutada isegi väiksemaid mälupesi, mis pole pidevad. Mälukasutuse osas mängivad osutid lingitud loendis peamist rolli ja ka nende tõhusus.

Esialgse massiiviloendi ja lingitud loendi suurus

Massiiviloendi korral on isegi tühja nimekirja jaoks vaja 10, kuid lingitud loendi korral pole meil nii suurt ruumi vaja. Saame luua tühja lingitud loendi suurusega 0. Hiljem saame seda vajadusel suurendada.

Andmete taastamine

Andmete otsimine on massiiviloendis lihtsam, kuna see salvestub järjest. Vaja on vaid tuvastada esimene andmete asukoht; sealt pääseb järgmisele kohale järjestikku, et ülejäänud kokku saada. See arvutatakse nagu esimene andmepositsioon + 'n', kus 'n' on massiivide loendis olevate andmete järjekord. Lingitud loend osutab esialgsele osutile esimese andmete asukoha leidmiseks ja sealt see osutab iga andmetega seotud osutile järgmise andmete asukoha leidmiseks. Väljastusprotsess sõltub peamiselt siin olevatest osutitest ja need näitavad meile tõhusalt järgmist andmete asukohta.

Andmete lõpp

Massiivi loend kasutab andmete lõpu tähistamiseks nullväärtust, samas kui seostatud loend kasutab selleks nullkursorit. Niipea kui süsteem tuvastab nullandmed, peatab massiiviloend järgmise andmete hankimise. Sarnasel viisil peatab nullkursor süsteemi jätkamise järgmise andmeotsinguga.

Tagurpidi liikumine

Lingitud loend võimaldab meil laskuva desiteraatori () abil vastupidises suunas liikuda. Massiivide loendis meil sellist võimalust siiski pole - tagurpidi liikumine muutub siin probleemiks.

Süntaks

Vaatame mõlema salvestusmehhanismi Java süntaksi.

Massiiviloendi loomine:

Loend arraylistsample = new ArrayList ();

Objektide lisamine massiiviloendisse:

Arraylistsample.add (“nimi1”);

Arraylistsample.add (“nimi2”);

Nii näeb välja tulemuseks olev massiivide loend - [name1, name2].

Lingitud loendi loomine:

Loetelude lingitud loetelu = uus linkitud loend ();

Objektide lisamine lingitud loendisse:

Linkedlistsample.add (“nimi3”);

Linkedlistsample.add (“nimi4”);

Nii näeb välja tulenev lingitud loend - [name3, name4].

 Kumb on parem operatsiooni Hangi või otsimine jaoks?

Massiivide loend võtab andmeotsingute tegemiseks O (1) aega, samas kui lingitud loend võtab n O jaoks n O (n)^th andmete otsing. Seetõttu kasutab massiivide loend andmete otsimiseks alati konstantset aega, kuid lingitud loendis sõltub kuluv aeg andmete asukohast. Seetõttu on massiivide loendid alati parem valik Hangi või Otsi toimingute jaoks.

Milline on parem sisestamise või lisamisega seotud toimingute jaoks?

Nii massiivide loend kui ka lingitud loend võtab andmete lisamiseks aega O (1). Kuid kui massiiv on täis, võtab massiivide loend selle suuruse muutmiseks ja üksuste uude kopeerimiseks märkimisväärselt palju aega. Sel juhul on parem valik Linked.

Kumb on parem operatsiooni Eemaldamine jaoks?

Eemaldamise toiming võtab nii massiivi loendis kui ka lingitud loendis peaaegu sama palju aega. Massiivi loendis kustutab see toiming andmed ja nihutab seejärel andmete asukohta uuema massiivi moodustamiseks - see võtab O (n) aega. Lingitud loendis liigub see toiming konkreetsete andmete juurde ja muudab kursori positsioone, moodustades uuema loendi. Läbiviimise ja eemaldamise aeg on siin ka O (n).

Kumb on kiirem?

Me teame, et massiivide loend kasutab tegelike andmete salvestamiseks sisemist massiivi. Seega, kui mõni teave kustutatakse, vajavad kõik eelseisvad andmed mäluvahetust. Ilmselt nõuab see märkimisväärselt palju aega ja aeglustab asju. Sellist mälu nihutamist pole lingitud loendis vaja, kuna see muudab vaid osuti asukohta. Seetõttu on lingitud loend kiirem kui massiivide loend igasuguses andmesalvestuses. See sõltub aga puhtalt toimingu tüübist, s.t operatsiooni Hangi või otsimine jaoks võtab lingitud loend palju rohkem aega kui massiivi loend. Üldist toimivust vaadates võime öelda, et lingitud nimekiri on kiirem.

Millal kasutada massiiviloendit ja lingitud loendit??

Massiivide loend sobib kõige paremini väiksemate andmenõuete jaoks, kui pidev mälu on saadaval. Kuid kui tegeleme tohutute andmemahtudega, rakendab pideva mälu olemasolu andmesalvestusmehhanisme, olgu see siis väike või tohutu. Järgmisena otsustage, kumba valida - massiiviloend või lingitud loend. Massiiviloendiga saate edasi minna, kui vajate lihtsalt andmete salvestamist ja otsimist. Kuid loetelu aitab teil andmete töötlemisega ka kaugemale jõuda. Kui olete otsustanud, kui sageli on andmetega manipuleerimine vajalik, on oluline kontrollida, millist tüüpi andmete otsingut tavaliselt teostate. Kui tegemist on lihtsalt Hangi või Otsimisega, on parem valik Massiiviloend; muude toimingute jaoks, näiteks sisestamine või kustutamine, jätkake lingitud nimekirjaga.

Vaadelgem tabelitabeli erinevusi.

S.Ei	Kontseptsioonid	Erinevused
		Massiivide nimekiri	Lingitud nimekiri
1	Andmesalvestuse mood	Kasutab järjestikust andmesalvestust	Kasutab mitte järjestikust andmete salvestamist
2	Sisemine salvestusskeem	Säilitab sisemise dünaamilise massiivi	Säilitab lingitud nimekirja
3	Mälu kasutamine	Nõuab ainult andmete jaoks mäluruumi	Nõuab mäluruumi nii andmete kui ka viidete jaoks
4	Algloendi suurus	Vajab ruumi vähemalt 10 eseme jaoks	Ei vaja ruumi ja saame luua isegi tühja lingitud loendi suurusega 0.
5	Andmete taastamine	Arvutab nagu esimene andmepositsioon + 'n', kus 'n' on andmete järjekord massiivi loendis	Vajalik on läbimine esimesest või viimasest kuni nõutavate andmete esitamiseni
6	Andmete lõpp	Nullväärtused tähistavad lõppu	Nullkursor tähistab lõppu
7	Tagurpidi liikumine	Ei luba seda	Võimaldab seda laskuva laskuri abil ()
8	Loendi loomise süntaks	Loend arraylistsample = new ArrayList ();	Loetelude lingitud loetelu = uus linkitud loend ();
9	Objektide lisamine	Arraylistsample.add (“nimi1”);	Linkedlistsample.add (“nimi3”);
10	Hankige või otsige	Võtab aega O (1) ja on jõudluses parem	Võtab O (n) aeg ja jõudlus sõltuvad andmete asukohast
11	Lisamine või lisamine	Tarbib O (1) aega, välja arvatud juhul, kui massiiv on täis	Tarbib O (1) aega igas olukorras
12	Kustutamine või eemaldamine	Võtab aega O (n)	Võtab aega O (n)
13	Millal kasutada?	Kui seotud on palju hanke- või otsingutoiminguid; mälu saadavus peaks olema suurem isegi alguses	Kui sisestamise või kustutamise toiminguid on palju ja mälu saadavus ei pea olema pidev