Масиви срещу свързани списъци
Масивите са най-често използваната структура от данни за съхраняване на колекция от елементи. Повечето езици за програмиране предоставят методи за лесно деклариране на масиви и елементи за достъп в масивите. Свързаният списък, по-точно единично свързан списък, също е структура от данни, която може да се използва за съхраняване на колекция от елементи. Състои се от последователност от възли и всеки възел има препратка към следващия възел в последователността.
Показаният на фигура 1 е парче код, обикновено използвано за деклариране и присвояване на стойности на масив. Фигура 2 изобразява как би изглеждал масив в паметта.
По-горе кодът дефинира масив, който може да съхранява 5 цели числа и до тях се осъществява достъп с помощта на индекси от 0 до 4. Едно важно свойство на масива е, че целият масив се разпределя като единичен блок памет и всеки елемент получава собствено пространство в масива. След като се дефинира масив, размерът му е фиксиран. Така че, ако не сте сигурни за размера на масива по време на компилиране, ще трябва да дефинирате достатъчно голям масив, за да бъде в безопасната страна. Но през повечето време всъщност ще използваме по-малък брой елементи, отколкото сме определили. Така че всъщност се губи значително количество памет. От друга страна, ако „достатъчно големият масив“всъщност не е достатъчно голям, програмата ще се срине.
Свързаният списък разпределя паметта към нейните елементи отделно в собствения си блок памет и цялостната структура се получава чрез свързване на тези елементи като връзки във верига. Всеки елемент в свързания списък има две полета, както е показано на Фигура 3. Полето с данни съдържа действително съхранените данни, а следващото поле съдържа препратката към следващия елемент във веригата. Първият елемент от свързания списък се съхранява като глава на свързания списък.
Фигура 3: Елемент на свързан списък
Фигура 4 изобразява свързан списък с три елемента. Всеки елемент съхранява своите данни, а всички елементи с изключение на последния съхраняват препратка към следващия елемент. Последният елемент съдържа нулева стойност в следващото си поле. Всеки елемент в списъка може да бъде достъпен, като се започне от главата и се следва следващият указател, докато се изпълни необходимия елемент.
Въпреки че масивите и свързаните списъци са сходни в смисъл, че и двата се използват за съхраняване на колекция от елементи, те пораждат разлики поради стратегиите, които използват за разпределяне на паметта към неговите елементи. Масивите разпределят паметта за всичките й елементи като единичен блок и размерът на масива трябва да бъде определен по време на изпълнение. Това би направило масивите неефективни в ситуации, когато не знаете размера на масива по време на компилация. Тъй като свързаният списък разпределя паметта по отделно за своите елементи, би бил много ефективен в ситуации, в които не знаете размера на списъка по време на компилиране. Декларирането и достъпът до елементи в свързан списък няма да бъдат директни в сравнение с начина, по който директно осъществявате достъп до елементи в масив, използвайки неговите индекси.
