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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

A doubly linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.
Двойно свързан списък, чиито елементи съдържат три полета: елемент със стойност от целочислен тип (integer), връзката към следващия елемент (node) и такава към предишния.

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

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


Номенклатура и имплементация[редактиране | редактиране на кода]

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

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

Основни алгоритми[редактиране | редактиране на кода]

Разглеждаме следните основни алгоритми написани на Ada:

Отворен свързан списък[редактиране | редактиране на кода]

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
}

Обхождане[редактиране | редактиране на кода]

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

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

node  := list.firstNode
 while node ≠ null
     <do something with node.data>
     node  := node.next

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

node  := list.lastNode
 while node ≠ null
     <do something with node.data>
     node  := node.prev

Вмъкване на елемент[редактиране | редактиране на кода]

Doubly linked list insert after.png

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

function insertAfter(List list, Node node, Node newNode)
     newNode.prev  := node
     newNode.next  := node.next
     if node.next == null
         list.lastNode  := newNode
     else
         node.next.prev  := newNode
     node.next  := newNode
function insertBefore(List list, Node node, Node newNode)
     newNode.prev  := node.prev
     newNode.next  := node
     if node.prev == null
         list.firstNode  := newNode
     else
         node.prev.next  := newNode
     node.prev  := newNode

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

function insertBeginning(List list, Node newNode)
     if list.firstNode == null
         list.firstNode  := newNode
         list.lastNode   := newNode
         newNode.prev  := null
         newNode.next  := null
     else
         insertBefore(list, list.firstNode, newNode)

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

function insertEnd(List list, Node newNode)
     if list.lastNode == null
         insertBeginning(list, newNode)
     else
         insertAfter(list, list.lastNode, newNode)

Премахване на елемент[редактиране | редактиране на кода]

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

function remove(List list, Node 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", защото в двойно свързаният списък можем просто да използваме "remove(node.prev)" или "remove(node.next)". Това също така ни гарантира, че елементът, който се отстранява съществува. Ако елементът не съществува в списъка, ще възникне грешка (“Exception”), която ще трябва да се обработи.

Кръгов двойно свързани списък[редактиране | редактиране на кода]

Обхождане[редактиране | редактиране на кода]

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

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

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

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

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

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

Вмъкване на елемент[редактиране | редактиране на кода]

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

function insertAfter(Node node, Node newNode)
     newNode.next  := node.next
     newNode.prev  := node
     node.next.prev  := newNode
     node.next       := newNode

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

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

function insertEnd(List list, Node node)
     if list.lastNode == null
         node.prev := node
         node.next := node
     else
         insertAfter(list.lastNode, node)
     list.lastNode := node

За да вмъкнем елемент в началото, можем да използваме "insertAfter(list.lastNode, node)".

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

function remove(List list, Node 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

Обобщение[редактиране | редактиране на кода]

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

Вижте също[редактиране | редактиране на кода]

Източници[редактиране | редактиране на кода]

Read Sort List

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Doubly_linked_list“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.