Atšķirība starp masīvu sarakstu un saistīto sarakstu

Kā tiek glabāti dati?

Masīvu saraksts un Saistītais saraksts ir izplatīti termini datu glabāšanai un izguvei. Lai gan ir daudz glabāšanas ierīču, galu galā tās ir atkarīgas no glabāšanas mehānisma. Šie divi glabāšanas mehānismi ievieto jūsu datus atmiņas ierīcēs un pēc nepieciešamības tos izgūst. Apskatīsim, kā viņi datus glabā atmiņā. Masīvu sarakstā tiek izmantota secīga krātuve, un datu gabali tiek glabāti viens pēc otra. Iespējams, ka tas ir vienkāršāks uzglabāšanas veids - tas ļauj izvairīties no neskaidrībām. Jā, nākamo vienumu vai datus mēs varam izgūt no masīvu saraksta nākamās atmiņas vietas; tomēr tas tiek saglabāts ar norāžu palīdzību saistītajā sarakstā. Šeit mums ir vajadzīgas divas atmiņas vietas glabāšanai - viena datiem, otra rādītājam. Rādītājs norāda nākamo datu atmiņas vietu. Mēs viegli saprotam, ka saistītais saraksts nekad neuzglabā datus secīgi; drīzāk tas izmanto nejaušas glabāšanas mehānismu. Norādījumi ir galvenie elementi, lai atrastu datu vietas atmiņā.

Dinamiskais masīvs un saistītais saraksts

Mēs jau esam apsprieduši, kā dati tiek ievietoti abos glabāšanas mehānismos, un masīvu saraksta iekšējās glabāšanas shēmai mēs varam dot terminu “dinamisks masīvs”. Tajā vienkārši tiek ievietoti datu elementi viens pēc otra - no nosaukuma -, savukārt saistītais saraksts nākamā vienuma izsekošanai izmanto iekšēju sarakstu ar norādījumu palīdzību. Tāpēc, lai parādītu mums nākamos datus, tas izmanto iekšēji saistītu sarakstu, piemēram, atsevišķi vai divreiz saistītu sarakstu.

Atmiņas lietošana

Tā kā masīvu sarakstā tiek glabāti tikai faktiskie dati, mums ir nepieciešama vieta tikai glabātajiem datiem. Un otrādi - saistītajā sarakstā mēs izmantojam arī norādes. Tāpēc ir vajadzīgas divas atmiņas vietas, un mēs varam teikt, ka saistītais saraksts patērē vairāk atmiņas nekā masīvu saraksts. Saistītā saraksta izdevīgā puse ir tā, ka mūsu datu glabāšanai nekad nav vajadzīgas nepārtrauktas atmiņas vietas pretstatā masīvu sarakstam. Norādes spēj noturēt nākamās datu atrašanās vietas stāvokli, un mēs varam izmantot pat mazākus atmiņas slotus, kas nav nepārtraukti. Runājot par atmiņas izmantošanu, rādītājiem ir galvenā loma saistīto sarakstā, tāpat arī to efektivitātei.

Sākotnējā masīva saraksta un saistītā saraksta lielums

Ar masīvu sarakstu pat tukša saraksta izmērs ir 10, bet ar saistīto sarakstu mums tik milzīga vieta nav vajadzīga. Mēs varam izveidot tukšu saistīto sarakstu ar lielumu 0. Vēlāk mēs varam palielināt to pēc nepieciešamības.

Datu izguve

Masīvu sarakstā datu iegūšana ir vienkāršāka, jo tā tiek saglabāta secīgi. Atliek tikai noteikt pirmās datu atrašanās vietu; no turienes secīgi piekļūst nākamajai atrašanās vietai, lai iegūtu pārējo. Tas tiek aprēķināts tāpat kā pirmā datu pozīcija + 'n', kur 'n' ir datu secība masīva sarakstā. Saistītais saraksts norāda sākotnējo rādītāju, lai atrastu pirmo datu atrašanās vietu, un no turienes tas norāda rādītāju, kas saistīts ar katru datu, lai atrastu nākamo datu atrašanās vietu. Ielādes process galvenokārt ir atkarīgs no šeit norādītajiem rādītājiem, un tie mums faktiski parāda nākamo datu atrašanās vietu.

