Python - Verknüpfte Listen

Eine verknüpfte Liste ist eine Folge von Datenelementen, die über Verknüpfungen miteinander verbunden sind. Jedes Datenelement enthält eine Verbindung zu einem anderen Datenelement in Form eines Zeigers. Python hat keine verknüpften Listen in seiner Standardbibliothek. Wir implementieren das Konzept der verknüpften Listen unter Verwendung des Konzepts der Knoten, wie im vorherigen Kapitel erläutert. Wir haben bereits gesehen, wie wir eine Knotenklasse erstellen und wie die Elemente eines Knotens durchlaufen werden. In diesem Kapitel werden wir die Arten von verknüpften Listen untersuchen, die als einfach verknüpfte Listen bezeichnet werden. In dieser Art von Datenstruktur gibt es nur eine Verbindung zwischen zwei beliebigen Datenelementen. Wir erstellen eine solche Liste und erstellen zusätzliche Methoden zum Einfügen, Aktualisieren und Entfernen von Elementen aus der Liste.

Erstellung einer verknüpften Liste

Eine verknüpfte Liste wird mithilfe der Knotenklasse erstellt, die wir im letzten Kapitel untersucht haben. Wir erstellen ein Node-Objekt und erstellen eine weitere Klasse, um dieses Ode-Objekt zu verwenden. Wir übergeben die entsprechenden Werte durch das Knotenobjekt, um auf die nächsten Datenelemente zu verweisen. Das folgende Programm erstellt die verknüpfte Liste mit drei Datenelementen. Im nächsten Abschnitt erfahren Sie, wie Sie die verknüpfte Liste durchlaufen.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Durchlaufen einer verknüpften Liste

Einfach verknüpfte Listen können ab dem ersten Datenelement nur in Vorwärtsrichtung durchlaufen werden. Wir drucken einfach den Wert des nächsten Datenelements, indem wir den Zeiger des nächsten Knotens auf das aktuelle Datenelement setzen.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

Mon
Tue
Wed

Einfügen in eine verknüpfte Liste

Das Einfügen eines Elements in die verknüpfte Liste umfasst das Neuzuweisen der Zeiger von den vorhandenen Knoten zu dem neu eingefügten Knoten. Abhängig davon, ob das neue Datenelement am Anfang oder in der Mitte oder am Ende der verknüpften Liste eingefügt wird, haben wir die folgenden Szenarien.

Einfügen am Anfang der verknüpften Liste

Dies beinhaltet das Zeigen des nächsten Zeigers des neuen Datenknotens auf den aktuellen Kopf der verknüpften Liste. So wird der aktuelle Kopf der verknüpften Liste zum zweiten Datenelement und der neue Knoten zum Kopf der verknüpften Liste.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtBegining("Sun")

list.listprint()

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

Sun
Mon
Tue
Wed

Einfügen am Ende der verknüpften Liste

Dies beinhaltet das Zeigen des nächsten Zeigers des aktuell letzten Knotens der verknüpften Liste auf den neuen Datenknoten. Der aktuelle letzte Knoten der verknüpften Liste wird also zum vorletzten Datenknoten und der neue Knoten zum letzten Knoten der verknüpften Liste.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add newnode
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

list.headval.nextval = e2
e2.nextval = e3

list.AtEnd("Thu")

list.listprint()

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

Mon
Tue
Wed
Thu

Einfügen zwischen zwei Datenknoten

Dies beinhaltet das Chagen des Zeigers eines bestimmten Knotens, um auf den neuen Knoten zu zeigen. Dies ist möglich, indem sowohl der neue Knoten als auch der vorhandene Knoten übergeben werden, wonach der neue Knoten eingefügt wird. Also definieren wir eine zusätzliche Klasse, die den nächsten Zeiger des neuen Knotens in den nächsten Zeiger des mittleren Knotens ändert. Weisen Sie dann den neuen Knoten dem nächsten Zeiger des mittleren Knotens zu.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

# Function to add node
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

# Print the linked list
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval


list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

list.headval.nextval = e2
e2.nextval = e3

list.Inbetween(list.headval.nextval,"Fri")

list.listprint()

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

Mon
Tue
Fri
Thu

Entfernen eines Elements aus einer Liked List

Wir können einen vorhandenen Knoten mit dem Schlüssel für diesen Knoten entfernen. Im folgenden Programm suchen wir den vorherigen Knoten des Knotens, der gelöscht werden soll. Zeigen Sie dann mit dem nächsten Zeiger dieses Knotens auf den nächsten Knoten des zu löschenden Knotens.

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

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

    def Atbegining(self, data_in):
        NewNode = Node(data_in)
        NewNode.next = self.head
        self.head = NewNode
		
# Function to remove node
    def RemoveNode(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None

    def LListprint(self):
        printval = self.head
        while (printval):
            print(printval.data),
            printval = printval.next


llist = SLinkedList()
llist.Atbegining("Mon")
llist.Atbegining("Tue")
llist.Atbegining("Wed")
llist.Atbegining("Thu")
llist.RemoveNode("Tue")
llist.LListprint()

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

Thu
Wed
Mon