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