Masyvai ir susieti sąrašai
Masyvai yra dažniausiai naudojama duomenų struktūra kaupiant elementus. Daugumoje programavimo kalbų pateikiami metodai, kaip lengvai deklaruoti masyvus ir prieigos elementus masyvuose. Susietasis sąrašas, tiksliau atskirai susietas sąrašas, taip pat yra duomenų struktūra, kuri gali būti naudojama kaupiant elementus. Jį sudaro mazgų seka ir kiekvienas mazgas turi nuorodą į kitą sekos mazgą.
Parodytas 1 paveiksle, yra kodo dalis, paprastai naudojama masyvui deklaruoti ir priskirti reikšmes. 2 paveiksle pavaizduota, kaip masyvas atrodytų atmintyje.
Virš kodas apibrėžia masyvą, kuriame gali būti saugomi 5 sveikieji skaičiai, ir prie jų prieinama naudojant indeksus nuo 0 iki 4. Viena svarbi masyvo savybė yra ta, kad visas masyvas yra paskirstomas kaip vienas atminties blokas ir kiekvienas elementas gauna savo vietą masyve. Apibrėžus masyvą, jo dydis yra fiksuotas. Taigi, jei nesate tikras dėl masyvo dydžio kompiliavimo metu, turėtumėte apibrėžti pakankamai didelį masyvą, kad jis būtų saugus. Tačiau dažniausiai mes iš tikrųjų naudosime mažiau elementų, nei skyrėme. Taigi nemažai atminties iš tikrųjų švaistoma. Kita vertus, jei „pakankamai didelis masyvas“iš tikrųjų nėra pakankamai didelis, programa sugenda.
Susietas sąrašas atskirai paskirsto atmintį savo elementams savo atminties bloke ir bendra struktūra gaunama susiejus šiuos elementus kaip grandinės grandis. Kiekvienas susieto sąrašo elementas turi du laukus, kaip parodyta 3 paveiksle. Duomenų lauke laikomi faktiniai duomenys, o kitame lauke pateikiama nuoroda į kitą grandinės elementą. Pirmasis susieto sąrašo elementas saugomas kaip susieto sąrašo galva.
3 paveikslas: susieto sąrašo elementas
4 paveiksle pavaizduotas susietas sąrašas su trim elementais. Kiekvienas elementas saugo savo duomenis, o visi elementai, išskyrus paskutinį, saugo nuorodą į kitą elementą. Paskutinis elementas kitame lauke turi nulinę vertę. Bet kurį sąrašo elementą galima pasiekti pradedant nuo galvos ir sekant kitą rodyklę, kol pasieksite reikiamą elementą.
Nors masyvai ir susieti sąrašai yra panašūs ta prasme, kad abu jie naudojami elementų kolekcijai saugoti, jie skiriasi dėl strategijų, kurias jie naudoja atminties paskirstymui jos elementams. Masyvai visiems elementams paskirsto atmintį kaip vieną bloką, o masyvo dydis turi būti nustatytas vykdymo metu. Tai padarytų masyvus neefektyviais tais atvejais, kai jūs nežinote masyvo dydžio kompiliavimo metu. Kadangi susietas sąrašas atskirai paskirsto atmintį jo elementams, tai būtų daug efektyviau tais atvejais, kai kompiliavimo metu nežinote sąrašo dydžio. Deklaravimas ir prieiga prie susieto sąrašo elementų nebus tiesiai į priekį, palyginti su tuo, kaip jūs tiesiogiai pasiekiate masyvo elementus naudodami jo indeksus.
