Masīvi vs saistītie saraksti
Masīvi ir visbiežāk izmantotā datu struktūra elementu kolekcijas glabāšanai. Lielākā daļa programmēšanas valodu nodrošina metodes, kā viegli deklarēt masīvus un piekļūt masīvos esošajiem elementiem. Saistītais saraksts, precīzāk atsevišķi piesaistītais saraksts, ir arī datu struktūra, kuru var izmantot, lai saglabātu elementu kolekciju. To veido mezglu secība, un katram mezglam ir atsauce uz nākamo mezglu secībā.
Parādīts 1. attēlā ir koda gabals, ko parasti izmanto masīva vērtību deklarēšanai un piešķiršanai. 2. attēlā attēlots, kā masīvs izskatītos atmiņā.
Virs koda ir definēts masīvs, kurā var uzglabāt 5 veselus skaitļus, un tiem piekļūst, izmantojot indeksus no 0 līdz 4. Viena svarīga masīva īpašība ir tā, ka viss masīvs tiek piešķirts kā viens atmiņas bloks, un katrs elements masīvā iegūst savu vietu. Kad masīvs ir definēts, tā lielums tiek fiksēts. Tātad, ja kompilācijas laikā neesat pārliecināts par masīva lielumu, jums vajadzētu definēt pietiekami lielu masīvu, lai tas būtu drošībā. Bet lielāko daļu laika mēs faktiski izmantosim mazāk elementu, nekā esam piešķīruši. Tātad ievērojams daudzums atmiņas faktiski tiek izniekots. No otras puses, ja “pietiekami liels masīvs” patiesībā nav pietiekami liels, programma avarētu.
Saistīts saraksts piešķir atmiņu tā elementiem atsevišķi savā atmiņas blokā, un kopējo struktūru iegūst, sasaistot šos elementus kā saites ķēdē. Katram saistītā saraksta elementam ir divi lauki, kā parādīts 3. attēlā. Datu laukā glabājas faktiski saglabātie dati, un nākamajā laukā ir atsauce uz nākamo ķēdes elementu. Pirmais saistītā saraksta elements tiek saglabāts kā saistītā saraksta vadītājs.
3. attēls: Saistītā saraksta elements
4. attēlā ir parādīts saistīts elements ar trim elementiem. Katrs elements saglabā savus datus, un visi elementi, izņemot pēdējo, saglabā atsauci uz nākamo elementu. Pēdējais elements nākamajā laukā saglabā nulles vērtību. Jebkuram saraksta elementam var piekļūt, sākot ar galvu un sekojot nākamajam rādītājam, līdz tiek sasniegts nepieciešamais elements.
Kaut arī masīvi un saistītie saraksti ir līdzīgi tādā nozīmē, ka tos abus izmanto elementu kolekcijas glabāšanai, tiem rodas atšķirības, pateicoties stratēģijām, kuras viņi izmanto, lai piešķirtu atmiņu tā elementiem. Masīvi piešķir atmiņu visiem tās elementiem kā vienu bloku, un masīva lielums jānosaka izpildlaikā. Tas padarītu masīvus neefektīvus situācijās, kad jūs nezināt masīva lielumu sastādīšanas laikā. Tā kā piesaistītais saraksts atdala atmiņu tā elementiem atsevišķi, tas būtu daudz efektīvāk situācijās, kad sastādīšanas laikā nezināt saraksta lielumu. Deklarēšana un piekļuve saistītā saraksta elementiem nebūtu tieša salīdzinājumā ar to, kā jūs tieši piekļūstat masīva elementiem, izmantojot tā indeksus.
