Skirtumas tarp masyvų sąrašo ir susietų sąrašų

Kaip saugomi duomenys?

Masyvų sąrašas ir Susietų sąrašas yra įprasti terminai, kai reikia saugoti ir nuskaityti duomenis. Nors saugojimo įrenginių yra daug, galiausiai jie priklauso nuo saugojimo mechanizmo. Šie du saugojimo mechanizmai talpina jūsų duomenis į saugojimo įrenginius ir, kai reikia, juos nuskaito. Pažvelkime, kaip jie saugo duomenis savo atmintyje. Masyvų sąraše naudojama nuosekli saugykla, o duomenų dalys saugomos viena po kitos. Tai galbūt yra paprastesnė saugojimo forma - išvengiama painiavos. Taip, mes galime nuskaityti kitą elementą ar duomenis iš kitos masyvų sąrašo atminties vietos; tačiau jis saugomas naudojant nuorodų sąrašą „Susietų“ sąraše. Čia mums reikia dviejų atminties vietų saugojimui - viena duomenims, kita - rodyklei. Rodyklė nurodo kitų duomenų atminties vietą. Mes lengvai suprantame, kad susietas sąrašas niekada nekaupia duomenų iš eilės; veikiau jis naudoja atsitiktinio saugojimo mechanizmą. Rodyklės yra pagrindiniai elementai nustatant duomenų vietas atmintyje.

Dinaminis masyvas ir susietų sąrašas

Mes jau aptarėme, kaip abu saugojimo mechanizmai įtraukia duomenis ir galime suteikti terminą „dinaminis masyvas“ masyvų sąrašo vidinei saugojimo schemai. Tiesiog pateikiami duomenų fragmentai vienas po kito - nurodykite pavadinimą -, o susietas sąrašas naudoja vidinį sąrašą rodyklių pagalba sekant kitą elementą. Todėl jis naudoja vidinį susietą sąrašą, kaip atskirai ar dvigubai susietą sąrašą, kad parodytų mums kitus duomenis.

Atminties naudojimas

Kadangi Masyvų sąraše saugomi tik faktiniai duomenys, mums reikia vietos tik saugomiems duomenims. Atvirkščiai, susietų sąraše mes taip pat naudojame rodykles. Todėl reikia dviejų atminties vietų ir galime pasakyti, kad susietas sąrašas sunaudoja daugiau atminties nei masyvų sąrašas. Naudinga susietojo sąrašo pusė yra ta, kad niekada nereikia nuolatinės atminties vietų mūsų duomenims saugoti, priešingai nei masyvo sąraše. Rodyklės yra pajėgios išlaikyti kitos duomenų vietos vietą, ir mes galime naudoti net mažesnius atminties lizdus, kurie nėra ištisiniai. Kalbant apie atminties naudojimą, rodyklės vaidina pagrindinį vaidmenį Susietų sąraše, taip pat jų efektyvumas.

Pradinio masyvo sąrašo ir susietų sąrašų dydis

Turint masyvo sąrašą, net tuščiam sąrašui reikia 10 dydžio, tačiau naudojant susietą sąrašą mums nereikia tokios didžiulės vietos. Galime sukurti tuščią susietų sąrašą, kurio dydis yra 0. Vėliau galime padidinti pagal poreikį.

Duomenų gavimas

Duomenų gavimas masyvų sąraše yra paprastesnis, nes jie kaupiami iš eilės. Viskas, ką reikia padaryti, yra nustatyti pirmąją duomenų vietą; iš ten sekanti vieta pasiekiama paeiliui, kad būtų atkurta likusi dalis. Jis apskaičiuojamas kaip pirmoji duomenų padėtis + 'n', kur 'n' yra duomenų eiliškumas masyvo sąraše. Susietas sąrašas nurodo pradinį rodyklę, kad būtų galima rasti pirmąją duomenų vietą, o iš ten nurodo rodyklę, susietą su kiekvienu duomenimis, kad rastų kitą duomenų vietą. Gavimo procesas daugiausia priklauso nuo čia esančių rodyklių, ir jie iš tikrųjų parodo mums kitą duomenų vietą.

Duomenų pabaiga

Masyvų sąrašas naudoja nulinę reikšmę duomenų pabaigai žymėti, o susietas sąrašas šiam tikslui naudoja nulinį žymeklį. Kai tik sistema atpažįsta nulinius duomenis, masyvų sąrašas sustabdo kitą duomenų gavimą. Panašiu būdu nulinis žymiklis sustabdo sistemos eigą prie kito duomenų gavimo.

Atbulinis važiavimas

Susietų sąrašas leidžia mums judėti atvirkštine kryptimi, naudojantis descenditeratoriumi (). Tačiau masyvo sąraše tokios galimybės neturime - atvirkštinis važiavimas čia tampa problema.

Sintaksė

Pažvelkime į abiejų saugojimo mechanizmų „Java“ sintaksę.

Masyvų sąrašo kūrimas:

Sąrašas arraylistsample = new ArrayList ();

Objektų įtraukimas į masyvų sąrašą:

Arraylistsample.add („name1“);

Arraylistsample.add („name2“);

Taip atrodys gaunamas masyvų sąrašas - [name1, name2].

Susieto sąrašo sudarymas:

Pateikti susietų sąrašų pavyzdį = Naujas susietų sąrašas ();

Objektų įtraukimas į susietą sąrašą:

„Linkedlistsample.add“ („name3“);

„Linkedlistsample.add“ („name4“);

Taip atrodys susietas sąrašas - [name3, name4].

Kuris yra geresnis gavimo ar paieškos operacijai?

