Masyvas ir Susietas sąrašas yra du būdai tvarkyti duomenis atmintyje. Prieš suprasdami skirtumus tarp Masyvas ir Susietas sąrašas , pirmiausia žiūrime masyve ir susietą sąrašą .
pritaikyta išimtis Java
Kas yra masyvas?
Duomenų struktūra, kurioje yra to paties tipo elementai. Duomenų struktūra yra duomenų organizavimo būdas; masyvas yra duomenų struktūra, nes jis nuosekliai tvarko duomenis. Masyvas yra didelė atminties dalis, kurioje atmintis yra padalinta į mažus-mažus blokus ir kiekvienas blokas gali saugoti tam tikrą vertę.
Tarkime, kad sukūrėme masyvą, kurį sudaro 10 reikšmių, tada kiekviename bloke bus saugoma sveikojo skaičiaus vertė. Jei bandysime išsaugoti reikšmę skirtingų tipų masyve, tai nėra teisingas masyvas ir išmes kompiliavimo laiko klaidą.
Masyvo deklaracija
Masyvas gali būti deklaruojamas taip:
data_type name of the array[no of elements]
Norėdami paskelbti masyvą, pirmiausia turime nurodyti masyvo tipą ir tada masyvo pavadinimą. laužtiniuose skliaustuose turime nurodyti elementų, kuriuos turi turėti mūsų masyvas, skaičių.
Supraskime per pavyzdį.
int a[5];
Pirmiau nurodytu atveju paskelbėme 5 elementų masyvą su ' a ' vardas an sveikasis skaičius duomenų tipas.
Kas yra susietų sąrašas?
Susietas sąrašas yra atsitiktinai saugomų mazgų rinkinys. Kiekvienas mazgas susideda iš dviejų laukų, t.y. duomenis ir nuoroda . Čia duomenys yra tame konkrečiame mazge saugoma reikšmė, o nuoroda yra rodyklė, kurioje yra kito mazgo adresas.
Skirtumai tarp masyvo ir susieto sąrašo
Negalime pasakyti, kuri duomenų struktūra yra geresnė, t. y. masyvas ar susietas sąrašas . Gali būti, kad viena duomenų struktūra yra geresnė vienos rūšies reikalavimams, o kita duomenų struktūra yra geresnė kitos rūšies reikalavimams. Yra įvairių veiksnių, pvz., dažnai atliekamos operacijos su duomenų struktūra ar duomenų dydis, taip pat kiti veiksniai, kuriais remiantis pasirenkama duomenų struktūra. Dabar pamatysime keletą skirtumų tarp masyvo ir susieto sąrašo, pagrįsto kai kuriais parametrais.
1. Prieigos prie elemento kaina
Masyvo atveju, neatsižvelgiant į masyvo dydį, masyve prieiti prie elemento reikia pastovaus laiko. Masyve elementai saugomi gretimais, taigi, jei žinome pagrindinį elemento adresą, galime lengvai gauti bet kurio masyvo elemento adresą. Turime atlikti paprastą skaičiavimą, kad gautume bet kurio masyvo elemento adresą. Taigi, prieiga prie masyvo elemento yra O(1) laiko sudėtingumo požiūriu.
Susietame sąraše elementai nėra saugomi gretimais. Jį sudaro keli blokai, o kiekvienas blokas vaizduojamas kaip mazgas. Kiekvienas mazgas turi du laukus, ty vienas skirtas duomenų laukui, o kitas saugo kito mazgo adresą. Norėdami rasti bet kurį mazgą susietame sąraše, pirmiausia turime nustatyti pirmąjį mazgą, žinomą kaip pagrindinis mazgas. Jei turime rasti antrąjį mazgą sąraše, tai turime pereiti nuo pirmojo mazgo, o blogiausiu atveju, norėdami rasti paskutinį mazgą, pervažiuosime visus mazgus. Vidutinis elemento prieigos atvejis yra O(n).
Darome išvadą, kad prieigos prie masyvo elemento kaina yra mažesnė nei susieto sąrašo. Todėl, jei turime kokių nors reikalavimų pasiekti elementus, masyvas yra geresnis pasirinkimas.
2. Elemento įdėjimo kaina
Įterpinyje gali būti trys scenarijai:
Susieto sąrašo atveju, norėdami įterpti elementą susieto sąrašo pradžioje, sukursime naują mazgą, o pirmojo mazgo adresas pridedamas prie naujo mazgo. Tokiu būdu naujas mazgas tampa pirmuoju mazgu. Taigi laiko sudėtingumas nėra proporcingas sąrašo dydžiui. Laiko sudėtingumas būtų pastovus, ty O(1).
java pabėgimo simbolis
Jei masyvas nėra pilnas, mes galime tiesiogiai pridėti naują elementą per indeksą. Šiuo atveju laiko sudėtingumas būtų pastovus, ty O(1). Jei masyvas pilnas, pirmiausia turime nukopijuoti masyvą į kitą masyvą ir pridėti naują elementą. Šiuo atveju laiko sudėtingumas būtų O (n).
Norėdami įterpti elementą susieto sąrašo pabaigoje, turime pereiti visą sąrašą. Jei susietą sąrašą sudaro n elementų, laiko sudėtingumas būtų O(n).
Tarkime, kad norime įterpti elementą ties ithmasyvo padėtis; turime perkelti n/2 elementus į dešinę. Todėl laiko sudėtingumas yra proporcingas elementų skaičiui. Laiko sudėtingumas vidutiniu atveju būtų O(n).
javascript eilutės apkarpymas
Susieto sąrašo atveju turime pereiti į tą vietą, kurioje turime įterpti naują elementą. Nors mes neturime atlikti jokio perjungimo, bet turime važiuoti į n/2 padėtį. Laikas, kurio reikia, yra proporcingas n elementų skaičiui, o vidutinio atvejo laiko sudėtingumas būtų O(n).
Gautas susietų sąrašas yra toks:
Palyginti su susietu sąrašu, masyvą įdiegti lengva. Kuriant programą naudojant susietą sąrašą, programa yra labiau linkusi į klaidas, tokias kaip segmentavimo gedimas arba atminties nutekėjimas. Taigi, kuriant programą susietame sąraše reikia būti labai atsargiems.
Susietas sąrašas yra dinamiško dydžio, o masyvas yra statinis. Čia statiškumas nereiškia, kad negalime nuspręsti dydžio vykdymo metu, bet negalime jo pakeisti, kai yra nuspręstas dydis.
3. Reikalavimai atminčiai
Kaip masyvo elementai saugomi viename gretimame atminties bloke, taip masyvas yra fiksuoto dydžio. Tarkime, kad turime 7 dydžio masyvą, o masyvą sudaro 4 elementai, tada likusi erdvė nenaudojama. Atmintis, kurią užima 7 elementai:
Atminties vieta = 7 * 4 = 28 baitai
Kur 7 yra masyvo elementų skaičius, o 4 yra sveikojo skaičiaus tipo baitų skaičius.
Susieto sąrašo atveju nepanaudotos atminties nėra, tačiau papildomą atmintį užima rodyklės kintamieji. Jei duomenys yra sveikųjų skaičių, tai bendra atmintis, kurią užima vienas mazgas, yra 8 baitai, ty 4 baitai duomenims ir 4 baitai rodyklės kintamajam. Jei susietą sąrašą sudaro 4 elementai, susieto sąrašo užimta atminties vieta būtų tokia:
žiniatinklio tvarkyklės
Atminties vieta = 8 * 4 = 32 baitai
Susietas sąrašas būtų geresnis pasirinkimas, jei duomenų dalis yra didesnė. Tarkime, kad duomenys yra 16 baitų. Masyvo užimta atminties vieta būtų 16 * 7 = 112 baitų, o susietasis sąrašas užima 20 * 4 = 80, čia mes nurodėme 20 baitų kaip 16 baitų duomenų dydžiui ir 4 baitai žymeklio kintamajam. Jei pasirinktume didesnį duomenų dydį, susietas sąrašas sunaudotų mažiau atminties; kitu atveju tai priklauso nuo veiksnių, į kuriuos atsižvelgiame norėdami nustatyti dydį.
Pažvelkime į skirtumus tarp masyvo ir susieto sąrašo lentelės pavidalu.
| Masyvas | Susietas sąrašas |
|---|---|
| Masyvas yra panašaus tipo duomenų elementų rinkinys. | Susietas sąrašas yra objektų, žinomų kaip mazgas, rinkinys, kuriame mazgas susideda iš dviejų dalių, ty duomenų ir adreso. |
| Masyvo elementai saugomi gretimoje atminties vietoje. | Susieti sąrašo elementai gali būti saugomi bet kurioje atminties vietoje arba atsitiktinai. |
| Masyvas veikia su statine atmintimi. Čia statinė atmintis reiškia, kad atminties dydis yra fiksuotas ir jo negalima keisti vykdymo metu. | Susietų sąrašas veikia su dinamine atmintimi. Čia dinaminė atmintis reiškia, kad atminties dydis gali būti keičiamas vykdymo metu pagal mūsų reikalavimus. |
| Masyvo elementai nepriklauso vienas nuo kito. | Susieti sąrašo elementai priklauso vienas nuo kito. Kadangi kiekviename mazge yra kito mazgo adresas, todėl norėdami pasiekti kitą mazgą, turime pasiekti ankstesnį jo mazgą. |
| Masyvas užtrunka daugiau laiko atliekant bet kokią operaciją, pvz., įterpimą, ištrynimą ir kt. | Atliekant bet kokią operaciją, pvz., įterpimą, ištrynimą ir pan., susietas sąrašas užima mažiau laiko. |
| Prieiga prie bet kurio masyvo elemento yra greitesnė, nes masyvo elementą galima tiesiogiai pasiekti per indeksą. | Prieiga prie elemento susietame sąraše yra lėtesnė, nes jis pradeda eiti nuo pirmojo susieto sąrašo elemento. |
| Masyvo atveju atmintis paskirstoma kompiliavimo metu. | Susieto sąrašo atveju atmintis paskirstoma vykdymo metu. |
| Atminties panaudojimas masyve yra neefektyvus. Pavyzdžiui, jei masyvo dydis yra 6, o masyvą sudaro tik 3 elementai, likusi erdvė bus nenaudojama. | Atminties panaudojimas yra efektyvus susieto sąrašo atveju, nes atmintis gali būti paskirstyta arba išskirstyta vykdymo metu pagal mūsų reikalavimus. |