Топ-100
Back

ⓘ Двойносвързан списък. В компютърните науки двойно свързаният списък е свързана структура от данни, състояща се от множество последователно свързани елементи. Вс ..




                                     

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

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

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

Тази концепция е и в основата на техниката за запаметяване в мнемоничната свързваща система наричана още "свързващ метод".

                                     

1. Номенклатура и имплементация

Първият и последният елемент на двойно свързания списък, наричани съответно "head" глава и "tail" опашка, могат да бъдат достигнати незабавно т.е. без обхождане на списъка. Те позволяват обхождането на списъка от началото или края – например обхождане на списъка от началото към края или от края към началото за намиране на елемент с конкретна стойност. След като намерим конкретен елемент с дадена стойност, той може да се използва като начало за ново обхождане на списъка в двете посоки – към началото на списъка или към неговия край.

Полетата, представляващи връзките към съседните елементи в двойно свързания списък, често се наричат next и previous или forward и backward, съответно предходен и следващ. Указателите, които държат съответните полета, най-често са представени катоpointer, но могат също така да бъдат и адресни отклонения или индекси в масив, в който съществуват елементите, към които се сочи.

                                     

2.1. Основни алгоритми Отворен свързан списък

record DoublyLinkedNode { prev // A reference to the previous node next // A reference to the next node data // Data or a reference to data } record DoublyLinkedList { DoublyLinkedNode firstNode // points to first node of list DoublyLinkedNode lastNode // points to last node of list }
                                     

2.2. Основни алгоритми Обхождане

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

Обхождане отпред назад с отправна точка първи елемент:

node:= list.firstNode while node ≠ null node:= node.next

Обхождане отзад напред с отправна точка последен елемент:

node:= list.lastNode while node ≠ null node:= node.prev
                                     

2.3. Основни алгоритми Вмъкване на елемент

За вмъкването на елемент преди или след конкретен елемент се използват следните симетрични функции:

function insertAfter newNode.prev:= node newNode.next:= node.next if node.next == null list.lastNode:= newNode else node.next.prev:= newNode node.next:= newNode function insertBefore newNode.prev:= node.prev newNode.next:= node if node.prev == null list.firstNode:= newNode else node.prev.next:= newNode node.prev:= newNode

За вмъкването на елемент в началото на празен списък се използва функцията:

function insertBeginningList list, Node newNode if list.firstNode == null list.firstNode:= newNode list.lastNode:= newNode newNode.prev:= null newNode.next:= null else insertBefore

За вмъкването на елемент в края на списъка се използва симетричната функция:

function insertEndList list, Node newNode if list.lastNode == null insertBeginninglist, newNode else insertAfter
                                     

2.4. Основни алгоритми Премахване на елемент

Премахванто на елемент node е по-лесно от вмъкването му, но изисква особен подход, ако елементът за премахване е първият firstNode или последният lastnNode:

function removeList list, node if node.prev == null list.firstNode:= node.next else node.prev.next:= node.next if node.next == null list.lastNode:= node.prev else node.next.prev:= node.prev

Нежелан ефект от предходния пример е довеждането до стойност null на firstNode и lastNode. Ако се вгледаме по-внимателно, можем да забележим, че няма нужда от отделни функции removeBefore и removeAfter, защото в двойно свързаният списък може да се използва removenode.prev или removenode.next. Това също така гарантира, че елементът, който се отстранява съществува. Ако елементът не съществува в списъка, ще възникне грешка Exception, която ще трябва да се обработи.

                                     

2.5. Основни алгоритми Обхождане

Ако се приеме, че someNode е елемент в списък който не е празен, следващият пример ще обходи списъка, използвайки someNode като отправна точка, която може да бъде който и да е елемент от списъка.

Обхождане отпред назад с отправна точка първи елемент:

node:= someNode do something with node.value node:= node.next while node ≠ someNode

Обхождане отзад напред с отправна точка последен елемент:

node:= someNode do something with node.value node:= node.prev while node ≠ someNode

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

                                     

2.6. Основни алгоритми Вмъкване на елемент

Вмъкването на елемент след даден елемент в кръговия двойно свързан списък става чрез следната функция:

function insertAfterNode node, Node newNode newNode.next:= node.next newNode.prev:= node node.next.prev:= newNode node.next:= newNode

За да вмъкнем елемент преди някой друг insertBefore, можем отново да използваме функцията insertAfternode.prev, newNode.

Вмъкване на елемент в празен списък изисква използването на по-сложна функция:

function insertEndList list, node if list.lastNode == null node.prev:= node node.next:= node else insertAfterlist.lastNode, node list.lastNode:= node

За да вмъкнем елемент в началото, можем да използваме insertAfterlist.lastNode, node.

Премахването на елемент node става чрез следната функция, която се съобразява с това, че елементите в списъка намаляват:

function removeList list, node if node.next == node list.lastNode:= null else node.next.prev:= node.prev node.prev.next:= node.next if node == list.lastNode list.lastNode:= node.prev; destroy node


                                     

3. Обобщение

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

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