Masyvai vs susietieji sąrašai
Masyvai yra dažniausiai naudojama duomenų struktūra elementų rinkiniui saugoti. Dauguma programavimo kalbų pateikia metodus, kaip lengvai deklaruoti masyvus ir pasiekti masyvo elementus. Susietas sąrašas, tiksliau atskirai susietas sąrašas, taip pat yra duomenų struktūra, kurią galima naudoti elementų rinkiniui saugoti. Jį sudaro mazgų seka ir kiekvienas mazgas turi nuorodą į kitą sekos mazgą.
Pavaizduota 1 paveiksle, yra kodo dalis, paprastai naudojama masyvo reikšmėms deklaruoti ir priskirti. 2 paveiksle pavaizduota, kaip masyvas atrodytų atmintyje.
Aukščiau pateiktas kodas apibrėžia masyvą, kuriame gali būti saugomi 5 sveikieji skaičiai ir jie pasiekiami 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 erdvę. masyve. Kai masyvas yra apibrėžtas, jo dydis yra fiksuotas. Taigi, jei nesate tikri dėl masyvo dydžio kompiliavimo metu, turėtumėte apibrėžti pakankamai didelį masyvą, kad būtumėte saugioje pusėje. Tačiau dažniausiai mes iš tikrųjų naudosime mažiau elementų, nei skyrėme. Taigi iš tikrųjų eikvojama nemažai atminties. Kita vertus, jei „pakankamai didelis masyvas“iš tikrųjų nėra pakankamai didelis, programa sugenda.
Susietasis sąrašas priskiria atmintį savo elementams atskirai savo atminties bloke, o bendra struktūra gaunama susiejant šiuos elementus kaip grandines grandinėje. Kiekvienas susieto sąrašo elementas turi du laukus, kaip parodyta 3 paveiksle. Duomenų lauke saugomi tikrieji saugomi duomenys, o kitame lauke yra nuoroda į kitą grandinės elementą. Pirmasis susieto sąrašo elementas išsaugomas kaip susieto sąrašo antraštė.
| duomenys | kitas |
3 pav. Susieto sąrašo elementas
4 paveiksle pavaizduotas susietas sąrašas su trimis elementais. Kiekvienas elementas saugo savo duomenis, o visi elementai, išskyrus paskutinį, saugo nuorodą į kitą elementą. Paskutinis elementas kitame lauke turi nulinę reikšmę. Bet kurį sąrašo elementą galima pasiekti pradedant nuo antraštės ir sekant kitą žymeklį, kol pasieksite reikiamą elementą.
Nors masyvai ir susieti sąrašai yra panašūs ta prasme, kad abu naudojami elementų rinkiniui saugoti, jie skiriasi dėl strategijų, kurias jie naudoja skirstydami atmintį elementams. Masyvai priskiria atmintį visiems savo elementams kaip vieną bloką, o masyvo dydis turi būti nustatytas vykdymo metu. Dėl to masyvai taptų neveiksmingi tais atvejais, kai kompiliavimo metu nežinote masyvo dydžio. Kadangi susietas sąrašas atmintį savo elementams paskiria atskirai, jis būtų labai efektyvus tais atvejais, kai kompiliavimo metu nežinote sąrašo dydžio. Deklaravimas ir prieiga prie susieto sąrašo elementų nebūtų paprasta, palyginti su tuo, kaip tiesiogiai pasiekiate masyvo elementus naudodami jo indeksus.