Masyvų sąrašui prireikia O (1) laiko bet kokiai duomenų paieškai vykdyti, tuo tarpu susietų sąrašas užima u O (n) n^tūkstduomenų paieška. Todėl masyvų sąrašas visada naudoja pastovų laiką bet kokiai duomenų paieškai, tačiau susietojo sąrašo metu laikas priklauso nuo duomenų padėties. Todėl masyvo sąrašai visada yra geresnis pasirinkimas norint gauti arba ieškoti operacijų.

Kuris yra geresnis įdėjimo ar papildymo operacijai?

Tiek masyvų sąrašui, tiek susietam sąrašui papildyti duomenys užtrunka O (1) laiką. Bet jei masyvas yra pilnas, tada masyvų sąrašas reikalauja nemažai laiko, kad pakeistumėte jo dydį ir nukopijuotumėte elementus į naujesnį. Tokiu atveju „Linked“ sąrašas yra geresnis pasirinkimas.

Kuris yra geresnis šalinimo operacijai?

Pašalinimo operacija užima beveik tiek pat laiko tiek masyvų sąraše, tiek susietų sąraše. Masyvų sąraše ši operacija ištrina duomenis ir paskui keičia duomenų vietą, kad būtų suformuotas naujesnis masyvas - tai užima O (n) laiko. Susietame sąraše ši operacija pereina prie konkrečių duomenų ir keičia žymeklio pozicijas, kad būtų sudarytas naujesnis sąrašas. Važiavimo ir pašalinimo laikas taip pat yra O (n).

Kuris yra greitesnis?

Mes žinome, kad masyvų sąraše faktiniams duomenims saugoti naudojamas vidinis masyvas. Taigi, jei bet kokie duomenys ištrinami, tada visus būsimus duomenis reikia pakeisti atmintimi. Akivaizdu, kad tam reikia nemažai laiko ir tai sulėtėja. Toks atminties poslinkis nėra būtinas susietų sąraše, nes viskas keičia žymeklio vietą. Todėl susietų sąrašas yra greitesnis nei masyvų sąrašas bet kokio tipo duomenų saugyklose. Tačiau tai visiškai priklauso nuo operacijos tipo, t. Y. Operacijai „Gauti ar ieškoti“ susietas sąrašas užima daug daugiau laiko nei masyvo sąrašas. Pažvelgę į bendrą našumą galime pasakyti, kad susietų sąrašas yra greitesnis.

Kada naudoti masyvų sąrašą ir susietą sąrašą?

Masyvų sąrašas geriausiai tinka mažesniems duomenų poreikiams ten, kur yra nuolatinė atmintis. Bet kai mes susiduriame su didžiuliu duomenų kiekiu, nuolatinė atmintis įgyvendina duomenų saugojimo mechanizmus, nesvarbu, ar jie yra maži, ar didžiuliai. Tada nuspręskite, kurį pasirinkti - masyvų sąrašą arba susietą sąrašą. Galite pereiti prie masyvų sąrašo, kai jums tereikia saugoti ir nuskaityti duomenis. Bet sąrašas gali jums padėti, manipuliuodamas duomenimis. Kai nuspręsite, kaip dažnai reikia manipuliuoti duomenimis, svarbu patikrinti, kokį duomenų nuskaitymo būdą dažniausiai atliekate. Kai tai tik „Gaukite arba ieškokite“, tada masyvų sąrašas yra geresnis pasirinkimas; jei norite atlikti kitas operacijas, tokias kaip įterpimas ar ištrynimas, eikite į susietų sąrašą.

Pažvelkime į lentelių formos skirtumus.

S.Ne	Sąvokos	Skirtumai
S.Ne	Sąvokos	Masyvų sąrašas	Susietas sąrašas
1	Duomenų saugojimo mada	Naudojama nuosekli duomenų saugykla	Naudoja nenuoseklią duomenų saugyklą
2	Vidinė saugojimo schema	Palaiko vidinį dinaminį masyvą	Turi susietų sąrašą
3	Atminties naudojimas	Reikia tik atminties vietos duomenims	Reikia atminties vietos duomenims ir rodyklėms
4	Pradinio sąrašo dydis	Reikia vietos bent 10 daiktų	Nereikia vietos ir mes netgi galime sukurti tuščią susietų 0 dydžių sąrašą.
5	Duomenų gavimas	Skaičiuojama kaip pirmoji duomenų padėtis + 'n', kur 'n' yra duomenų eiliškumas masyvų sąraše	Važiavimas nuo pirmo ar paskutinio iki reikiamų duomenų
6	Duomenų pabaiga	Null reikšmės žymi pabaigą	Null žymeklis žymi pabaigą
7	Atbulinis važiavimas	Neleidžia	Leidžia tai padaryti naudojant descendingiterator ()
8	Sąrašo sudarymo sintaksė	Sąrašas arraylistsample = new ArrayList ();	Pateikti susietų sąrašų pavyzdį = Naujas susietų sąrašas ();
9	Objektų pridėjimas	Arraylistsample.add („name1“);	„Linkedlistsample.add“ („name3“);
10	Gaukite arba ieškokite	Laiko O (1) laikas ir yra geresnių rezultatų	Laikoma, kad O (n) laikas ir našumas priklauso nuo duomenų padėties
11	Įterpti arba papildyti	Sunaudoja O (1) laiką, išskyrus atvejus, kai masyvas yra pilnas	Visomis aplinkybėmis sunaudoja O (1) laiką
12	Ištrynimas arba pašalinimas	Laiko O (n) laikas	Laiko O (n) laikas
13	Kada naudoti?	Kai yra daug „Get or Search“ operacijų; atminties prieinamumas turėtų būti didesnis net pradžioje	Kai yra daug įterpimo arba ištrynimo operacijų, o atmintis neturi būti nuolat naudojama

Programinė įranga