Datu beigas

Masīva sarakstā datu beigu atzīmei tiek izmantota nulles vērtība, savukārt saistītajam sarakstam šim nolūkam tiek izmantots nulles rādītājs. Tiklīdz sistēma atpazīst nulles datus, Masīvu saraksts pārtrauc nākamo datu izguvi. Līdzīgā veidā nulles rādītājs aptur sistēmu no nākamās datu izguves.

Atpakaļgaita

Saistītais saraksts ļauj mums virzīties pretējā virzienā ar descenditeiteratora palīdzību (). Tomēr masīvu sarakstā mums šādas iespējas nav - apgrieztā šķērsošana šeit kļūst par problēmu.

Sintakse

Apskatīsim abu glabāšanas mehānismu Java sintakse.

Masīvu saraksta izveidošana:

Sarakstu arraylistsample = new ArrayList ();

Objektu pievienošana masīvu sarakstam:

Arraylistsample.add (“name1”);

Arraylistsample.add (“name2”);

Šādi izskatīsies iegūtais masīvu saraksts - [name1, name2].

Saistītā saraksta izveidošana:

Saistītie saraksti paraugs = jauns piesaistītais saraksts ();

Objektu pievienošana saistītajam sarakstam:

Linkedlistsample.add (“name3”);

Linkedlistsample.add (“name4”);

Šādi izskatīsies izveidotais saistīto saraksts - [name3, name4].

 Kura ir labāka operācijai Iegūt vai meklēt?

Masīvu sarakstam ir nepieciešams O (1) laiks, lai palaistu jebkuru datu meklēšanu, savukārt Saistītajam sarakstam n u ir u O (n).^th datu meklēšana. Tāpēc masīvu sarakstā datu meklēšanai vienmēr tiek izmantots nemainīgs laiks, bet saistītajā sarakstā izmantotais laiks ir atkarīgs no datu atrašanās vietas. Tāpēc masīvu saraksti vienmēr ir labāka izvēle Get vai Search operācijām.

Kura ir labāka ievietošanas vai pievienošanas operācijai?

Gan masīvu sarakstam, gan saistītajam sarakstam datu pievienošanai nepieciešams O (1) laiks. Bet, ja masīvs ir pilns, masīvu sarakstam ir nepieciešams daudz laika, lai mainītu tā izmērus un kopētu vienumus uz jaunāku. Šādā gadījumā labāka izvēle ir saistītais saraksts.

Kura ir labāka operācijai noņemt?

Noņemšanas darbība prasa gandrīz tikpat daudz laika gan masīva sarakstā, gan saistītajā sarakstā. Masīva sarakstā šī darbība izdzēš datus un pēc tam maina datu pozīciju, lai izveidotu jaunāku masīvu - tas prasa O (n) laiku. Saistītajā sarakstā šī darbība tiek virzīta uz konkrētajiem datiem un maina rādītāja pozīcijas, veidojot jaunāku sarakstu. Arī šķērsošanas un noņemšanas laiks šeit ir O (n).

Kurš ir ātrāks?

Mēs zinām, ka Masīvu sarakstā tiek izmantots iekšējais masīvs, lai saglabātu faktiskos datus. Tāpēc, ja kādi dati tiek izdzēsti, visiem nākamajiem datiem ir nepieciešama atmiņas maiņa. Acīmredzot tas prasa daudz laika un palēnina lietas gaitu. Saistītajā sarakstā šāda atmiņas maiņa nav nepieciešama, jo tas viss ir tikai rādītāja vietas maiņa. Tāpēc jebkura veida datu glabāšanā saistītais saraksts ir ātrāks nekā masīvu saraksts. Tomēr tas ir pilnībā atkarīgs no operācijas veida, t.i., lai iegūtu vai meklētu operāciju, saistītais saraksts prasa daudz vairāk laika nekā masīva saraksts. Apskatot kopējo sniegumu, mēs varam teikt, ka saistīto saraksts ir ātrāks.

