Dvojnásobně propojený seznam - Doubly linked list

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Double doubled list“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Leden 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v počítačová věda, a dvojnásobně propojený seznam je propojená datová struktura který se skládá ze sady postupně propojených evidence volala uzly. Každý uzel obsahuje tři pole: dvě pole odkazu (Reference k předchozímu a dalšímu uzlu v pořadí uzlů) a jedno datové pole. Počáteční a koncový uzel předchozí a další odkazy odkazují na nějaký druh zakončení, obvykle a sentinelový uzel nebo nula, pro usnadnění procházení seznamu. Pokud existuje pouze jeden ověřovací uzel, je seznam kruhově propojen prostřednictvím ověřovacího uzlu. Lze jej pojmout jako dva jednotlivě propojené seznamy vytvořeny ze stejných datových položek, ale v opačném pořadí.

Dvojitě propojený seznam, jehož uzly obsahují tři pole: odkaz na předchozí uzel, celočíselnou hodnotu a odkaz na další uzel.

Tyto dva uzlové odkazy umožňují procházení seznamu v obou směrech. Zatímco přidání nebo odebrání uzlu v dvojnásobně propojeném seznamu vyžaduje změnu více odkazů než stejné operace v jednotlivě propojeném seznamu, operace jsou jednodušší a potenciálně efektivnější (pro jiné uzly než první uzly), protože není třeba sledovat předchozí uzel během procházení nebo není třeba procházet seznamem, abyste našli předchozí uzel, aby bylo možné upravit jeho odkaz.

Názvosloví a provádění

První a poslední uzly dvojitě propojeného seznamu jsou okamžitě přístupné (tj. Přístupné bez procházení a obvykle se volají.) hlava a ocas) a proto umožňují procházení seznamu od začátku nebo na konci seznamu: např. procházení seznamu od začátku do konce nebo od konce do začátku při hledání seznamu pro uzel se specifickou hodnotou dat. Jakýkoli uzel dvojnásobně propojeného seznamu, jakmile je získán, lze použít k zahájení nového procházení seznamu v daném uzlu v obou směrech (směrem k začátku nebo konci).

Pole odkazů dvojitě propojeného uzlu seznamu se často nazývají další a předchozí nebo vpřed a dozadu. Odkazy uložené v polích odkazu jsou obvykle implementovány jako ukazatele, ale (stejně jako v jakékoli propojené datové struktuře) mohou být také adresami kompenzací nebo indexů do pole kde uzly žijí.

Základní algoritmy

Zvažte následující základní algoritmy napsané v Adě:

Otevírat dvojnásobně propojené seznamy

