Erstellen Sie eine doppelt verknüpfte Liste in Python

In diesem Artikel wird das Erstellen einer doppelt verknüpften Liste mit der Programmiersprache Python demonstriert.

Erstellen Sie eine doppelt verknüpfte Liste in Python

Eine doppelt verknüpfte Liste bezieht sich auf eine verknüpfte Datenstruktur, die aus einer sequentiell verknüpften Menge von Datensätzen besteht, die als Knoten bezeichnet werden. Jeder Knoten enthält einen vorherigen Zeiger, einen nächsten Zeiger und ein Datenfeld.

Zurück- und Weiter-Zeiger zeigen auf den vorherigen und den nächsten Knoten. Der vorherige Zeiger auf dem ersten Knoten und der nächste Zeiger auf dem letzten Knoten zeigt auf None.

Wir können einen neuen Knoten vor und nach einem gegebenen Knoten in die doppelt verkettete Liste einfügen. Außerdem können wir die doppelt verknüpfte Liste sowohl vorwärts als auch rückwärts durchlaufen.

Jeder doppelt verknüpfte Listenknoten benötigt jedoch zusätzlichen Platz für einen vorherigen Zeiger.

Eine Knotenklasse wird wie folgt erstellt. Zeiger und Datenwerte sind standardmäßig None.

class Node:
    def __init__(self, next=None, previous=None, data=None):
        self.next = next
        self.previous = previous
        self.data = data

Dann wird die Klasse erstellt, die für die doppelt verknüpfte Liste verwendet wird. Der self.head gibt den Kopf der Liste an und ist zunächst None.

Wir werden die Funktion add_to_end verwenden, um einen neuen Knoten am Ende der doppelt verknüpften Liste hinzuzufügen. Zuerst erstellen wir eine Node-Klasseninstanz mit der Variablen new_node.

Da der new_node der letzte Wert der Liste sein wird, setzen wir seinen nächsten Zeiger auf None. Wir definieren die Variable last, um den Knoten zu finden, zu dem wir den new_node hinzufügen.

Erstens ist diese Variable der Kopf der doppelt verknüpften Liste (für den ersten hinzugefügten Knoten ist dieser Kopf None).

Wir prüfen, ob der self.head im if-Block None ist. Wenn dies der Fall ist, gibt es keine Knoten in der Liste, und der Kopf der Liste ist jetzt der neu hinzugefügte Knoten.

Im while-Block prüfen wir den next-Zeiger der last-Variablen, um den letzten Wert der Liste zu finden. Wir ersetzen die last-Variable durch last.next, bis wir None erhalten.

Wir beenden die Liste, wenn wir den Knoten finden, dessen last.next-Wert None ist.

Wir setzen den next-Zeiger des letzten Knotenwerts, den wir gefunden haben, auf den new_node. Abschließend setzen wir den vorherigen Zeiger der new_node Variable auf die last Variable.

Somit wird der Knoten new_node am Ende der doppelt verketteten Liste hinzugefügt.

Siehe Code unten.

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = None
        last = self.head

        if self.head is None:
            new_node.previous = None
            self.head = new_node
            return

        while last.next is not None:
            last = last.next

        last.next = new_node
        new_node.previous = last

Wir können die Funktion add_to_beginning verwenden, um einen Knoten am Anfang der doppelt verketteten Liste hinzuzufügen. Dieser Vorgang ist einfacher.

Zuerst setzen wir den next-Zeiger der new_node-Variablen auf self.head und den previous-Zeiger auf None. Der Kopfwert, der erste Wert der alten Liste, wird also zum nächsten Wert, auf den new_node zeigt.

Im if-Block prüfen wir, ob der self.head-Wert None ist, wenn die Liste leer ist. Wenn dieser Wert definiert ist oder es einen Knoten gibt, der dem Kopf entspricht, ändern wir den vorherigen Zeiger dieses Knotens auf neuer_Knoten.

Zum Schluss ändern wir self.head in new_node. Somit wird der new_node am Anfang der doppelt verketteten Liste hinzugefügt.

Sehen Sie sich die Code-Demonstration unten an.

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, new_node):
        # previous function
        pass

    def add_to_beginning(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = self.head
        new_node.previous = None

        if self.head is not None:
            self.head.previous = new_node

        self.head = new_node

Im Beispiel unten wird zuerst die Variable double_linked_list erstellt. Diese Variable ist eine Instanz der DoubleLinkedList-Klasse.

Dann fügen wir 1 und 3 am Ende der Liste bzw. 5 am Anfang hinzu. Der Endzustand der Liste ist 5 -> 1 -> 3 -> None.

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)