Atšķirība starp masīviem un saistītajiem sarakstiem

Masīvi un saistītie saraksti

Masīvi ir visbiežāk izmantotā datu struktūra, lai saglabātu elementu kolekciju. Lielākā daļa programmēšanas valodu nodrošina metodes masīvu un piekļuves elementu vieglai deklarēšanai masīvā. Saistītais saraksts, precīzāk atsevišķi savienots saraksts, ir arī datu struktūra, ko 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ā parādīts, kā masīvs izskatās atmiņā.

Virs kods definē masīvu, kurā var saglabāt 5 veselus skaitļus, un tiem var piekļūt, izmantojot indeksus no 0 līdz 4. Viena no svarīgām masīva īpašībām 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 sastādīšanas laikā neesat pārliecināts par masīva lielumu, jums jādefinē pietiekami liels masīvs, lai tas atrastos drošajā pusē. Bet lielāko daļu laika mēs faktiski izmantosim mazāk elementu, nekā esam iedalījuši. Tātad faktiski tiek tērēts ievērojams atmiņas apjoms. No otras puses, ja “pietiekami liels masīvs” faktiski nav pietiekami liels, programma sabojājas.

Saistītais saraksts piešķir atmiņu saviem 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 lauks satur faktiskos saglabātos datus, un nākamais lauks satur atsauci uz nākamo ķēdes elementu. Pirmais saistītā saraksta elements tiek saglabāts kā saistītā saraksta galviņa.

3. attēls. Saistītā saraksta elements

4. attēlā parādīts saistīts saraksts ar trim elementiem. Katrs elements saglabā savus datus un visus elementus, izņemot pēdējo, - atsauci uz nākamo elementu. Pēdējais elements nākamajā laukā tur nulles vērtību. Jebkuram saraksta elementam var piekļūt, sākot ar galvu un sekojot nākamajam rādītājam, līdz sasniedzat vajadzīgo elementu.

Pat ja masīvi un saistītie saraksti ir līdzīgi tādā nozīmē, ka abi no tiem tiek izmantoti elementu kolekcijas glabāšanai, tie rodas atšķirības, pateicoties stratēģijām, kuras viņi izmanto, lai piešķirtu atmiņu tā elementiem. Masīvi piešķir visiem tā elementiem atmiņu kā vienu bloku, un masīva lielums ir jānosaka izpildlaikā. Tas masīvu padarītu neefektīvu situācijās, kad kompilēšanas laikā jūs nezināt masīva lielumu. Tā kā saistītais saraksts piešķir atmiņu saviem 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ļuves elementi sasaistītajā sarakstā nebūtu tieša, salīdzinot ar to, kā jūs tieši piekļūstat masīva elementiem, izmantojot tā indeksus.