Wie finde und lösche ich Knoten in einer einfach verknüpften Python-Liste?

Im vorherigen Artikel [Wie füge ich Knoten in eine einfach verknüpfte Python-Liste ein und gebe sie aus? ] stellt Ihnen vor, was eine einfach verknüpfte Liste ist und wie Sie Knoten hinzufügen und alle Knoten ausgeben. Im folgenden Artikel erfahren Sie, wie Sie Knoten finden und löschen. Ich hoffe, dass er für Sie hilfreich ist.

Wie finde ich einen Knoten aus einer einfach verknüpften Liste?

Wie bei den meisten Datenstrukturen besteht die einzige Möglichkeit herauszufinden, ob ein Element existiert, darin, die gesamte verknüpfte Liste zu durchlaufen. Beachten Sie, dass wir die binäre Suche verwenden können, wenn die verknüpfte Liste sortiert ist. Aber hier betrachten wir eine unsortierte verknüpfte Liste.

Wie es funktioniert: Der Benutzer gibt das zu findende Knotenelement an. Wenn wir das Element finden, geben wir true zurück, andernfalls können Sie auch einen Zähler verwenden und den Index des Elements zurückgeben (falls vorhanden).

Algorithmus

1. Stellen Sie den Zeiger auf den Kopf

2. Vergleichen Sie curr.data mit dem Eingabewert:

●　Wenn gleich, gebe True zurück

●● Ansonsten gehe zum nächsten Zeiger

3 Wiederholen Sie die Schritte 1-2, bis das Element gefunden wird oder das Ende der verknüpften Liste erreicht ist

Implementierungscode:

def findNode(self,value):
       curr = self.head
       while curr:
           if curr.getData() == value:
               return True
           curr = curr.getNextNode()
       return False

Wie lösche ich einen Knoten aus einer einfach verknüpften Liste?

Aus dem obigen Beispiel wissen wir, wie man Knoten findet, und können es dann zum Löschen von Knoten verwenden. Wir können einen Wert vom Benutzer erhalten, das Element in der verknüpften Liste finden und es entfernen, falls es vorhanden ist.

Hinweis: Es ist sehr wichtig, dem Benutzer mitzuteilen, ob das Element erfolgreich gelöscht wurde. Daher wird „True“ zurückgegeben, wenn der Löschvorgang erfolgreich ist. Andernfalls wird „False“ zurückgegeben. Bitte denken Sie daran, das Größenattribut um 1 zu verringern.

Nennen wir den zu löschenden Knoten den aktuellen Knoten. Die Idee besteht darin, den nächsten Knoten des vorherigen Knotens mit dem nächsten Knoten des aktuellen Knotens zu verknüpfen. Angenommen, wir möchten 4 aus der angegebenen verknüpften Liste entfernen:

原链表： H-->3-->4-->5 
删除4后：H-->3-->5

Wir müssen den nächsten Knoten von 3 auf den nächsten Knoten von 4 verweisen, der 5 ist.

Angenommen, wir löschen auch 3

删除3后：H-->5

Hinweis: Um eine Verbindung zwischen dem vorherigen Knoten und dem Knoten neben dem aktuellen Knoten herzustellen, achten Sie darauf, den vorherigen Knoten im Auge zu behalten.

Algorithmus

1. Es gibt zwei Zeiger:

●CURR – zunächst dem Header zugewiesen

●prev – zunächst zeigte auf None

2. Wenn der Eingabewert mit den Daten von curr übereinstimmt, überprüfen Sie die Existenz von prev:

● Wenn ja, setzen Sie den nächsten Knoten von prev auf den nächsten Knoten von curr

●Wenn nicht, zeigen Sie einfach mit dem Kopf auf den nächsten Knoten von curr (dies geschieht, wenn Sie den ersten Knoten löschen möchten)

● Dekrementieren Sie das Größenattribut um 1

● True zurückgeben

3. Wenn der Eingabewert nicht mit den Daten von curr übereinstimmt, gehen Sie wie folgt zum nächsten Knoten:

● Zeigen Sie auf die vorherige Kurve

● Zeigen Sie mit CURR auf den nächsten Knoten CURR

4 Wiederholen Sie die Schritte 1-3 bis zum Ende der verknüpften Liste

5. Wenn das Ende der verknüpften Liste erreicht ist, wird False zurückgegeben , was darauf hinweist, dass in der verknüpften Liste keine Elemente mit dem Eingabewert vorhanden sind

Implementierungscode:

def removeNode(self,value):
        prev = None
        curr = self.head
        while curr:
            if curr.getData() == value:
                if prev:
                    prev.setNextNode(curr.getNextNode())
                else:
                    self.head = curr.getNextNode()
                return True
                    
            prev = curr
            curr = curr.getNextNode()
            
        return False

Empfohlene verwandte Video-Tutorials: „

Python3-Tutorial"

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 finde und lösche ich Knoten in einer einfach verknüpften Python-Liste?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!