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

Единично свързан списък срещу двойно свързан списък

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

Единично свързан списък

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

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

Двойно свързан списък

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

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

Каква е разликата между Singly Linked List и Doubly Linked List?

Всеки елемент в отделно свързания списък съдържа препратка към следващия елемент в списъка, докато всеки елемент в двойно свързания списък съдържа препратки към следващия елемент, както и към предишния елемент в списъка. Двойно свързаните списъци изискват повече място за всеки елемент от списъка, а елементарните операции като вмъкване и изтриване са по-сложни, тъй като трябва да се справят с две препратки. Но двойните списъци с връзки позволяват по-лесна манипулация, тъй като позволява преминаване на списъка в посоки напред и назад.