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

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

Двойно свързан списък, чиито елементи съдържат три полета: елемент със стойност от целочислен тип (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

Вмъкване на елемент

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

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 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​