Kad izmantot masīvu sarakstu un saistīto sarakstu?

Masīvu saraksts ir vislabāk piemērots mazākām datu prasībām, ja ir pieejama nepārtraukta atmiņa. Bet, kad mēs strādājam ar milzīgu datu daudzumu, nepārtrauktas atmiņas pieejamība īsteno datu glabāšanas mehānismus neatkarīgi no tā, vai tie ir mazi vai milzīgi. Pēc tam izlemiet, kuru izvēlēties - masīvu sarakstu vai saistīto sarakstu. Masīvu sarakstu varat turpināt, ja jums vienkārši nepieciešama datu glabāšana un izguve. Bet saraksts var jums palīdzēt, manipulējot ar datiem. Kad esat izlēmis, cik bieži ir jāveic manipulācijas ar datiem, ir svarīgi pārbaudīt, kāda veida datus parasti izgūstat. Kad tas ir tikai Iegūt vai meklēt, labāka izvēle ir masīvu saraksts; citām operācijām, piemēram, ievietošanai vai dzēšanai, dodieties uz saistīto sarakstu.

Apskatīsim atšķirības tabulas formā.

S.Nē	Koncepcijas	Atšķirības
		Masīvu saraksts	Saistītais saraksts
1	Datu glabāšanas mode	Izmanto secīgu datu glabāšanu	Izmanto ne secīgu datu glabāšanu
2	Iekšējās glabāšanas shēma	Uztur iekšējo dinamisko masīvu	Uztur saistīto sarakstu
3	Atmiņas lietošana	Nepieciešama atmiņas vieta tikai datiem	Nepieciešama atmiņas vieta datiem, kā arī rādītājiem
4	Sākotnējā saraksta lielums	Nepieciešama vieta vismaz 10 priekšmetiem	Nav nepieciešama vieta, un mēs pat varam izveidot tukšu saistīto sarakstu ar lielumu 0.
5	Datu izguve	Aprēķina tāpat kā pirmā datu pozīcija + 'n', kur 'n' ir datu secība masīva sarakstā	Nepieciešami šķērsojumi no pirmā vai pēdējā līdz nepieciešamajiem datiem
6	Datu beigas	Null vērtības iezīmē beigas	Null Pointer iezīmē beigas
7	Atpakaļgaita	Neļauj to darīt	Ļauj tam izmantot descendingiterator ()
8	Saraksta veidošanas sintakse	Sarakstu arraylistsample = new ArrayList ();	Saistītie saraksti paraugs = jauns piesaistītais saraksts ();
9	Objektu pievienošana	Arraylistsample.add (“name1”);	Linkedlistsample.add (“name3”);
10	Iegūstiet vai meklējiet	Ņem O (1) laiku un ir labāks sniegumā	Ņem O (n) laiks un veiktspēja ir atkarīga no datu atrašanās vietas
11	Ievietot vai papildināt	Patērē O (1) laiku, izņemot gadījumus, kad masīvs ir pilns	Jebkurā gadījumā patērē O (1) laiku
12	Dzēšana vai noņemšana	Ņem O (n) laiku	Ņem O (n) laiku
13	Kad lietot?	Ja ir iesaistītas daudz meklēšanas vai meklēšanas operācijas; atmiņas pieejamībai vajadzētu būt lielākai pat sākumā	Ja ir daudz ievietošanas vai dzēšanas darbību un atmiņas pieejamībai nav jābūt nepārtrauktai