Masīvs un Saistītais saraksts ir divi veidi, kā kārtot datus atmiņā. Pirms saprast atšķirības starp Masīvs un Saistītais saraksts , mēs vispirms skatāmies masīvā un saistīts saraksts .
stīgu savienošana
Kas ir masīvs?
Datu struktūra, kas satur viena veida elementus. Datu struktūra ir veids, kā organizēt datus; masīvs ir datu struktūra, jo tas secīgi organizē datus. Masīvs ir liels atmiņas gabals, kurā atmiņa ir sadalīta mazos mazos blokos, un katrs bloks spēj saglabāt kādu vērtību.
Pieņemsim, ka esam izveidojuši masīvu, kas sastāv no 10 vērtībām, tad katrā blokā tiks saglabāta vesela skaitļa veida vērtība. Ja mēs mēģinām saglabāt vērtību dažādu veidu masīvā, tas nav pareizs masīvs un radīs kompilēšanas laika kļūdu.
Masīva deklarācija
Masīvu var deklarēt šādi:
data_type name of the array[no of elements]
Lai deklarētu masīvu, mums vispirms jānorāda masīva veids un pēc tam masīva nosaukums. Kvadrātiekavās mums ir jānorāda elementu skaits, kam vajadzētu būt mūsu masīvā.
Sapratīsim, izmantojot piemēru.
int a[5];
Iepriekš minētajā gadījumā mēs esam deklarējuši 5 elementu masīvu ar ' a ' anas vārds vesels skaitlis datu tips.
Kas ir saistītais saraksts?
Saistītais saraksts ir nejauši saglabāto mezglu kolekcija. Katrs mezgls sastāv no diviem laukiem, t.i., datus un saite . Šeit dati ir vērtība, kas tiek glabāta konkrētajā mezglā, un saite ir rādītājs, kas satur nākamā mezgla adresi.
Atšķirības starp masīvu un saistīto sarakstu
Mēs nevaram pateikt, kura datu struktūra ir labāka, t.i., masīvs vai saistītais saraksts . Var būt iespēja, ka viena datu struktūra ir labāka viena veida prasībām, bet otra datu struktūra ir labāka cita veida prasībām. Ir dažādi faktori, piemēram, biežas darbības ar datu struktūru vai datu lielums, kā arī citi faktori, uz kuru pamata tiek izvēlēta datu struktūra. Tagad mēs redzēsim dažas atšķirības starp masīvu un saistīto sarakstu, pamatojoties uz dažiem parametriem.
1. Maksa par piekļuvi elementam
Masīva gadījumā neatkarīgi no masīva lieluma masīvam ir nepieciešams nemainīgs laiks, lai piekļūtu elementam. Masīvā elementi tiek glabāti blakus, tāpēc, ja mēs zinām elementa bāzes adresi, mēs varam viegli iegūt jebkura masīva elementa adresi. Mums ir jāveic vienkāršs aprēķins, lai iegūtu jebkura masīva elementa adresi. Tātad, piekļuve elementam masīvā ir O(1) laika sarežģītības ziņā.
Saistītajā sarakstā elementi netiek glabāti blakus. Tas sastāv no vairākiem blokiem, un katrs bloks tiek attēlots kā mezgls. Katram mezglam ir divi lauki, t.i., viens ir paredzēts datu laukam, bet vēl viens saglabā nākamā mezgla adresi. Lai atrastu jebkuru mezglu saistītajā sarakstā, mums vispirms ir jānosaka pirmais mezgls, kas pazīstams kā galvenais mezgls. Ja mums ir jāatrod otrais mezgls sarakstā, tad mums jāšķērso no pirmā mezgla, un sliktākajā gadījumā, lai atrastu pēdējo mezglu, mēs šķērsosim visus mezglus. Piekļuves elementam vidējais gadījums ir O(n).
Mēs secinām, ka maksa par piekļuvi elementam masīvā ir mazāka nekā saistītajam sarakstam. Tāpēc, ja mums ir kādas prasības piekļūt elementiem, masīvs ir labāka izvēle.
singleton dizains
2. Elementa ievietošanas izmaksas
Ievietojumā var būt trīs scenāriji:
Saistītā saraksta gadījumā, lai ievietotu elementu saistītā saraksta sākumā, mēs izveidosim jaunu mezglu, un jaunajam mezglam tiks pievienota pirmā mezgla adrese. Tādā veidā jaunais mezgls kļūst par pirmo mezglu. Tātad laika sarežģītība nav proporcionāla saraksta lielumam. Laika sarežģītība būtu nemainīga, t.i., O(1).
Ja masīvs nav pilns, mēs varam tieši pievienot jauno elementu, izmantojot indeksu. Šajā gadījumā laika sarežģītība būtu nemainīga, t.i., O(1). Ja masīvs ir pilns, mums vispirms ir jākopē masīvs citā masīvā un jāpievieno jauns elements. Šajā gadījumā laika sarežģītība būtu O(n).
Lai ievietotu elementu saistītā saraksta beigās, mums ir jāšķērso viss saraksts. Ja saistītais saraksts sastāv no n elementiem, tad laika sarežģītība būtu O(n).
Pieņemsim, ka mēs vēlamies ievietot elementu pie ithmasīva pozīcija; mums ir jāpārvieto n/2 elementi pa labi. Tāpēc laika sarežģītība ir proporcionāla elementu skaitam. Laika sarežģītība vidējam gadījumam būtu O(n).
aws sarkanā nobīde
Saistītā saraksta gadījumā mums ir jāpārvietojas uz to pozīciju, kurā jāievieto jaunais elements. Lai gan mums nav jāveic nekāda veida pārslēgšana, bet mums ir jāpārvietojas uz n/2 pozīciju. Patērētais laiks ir proporcionāls n elementu skaitam, un laika sarežģītība vidējam gadījumam būtu O(n).
Rezultātā iegūtais saistīto saraksts ir:
Salīdzinot ar saistīto sarakstu, masīva ieviešana ir vienkārša. Veidojot programmu, izmantojot saistīto sarakstu, programma ir vairāk pakļauta kļūdām, piemēram, segmentācijas kļūmei vai atmiņas noplūdei. Tāpēc, veidojot programmu saistītajā sarakstā, ir jābūt ļoti uzmanīgiem.
Saistītajam sarakstam ir dinamisks izmērs, savukārt masīvs ir statisks. Šeit statisks nenozīmē, ka mēs nevaram noteikt izmēru izpildes laikā, bet mēs nevaram to mainīt, kad izmērs ir izlemts.
3. Atmiņas prasības
Tā kā masīva elementi glabājas vienā blakus esošā atmiņas blokā, masīvs ir fiksēta izmēra. Pieņemsim, ka mums ir 7. izmēra masīvs un masīvs sastāv no 4 elementiem, tad pārējā vieta netiek izmantota. Atmiņa, ko aizņem 7 elementi:
Atmiņas vieta = 7 * 4 = 28 baiti
Kur 7 ir elementu skaits masīvā un 4 ir vesela skaitļa tipa baitu skaits.
Saistītā saraksta gadījumā neizmantotas atmiņas nav, bet papildu atmiņu aizņem rādītāja mainīgie. Ja dati ir vesela skaitļa tipa, tad viena mezgla kopējā atmiņa ir 8 baiti, t.i., 4 baiti datiem un 4 baiti rādītāja mainīgajam. Ja saistītais saraksts sastāv no 4 elementiem, tad saistītā saraksta aizņemtā atmiņas vieta būtu:
tīmekļa draiveris
Atmiņas vieta = 8 * 4 = 32 baiti
Saistītais saraksts būtu labāka izvēle, ja datu daļa ir lielāka. Pieņemsim, ka dati ir 16 baiti. Masīva aizņemtā atmiņas vieta būtu 16 * 7 = 112 baiti, savukārt saistītais saraksts aizņem 20 * 4 = 80, šeit mēs esam norādījuši 20 baitus kā 16 baitus datu lielumam plus 4 baiti rādītāja mainīgajam. Ja mēs izvēlamies lielāku datu apjomu, saistītais saraksts patērētu mazāk atmiņas; pretējā gadījumā tas ir atkarīgs no faktoriem, kurus mēs izmantojam, lai noteiktu izmēru.
Apskatīsim atšķirības starp masīvu un saistīto sarakstu tabulas veidā.
| Masīvs | Saistītais saraksts |
|---|---|
| Masīvs ir līdzīga datu tipa elementu kolekcija. | Saistītais saraksts ir objektu kopums, kas pazīstams kā mezgls, kurā mezgls sastāv no divām daļām, t.i., datiem un adreses. |
| Masīva elementi tiek glabāti blakus esošā atmiņas vietā. | Saistītos saraksta elementus var saglabāt jebkur atmiņā vai nejauši saglabāt. |
| Masīvs darbojas ar statisku atmiņu. Šeit statiskā atmiņa nozīmē, ka atmiņas lielums ir fiksēts un to nevar mainīt izpildes laikā. | Saistītais saraksts darbojas ar dinamisko atmiņu. Šeit dinamiskā atmiņa nozīmē, ka atmiņas lielumu var mainīt darbības laikā atbilstoši mūsu prasībām. |
| Masīva elementi ir neatkarīgi viens no otra. | Saistītie saraksta elementi ir atkarīgi viens no otra. Tā kā katrā mezglā ir nākamā mezgla adrese, lai piekļūtu nākamajam mezglam, mums ir jāpiekļūst tā iepriekšējam mezglam. |
| Masīvs aizņem vairāk laika, veicot jebkuru darbību, piemēram, ievietošanu, dzēšanu utt. | Saistītais saraksts aizņem mazāk laika, veicot jebkādas darbības, piemēram, ievietošanu, dzēšanu utt. |
| Piekļuve jebkuram masīva elementam ir ātrāka, jo masīva elementam var tieši piekļūt, izmantojot indeksu. | Piekļuve elementam saistītajā sarakstā ir lēnāka, jo tas sāk pārvietoties no pirmā saistītā saraksta elementa. |
| Masīva gadījumā atmiņa tiek piešķirta kompilēšanas laikā. | Saistīta saraksta gadījumā atmiņa tiek piešķirta izpildes laikā. |
| Atmiņas izmantošana masīvā ir neefektīva. Piemēram, ja masīva lielums ir 6 un masīvs sastāv tikai no 3 elementiem, pārējā vieta netiks izmantota. | Atmiņas izmantošana ir efektīva saistīta saraksta gadījumā, jo atmiņu var piešķirt vai atdalīt izpildes laikā atbilstoši mūsu prasībām. |