Wie füge ich Knoten in eine einfach verknüpfte Python-Liste ein und gebe sie aus? (Codebeispiel)

Wie füge ich Knoten in eine einfach verknüpfte Python-Liste ein und gebe sie aus? Der folgende Artikel wird Ihnen helfen zu verstehen, was eine einfach verknüpfte Liste ist und wie Sie einige sehr grundlegende Operationen an einer einfach verknüpften Liste ausführen, wie z. B. Einfügen und Ausgabe. Ich hoffe, dass er für Sie hilfreich ist.

Was ist eine einfach verknüpfte Liste?

Bevor wir einfach verknüpfte Listen verstehen, müssen wir zunächst verstehen, was ein Knoten ist.

Knoten ist der Baustein der verknüpften Liste, der aus zwei Teilen besteht:

1. Datenteil: enthält früher Daten

2 zeigen Sie auf den nächsten Zeiger auf die Knotenposition.

In einer einfach verknüpften Liste enthält der Adressteil jedes Knotens Informationen über den Standort des nächsten Knotens. Dies bildet eine Reihe von Ketten oder Links. Der erste Knoten der verknüpften Liste wird vom Kopfzeiger verfolgt; der letzte Knoten zeigt auf None.

Sehen wir uns das folgende Diagramm an, um dies besser zu verstehen:

Hinweis: Im obigen Diagramm zeigt das letzte Element 1 auf None. Auch wenn diese Knoten zusammenhängend zueinander gezeichnet sind, können sie sich tatsächlich an zusammenhängenden Speicherorten befinden oder auch nicht.

Wie füge ich Knoten in eine einfach verknüpfte Liste ein und gebe sie aus?

1. Erstellen Sie eine einfach verknüpfte Liste

Zuerst müssen Sie einen Knoten erstellen, um eine einfach verknüpfte Liste zu erstellen. Dazu erstellen wir eine Node-Klasse mit den Eigenschaften data und nextNode. Wie bereits erwähnt, enthält das Datenattribut die Daten und nextNode zeigt einfach auf den nächsten Knoten in der verknüpften Liste. Wir legen den Standardwert für nextNode auf None fest. Dazu können Sie Getter- und Setter-Methoden verwenden.

Da nun die Node-Klasse erstellt wurde, ist es an der Zeit, die LinkedList-Klasse zu erstellen. Dies hat nur ein Attribut, Kopf. Standardmäßig zeigt dies auf „Keine“. Wenn der Header auf „None“ zeigt, bedeutet dies, dass die verknüpfte Liste leer ist. Um die Anzahl der Knoten in der verknüpften Liste zu verfolgen, können wir der LinkedList-Klasse ein Größenattribut hinzufügen und es standardmäßig auf 0 setzen.

2. Knoten einfügen

Dies ist die Methode der LinkedList-Klasse. Wir können an einer beliebigen Stelle in der verknüpften Liste einen neuen Knoten einfügen. Um die Codierung jedoch einfach und effizient zu halten, fügen wir neue Knoten immer am Anfang der verknüpften Liste hinzu. Mit anderen Worten: Der Kopf zeigt immer auf den zuletzt hinzugefügten Knoten .

Wenn wir am Ende der Liste einen neuen Knoten hinzufügen, müssen wir zusätzliche Arbeit leisten, um das Ende der Liste zu finden und ihn dann hinzuzufügen. Dies ist ein verschwenderischer Vorgang. Dies kann jedoch erreicht werden, wenn Sie einen anderen Zeiger beibehalten, nennen wir ihn Endzeiger, der auf den letzten Knoten zeigt.

Im Folgenden stellen wir die erstere Methode vor, also das Einfügen eines Knotens am Anfang der verknüpften Liste.

Angenommen, wir müssen 7 zur verknüpften Liste hinzufügen, müssen wir die folgenden Schritte ausführen:

● Erstellen Sie ein Knotenobjekt, wobei 7 Daten darstellt und die nächsten Knotenpunkte auf den Kopfknoten

●　Zeigen Sie den Kopfzeiger auf diesen neuen Knoten

Erhöhen Sie schließlich das Größenattribut um 1 und geben Sie True zurück, wenn das Einfügen erfolgreich ist , der Benutzer weiß, was passiert ist.

3. Ausgabeknoten

Dies ist die Methode der LinkedList-Klasse. Um die Daten in allen Knoten in der verknüpften Liste zu drucken, müssen wir jeweils einen Knoten durchlaufen und den Datenteil jedes Knotens drucken.

Implementierungscode:

class Node:
   def __init__(self,data,nextNode=None):
       self.data = data
       self.nextNode = nextNode
   def getData(self):
       return self.data
   def setData(self,val):
       self.data = val
   def getNextNode(self):
       return self.nextNode
   def setNextNode(self,val):
       self.nextNode = val
class LinkedList:
   def __init__(self,head = None):
       self.head = head
       self.size = 0
   def getSize(self):
       return self.size
   def addNode(self,data):
       newNode = Node(data,self.head)
       self.head = newNode
       self.size+=1
       return True
       
   def printNode(self):
       curr = self.head
       while curr:
           print(curr.data)
           curr = curr.getNextNode()
myList = LinkedList()
print("Inserting")
print(myList.addNode(5))
print(myList.addNode(15))
print(myList.addNode(25))
print("Printing")
myList.printNode()
print("Size")
print(myList.getSize())

Was sind die Vor- und Nachteile einfach verknüpfter Listen?

Vorteile:

● Es handelt sich um eine dynamische Datenstruktur, in der das Einfügen und Löschen einfach ist, weil wir es nicht brauchen um das Element zu verschieben. Es genügt, den nächsten Zeiger zu aktualisieren.

●Stapel- und Warteschlangendatenstrukturen können mithilfe verknüpfter Listen einfach implementiert werden.

Nachteile

●Der nächste Zeiger beansprucht zusätzlichen Speicher.

●Kann nicht zufällig aufgerufen werden. Die verknüpfte Liste muss von Anfang an durchlaufen werden, um einen bestimmten Knoten zu erreichen.

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Studium aller hilfreich sein. Weitere spannende Inhalte finden Sie in den entsprechenden Tutorial-Kolumnen auf der chinesischen PHP-Website! ! !

Das obige ist der detaillierte Inhalt vonWie füge ich Knoten in eine einfach verknüpfte Python-Liste ein und gebe sie aus? (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!