Skirtumas tarp masyvų ir susietų sąrašų

Masyvai vs susieti sąrašai

Masyvai yra dažniausiai naudojama duomenų struktūra elementų kolekcijai saugoti. Daugelyje programavimo kalbų pateikiami būdai, kaip lengvai deklaruoti masyvus ir prieigos elementus masyvuose. Susietas sąrašas, tiksliau atskirai susietas sąrašas, taip pat yra duomenų struktūra, kurią galima naudoti elementų kolekcijai laikyti. Jis sudarytas iš mazgų sekos ir kiekvienas mazgas nurodo kitą sekos mazgą.

Parodytas 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 apibūdina 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 tai, kad visas masyvas yra paskirstomas kaip vienas atminties blokas ir kiekvienas elementas užima savo vietą masyve. Kai masyvas yra apibrėžtas, jo dydis yra fiksuotas. Taigi, jei nesate tikri dėl masyvo dydžio sudarydami, turėtumėte apibrėžti pakankamai didelį masyvą, kad jis būtų saugioje pusėje. Tačiau dažniausiai mes naudojame mažiau elementų, nei skyrėme. Taigi iš tiesų iššvaistoma nemažai atminties. Kita vertus, jei „pakankamai didelis masyvas“ iš tikrųjų nėra pakankamai didelis, programa sudužtų.

Susietas sąrašas atmintį atskiriems elementams skiria atskirai savo atminties bloke, o bendra struktūra gaunama susiejant šiuos elementus kaip grandinės grandis. Kiekvienas susieto sąrašo elementas turi du laukus, kaip parodyta 3 paveiksle. Duomenų lauke pateikiami faktiniai saugomi duomenys, o kitame lauke yra 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 trimis elementais. Kiekvienas elementas saugo savo duomenis ir visus elementus, išskyrus paskutinįjį, saugo nuorodą į kitą elementą. Paskutinis elementas kitame lauke turi nulinę vertę. Bet kurį sąrašo elementą galima pasiekti pradedant nuo galvos ir sekant kitu žymekliu, kol pasieksite reikiamą elementą.

Nors masyvai ir susieti sąrašai yra panašūs ta prasme, kad abu jie yra naudojami elementų kolekcijai saugoti, jie patiria skirtumų dėl strategijų, kurias jie naudoja atminties paskirstymui jos elementams. Masyvai visiems savo elementams atmintį skiria kaip vieną bloką, o masyvo dydis turi būti nustatytas vykdant. Tai padarytų masyvus neveiksmingus tais atvejais, kai kompiliavimo metu nežinote masyvo dydžio. Kadangi susietas sąrašas atmintį paskirsto atskirai jo elementams, jis būtų daug efektyvesnis tais atvejais, kai sudarymo metu nežinote sąrašo dydžio. Deklaravimas ir prieiga prie elementų susietame sąraše nebūtų tiesūs, palyginti su tuo, kaip jūs tiesiogiai pasiekiate masyvo elementus naudodami jo indeksus.