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

2024 Автор: Mildred Bawerman | [email protected]. Последно модифициран: 2023-12-16 08:37

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

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

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

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

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

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

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

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

Каква е разликата между еднократно свързан списък и двойно свързан списък?

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