Arrays vs Linked Lists
Ang Array ay ang pinakakaraniwang ginagamit na istraktura ng data upang mag-imbak ng koleksyon ng mga elemento. Karamihan sa mga programming language ay nagbibigay ng mga paraan upang madaling magdeklara ng mga array at ma-access ang mga elemento sa mga array. Ang naka-link na listahan, na mas tiyak na isa-isang naka-link na listahan, ay isa ring istraktura ng data na maaaring magamit upang mag-imbak ng koleksyon ng mga elemento. Binubuo ito ng isang sequence ng mga node at ang bawat node ay may reference sa susunod na node sa sequence.
Ipinapakita sa figure 1, ay isang piraso ng code na karaniwang ginagamit upang magdeklara at magtalaga ng mga value sa isang array. Ang Figure 2 ay naglalarawan kung ano ang magiging hitsura ng isang array sa memorya.
Ang code sa itaas ay tumutukoy sa isang array na maaaring mag-imbak ng 5 integer at ina-access ang mga ito gamit ang mga indeks 0 hanggang 4. Ang isang mahalagang katangian ng isang array ay ang buong array ay inilalaan bilang isang bloke ng memorya at ang bawat elemento ay nakakakuha ng sarili nitong espasyo sa hanay. Kapag natukoy na ang isang array, naayos na ang laki nito. Kaya't kung hindi ka sigurado tungkol sa laki ng array sa oras ng pag-compile, kailangan mong tukuyin ang isang sapat na malaking array upang maging ligtas na bahagi. Ngunit, kadalasan ay talagang gagamit tayo ng mas kaunting bilang ng mga elemento kaysa sa inilaan natin. Kaya ang isang malaking halaga ng memorya ay talagang nasayang. Sa kabilang banda, kung ang “large enough array” ay hindi talaga sapat na laki, ang program ay mag-crash.
Ang isang naka-link na listahan ay naglalaan ng memorya sa mga elemento nito nang hiwalay sa sarili nitong bloke ng memorya at ang kabuuang istraktura ay nakukuha sa pamamagitan ng pag-link sa mga elementong ito bilang mga link sa isang chain. Ang bawat elemento sa isang naka-link na listahan ay may dalawang field tulad ng ipinapakita sa Figure 3. Ang data field ay nagtataglay ng aktwal na data na nakaimbak at ang susunod na field ay nagtataglay ng reference sa susunod na elemento sa chain. Ang unang elemento ng naka-link na listahan ay naka-store bilang pinuno ng naka-link na listahan.
| data | susunod |
Figure 3: Element of a Linked List
Ang Figure 4 ay naglalarawan ng isang naka-link na listahan na may tatlong elemento. Ang bawat elemento ay nag-iimbak ng data nito at lahat ng mga elemento maliban sa huling isa ay nag-iimbak ng isang reference sa susunod na elemento. Ang huling elemento ay mayroong null na halaga sa susunod nitong field. Maaaring ma-access ang anumang elemento sa listahan sa pamamagitan ng pagsisimula sa head at pagsunod sa susunod na pointer hanggang sa matugunan mo ang kinakailangang elemento.
Kahit na ang mga array at naka-link na listahan ay magkapareho sa kahulugan na pareho ang mga ito ay ginagamit upang mag-imbak ng koleksyon ng mga elemento, nagkakaroon sila ng mga pagkakaiba dahil sa mga diskarte na ginagamit nila upang maglaan ng memorya sa mga elemento nito. Ang mga array ay naglalaan ng memorya sa lahat ng mga elemento nito bilang isang bloke at ang laki ng array ay kailangang matukoy sa runtime. Gagawin nitong hindi mahusay ang mga array sa mga sitwasyon kung saan hindi mo alam ang laki ng array sa oras ng pag-compile. Dahil ang isang naka-link na listahan ay naglalaan ng memorya sa mga elemento nito nang hiwalay, magiging mahusay ito sa mga sitwasyon kung saan hindi mo alam ang laki ng listahan sa oras ng pag-compile. Ang deklarasyon at pag-access sa mga elemento sa isang naka-link na listahan ay hindi magiging straight forward kumpara sa kung paano mo direktang ina-access ang mga elemento sa isang array gamit ang mga indeks nito.
