Разлика между масиви и свързани списъци

Масиви срещу свързани списъци

Масивите са най-често използваната структура на данни за съхраняване на колекция от елементи. Повечето езици за програмиране предоставят методи за лесно деклариране на масиви и достъп до елементи в масивите. Свързан списък, по-точно единично свързан списък, също е структура от данни, която може да се използва за съхраняване на колекция от елементи. Той е съставен от последователност от възли и всеки възел има препратка към следващия възел в последователността.

Показан на фигура 1, е парче код, който обикновено се използва за деклариране и присвояване на стойности на масив. Фигура 2 изобразява как би изглеждал масив в паметта.

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

Свързан списък разпределя паметта на елементите си отделно в своя собствен блок памет и цялостната структура се получава чрез свързване на тези елементи като връзки във верига. Всеки елемент в свързан списък има две полета, както е показано на фигура 3. Полето за данни съдържа действително съхранените данни, а следващото поле съдържа препратката към следващия елемент във веригата. Първият елемент от свързания списък се съхранява като глава на свързания списък.

Фигура 3: Елемент на свързан списък

Фигура 4 изобразява свързан списък с три елемента. Всеки елемент съхранява своите данни и всички елементи с изключение на последния съхранява препратка към следващия елемент. Последният елемент съдържа нулева стойност в следващото си поле. До всеки елемент в списъка можете да получите достъп, като започнете от главата и следвате следващия показалец, докато не срещнете необходимия елемент.

Въпреки че масивите и свързаните списъци са сходни по смисъла, че и двамата се използват за съхранение на колекция от елементи, те имат разлики поради стратегиите, които използват за разпределяне на паметта към неговите елементи. Масивите разпределят паметта на всичките й елементи като един блок и размерът на масива трябва да се определя по време на изпълнение. Това би направило масивите неефективни в ситуации, когато не знаете размера на масива по време на компилиране. Тъй като свързаният списък отделя памет за елементите си отделно, би било много ефикасно в ситуации, в които не знаете размера на списъка по време на компилиране. Декларацията и достъпът до елементи в свързан списък не биха били направо напред в сравнение с това как директно осъществявате достъп до елементи в масив, използвайки неговите индекси.