Comment rechercher et supprimer des nœuds dans une liste python à lien unique ?

Dans l'article précédent [Comment insérer et afficher des nœuds dans une liste python à chaînage unique ? ] vous présente ce qu'est une liste à chaînage unique et comment ajouter des nœuds et afficher tous les nœuds. L'article suivant explique comment rechercher et supprimer des nœuds. J'espère qu'il vous sera utile.

Comment trouver un nœud à partir d'une liste à chaînage unique ?

Comme pour la plupart des structures de données, la seule façon de savoir si un élément existe est de parcourir l'intégralité de la liste chaînée. Notez que nous pouvons utiliser la recherche binaire si la liste chaînée est triée. Mais ici, nous considérerons une liste chaînée non triée.

Comment ça marche : L'utilisateur donne l'élément de nœud qu'il faut trouver. Si on trouve l'élément, on renvoie vrai, sinon on renvoie faux, vous pouvez également utiliser un compteur et renvoyer l'index de l'élément ; (si cela existe).

Algorithme

1. Réglez le pointeur curr sur la tête

2. Comparez curr.data avec la valeur d'entrée :

.

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

Comment supprimer un nœud d'une liste à chaînage unique ? À partir de l'exemple ci-dessus, nous savons comment trouver des nœuds, nous pouvons ensuite l'utiliser pour supprimer des nœuds. Nous pouvons obtenir une valeur de l'utilisateur, rechercher l'élément dans la liste chaînée et le supprimer s'il existe.

Remarque : Il est très important d'indiquer à l'utilisateur si l'élément a été supprimé avec succès. Par conséquent, il renvoie True lorsque la suppression est réussie, sinon il renvoie False, n'oubliez pas de décrémenter l'attribut size de 1 ;

Appelons le nœud à supprimer le nœud actuel. L’idée est de relier le nœud suivant du nœud précédent au nœud suivant du nœud actuel. Par exemple, disons que nous voulons supprimer 4 de la liste chaînée donnée :

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

Supposons que nous supprimions également 3

删除3后：H-->5

1 Il y a deux pointeurs :

Quantity CURR - initialement attribué à l'en-tête

Quantityprev - initialement. pointé vers Aucun

2. Si la valeur d'entrée correspond aux données de curr, vérifiez l'existence de prev :

● Si c'est le cas, définissez le nœud suivant de prev sur le nœud suivant de curr

● Sinon, pointez simplement la tête vers le nœud suivant de curr (cela se produit lorsque vous souhaitez supprimer le premier nœud)

● Décrémentez l'attribut size de 1

● Return True

3. Si la valeur d'entrée ne correspond pas aux données de curr, passez au nœud suivant de la manière suivante :

● Pointez sur la courbe précédente

● Pointez CURR vers le nœud suivant CURR

4. Répétez les étapes 1 à 3 jusqu'à la fin de la liste chaînée

5 Si la fin de la liste chaînée est atteinte, False est renvoyé. , indiquant qu'il n'y a aucun élément dans la liste chaînée avec La valeur d'entrée correspond au

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

" et plus C'est tout le contenu de cet article, j'espère qu'il sera utile à l'étude de chacun. Pour un contenu plus passionnant, vous pouvez prêter attention aux colonnes de didacticiels pertinentes du site Web PHP chinois ! ! !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!