záznam DoublyLinkedNode {    další // Odkaz na další uzel    předchozí // Odkaz na předchozí uzel    data // Data nebo odkaz na data}

záznam DoublyLinkedList {     DoublyLinkedNode firstNode // ukazuje na první uzel seznamu     DoublyLinkedNode lastNode // ukazuje na poslední uzel seznamu}

Procházení seznamu

Procházení dvojnásobně propojeného seznamu může být v obou směrech. Ve skutečnosti se může směr procházení podle potřeby mnohokrát změnit. Traverz se často nazývá opakování, ale tato volba terminologie je nešťastná, protože opakování má dobře definovanou sémantiku (např. v matematice), která není analogická traverz.

Vpřed

node: = list.firstNodezatímco uzel ≠ nula     node: = node.next

Zpět

node: = list.lastNodezatímco uzel ≠ nula     node: = node.prev

Vkládání uzlu

Tyto symetrické funkce vloží uzel buď za nebo před daný uzel:

funkce insertAfter (Seznam seznam, Uzel uzel, Uzel newNode) newNode.prev: = uzel -li node.next == nula        newNode.next: = nula - (ne vždy nutné)        list.lastNode: = newNode jiný        newNode.next: = node.next node.next.prev: = newNode node.next: = newNode

funkce insertBefore (Seznam seznam, Uzel uzel, Uzel newNode) newNode.next: = uzel -li node.prev == nula        newNode.prev: = nula - (ne vždy nutné)        list.firstNode: = newNode jiný        newNode.prev: = node.prev node.prev.next: = newNode node.prev: = newNode

Také potřebujeme funkci pro vložení uzlu na začátek případně prázdného seznamu:

funkce insertBeginning (Seznam seznam, Uzel newNode) -li list.firstNode == nula        list.firstNode: = newNode list.lastNode: = newNode newNode.prev: = null newNode.next: = null jiný        insertBefore (list, list.firstNode, newNode)

Na konec se vloží symetrická funkce:

funkce insertEnd (Seznam seznam, Uzel newNode) -li list.lastNode == nula         insertBeginning (list, newNode) jiný         insertAfter (list, list.lastNode, newNode)

Odebrání uzlu

Odebrání uzlu je jednodušší než vložení, ale vyžaduje zvláštní zacházení, pokud je uzlem, který má být odstraněn firstNode nebo lastNode:

funkce odstranit(Seznam, Uzel uzel)    -li node.prev == nula        list.firstNode: = node.next jiný        node.prev.next: = node.next -li node.next == nula        list.lastNode: = node.prev jiný        node.next.prev: = node.prev

Drobným důsledkem výše uvedeného postupu je, že odstraněním posledního uzlu seznamu nastavíte obě firstNode a lastNode na nula, a tak správně zpracovává odebrání posledního uzlu ze seznamu s jedním prvkem. Všimněte si, že také nepotřebujeme samostatné metody „removeBefore“ nebo „removeAfter“, protože v dvojnásobně propojeném seznamu můžeme použít pouze „remove (node.prev)“ nebo „remove (node.next)“, kde jsou platné. To také předpokládá, že zaručeně existuje uzel, který se má odebrat. Pokud uzel v tomto seznamu neexistuje, bude vyžadováno určité zpracování chyb.

Kruhové dvojnásobně propojené seznamy

Procházení seznamu

Za předpokladu, že someNode je nějaký uzel v neprázdném seznamu, tento kód prochází tímto seznamem počínaje someNode (jakýkoli uzel bude dělat):

Vpřed

uzel: = someNodedělat    udělejte něco s node.value node: = node.nextzatímco uzel ≠ someNode

Zpět

uzel: = someNodedělat    udělejte něco s node.value node: = node.prevzatímco uzel ≠ someNode

Všimněte si odložení testu na konec smyčky. To je důležité pro případ, kdy seznam obsahuje pouze jeden uzel someNode.

Vkládání uzlu

Tato jednoduchá funkce vloží uzel do dvojitě spojeného kruhového spojeného seznamu za daným prvkem:

funkce insertAfter (Uzel uzel, Uzel newNode) newNode.next: = node.next newNode.prev: = uzel node.next.prev: = newNode node.next: = newNode

Chcete-li provést „insertBefore“, můžeme jednoduše „insertAfter (node.prev, newNode)“.

Vložení prvku do případně prázdného seznamu vyžaduje speciální funkci:

funkce insertEnd (Seznam seznam, Uzel uzel) -li list.lastNode == nula        node.prev: = uzel node.next: = uzel jiný        insertAfter (list.lastNode, node) list.lastNode: = uzel

Vložit na začátek jednoduše „insertAfter (list.lastNode, node)“.

Nakonec odebrání uzlu musí řešit případ, kdy se seznam vyprázdní:

funkce odstranit(Seznam seznam, Uzel uzel); -li node.next == seznam uzlů.lastNode: = nula    jiný        node.next.prev: = node.prev node.prev.next: = node.next -li node == list.lastNode list.lastNode: = node.prev; zničit uzel

Odstranění uzlu

Stejně jako v seznamech s dvojitým propojením lze „removeAfter“ a „removeBefore“ implementovat pomocí „remove (list, node.prev)“ a „remove (list, node.next)“.

Pokročilé koncepty

Asymetrický dvojnásobně propojený seznam

Asymetrický dvojnásobně propojený seznam je někde mezi jednotlivě propojeným seznamem a běžným dvojnásobně spojeným seznamem. Sdílí některé funkce s jednotlivě propojeným seznamem (jednosměrný průchod) a dalšími ze dvojnásobně propojeného seznamu (snadná modifikace)

Je to seznam, kde je každý uzel předchozí odkaz neodkazuje na předchozí uzel, ale na odkaz sám k sobě. I když to dělá malý rozdíl mezi uzly (pouze ukazuje na posun v předchozím uzlu), mění se hlava seznamu: Umožňuje prvnímu uzlu upravit firstNode snadno propojit.^[1][2]

Pokud je uzel v seznamu, je předchozí odkaz není nikdy null.

Vkládání uzlu

Chcete-li vložit uzel před jiný, změníme odkaz, který ukázal na starý uzel, pomocí předchozí odkaz; potom nastavte nové uzly další odkaz, který ukazuje na starý uzel, a změnit jeho uzel předchozí odpovídajícím způsobem.

funkce insertBefore (Uzel uzel, Uzel newNode) -li node.prev == nula        chyba „Uzel není v seznamu“ newNode.prev: = node.prev atAddress (newNode.prev): = newNode newNode.next: = uzel node.prev = addressOf (newNode.next)

funkce insertAfter (Uzel uzel, Uzel newNode) newNode.next: = node.next -li newNode.next! = nula        newNode.next.prev = addressOf (newNode.next) node.next: = newNode newNode.prev: = addressOf (node.next)

Odstranění uzlu

Chcete-li odstranit uzel, jednoduše upravíme odkaz, na který ukazuje předchozí, bez ohledu na to, zda byl uzel prvním ze seznamu.

funkce odstranit(Uzel uzel) atAddress (node.prev): = node.next -li node.next! = nula        node.next.prev = node.prev zničit uzel

Viz také

• Propojený seznam XOR
• SLIP (programovací jazyk)

Reference