Tuto Python : Liste doublement chaînée : Suppression d'éléments

Table des matières

Introduction :

Suite au chapitre précédent des listes doublements chaînées, après avoir comment crées les class d’une liste, est comment définir les fonctions de l’ajoute et de l’affichage, dans ce dernier chapitre on va voir la fonction de suppression.

1. Suppression d'éléments de la liste doublement chaînée :

Comme pour l'insertion, il peut y avoir plusieurs façons de supprimer des éléments d'une liste doublement chaînée. Dans cette section, nous allons passer en revue certaines d'entre elles.

1.1. Suppression d'éléments au début :

Il suffit de fixer la valeur du nœud de départ au nœud suivant, puis de fixer la référence précédente du nœud de départ à None. Mais avant cela, nous devons effectuer deux vérifications. Tout d'abord, nous devons voir si la liste est vide. Ensuite, nous devons voir si la liste ne contient qu'un seul élément ou non. Si la liste ne contient qu'un seul élément, nous pouvons simplement mettre le nœud de départ sur None. Le script suivant peut être utilisé pour supprimer des éléments du début de la liste doublement chaînée.

Exemple de syntaxe :

def suprimer_au_debut(liste):
if liste.start_node is None:
print("la liste est vide")
return
if liste.start_node.suivant is None:
liste.start_node = None
return
liste.start_node = liste.start_node.suivant
liste.start_precedent = None;

Ajoutez la méthode suprimer_au_debut() à la classe listedoublementchainee que vous avez créée précédemment.

Syntaxe :

1.2. Suppression d'éléments à la fin :

Pour supprimer l'élément de la fin, nous vérifions à nouveau si la liste est vide ou si la liste contient un seul élément. Si la liste ne contient qu'un seul élément, il suffit de mettre le nœud de départ sur None. Si la liste contient plus d'un élément, nous répétons l'opération jusqu'à ce que le dernier nœud soit atteint. Une fois que nous avons atteint le dernier nœud, nous fixons la référence suivante du nœud précédant le dernier nœud à None, ce qui supprime effectivement le dernier nœud. Le script suivant peut être utilisé pour supprimer l'élément de la fin.

Exemple de syntaxe :

def suprimer_fin(liste):
if liste.start_node is None:
print("la liste est vide.")
return
if liste.start_node.suivant is None:
liste.start_node = None
return
n = liste.start_node
while n.suivant is not None:
n = n.suivant
n.precedent.suivant = None

Syntaxe :

1.3. Suppression d'éléments par valeur :

Exemple de syntaxe :

def suprimer_valeur(liste, x):
if liste.start_node is None:
print("la liste est vide")
return
if liste.start_node.suivant is None:
if liste.start_node.element == x:
liste.start_node = None
else:
print("element indisponible")
return
if liste.start_node.element == x:
liste.start_node = liste.start_node.suivant
liste.start_node.precedent = None
return
n = liste.start_node
while n.suivant is not None:
if n.element == x:
break;
n = n.suivant
if n.precedent is not None:
n.precedent.suivant= n.suivant
n.suivant.precedent = n.precedent
else:
if n.element == x:
n.precedent.suivant = None
else:
print("element introuvable")

Dans le script ci-dessus, nous créons la fonction suprimer_valeur() qui prend la valeur du nœud comme paramètre et supprime ce nœud. Au début de la fonction, nous vérifions si la liste est vide ou non. Si la liste est vide, nous affichons simplement à l'utilisateur que la liste est vide.

if liste.start_node is None:
print("la liste est vide")
return

Ensuite, nous vérifions si la liste ne comporte qu'un seul élément et si cet élément est bien celui que nous voulons supprimer. Si le seul élément est celui que nous voulons supprimer, nous définissons simplement le fichier liste.start_node à "None", ce qui signifie que la liste n'aura plus d'élément. S'il n'y a qu'un seul élément et que ce n'est pas l'élément que nous voulons supprimer, nous afficherons simplement le message que l'élément à supprimer n'est pas trouvé.

if liste.start_node.suivant is None:
if liste.start_node.element == x:
liste.start_node = None
else:
print("element indisponible")
return

Ensuite, nous traitons le cas où la liste comporte plus d'un élément mais où l'élément à supprimer est le premier. Dans ce cas, nous exécutons simplement la logique que nous avons écrite pour la méthode suprimer_debut(). Le code suivant supprime un élément dès le début en cas d'éléments multiples :

if liste.start_node.element == x:
liste.start_node = liste.start_node.suivant
liste.start_node.precedent = None
return

Enfin, si la liste contient plusieurs éléments et que l'élément à supprimer n'est pas le premier, nous parcourons tous les éléments de la liste sauf le dernier et nous voyons si l'un des nœuds a la valeur qui correspond à la valeur à supprimer. Si le nœud est trouvé, nous effectuons les deux opérations suivantes :

·Fixer la valeur de la référence suivante du nœud précédent à la référence suivante du nœud à supprimer.
·Fixer la valeur de la référence suivante du nœud précédent à la référence suivante du nœud à supprimer.

Enfin, si le nœud à supprimer est le dernier nœud, la référence suivante du nœud précédant le dernier nœud est fixée à Aucune. Le script suivant met en œuvre cette logique :

n = liste.start_node
while n.suivant is not None:
if n.element == x:
break;
n = n.suivant
if n.precedent is not None:
n.precedent.suivant= n.suivant
n.suivant.precedent = n.precedent
else:
if n.element == x:
n.precedent.suivant = None
else:
print("element introuvable")

Syntaxe :

class Node:
def __init__(liste, donnee):
liste.element = donnee
liste.suivant = None
liste.precedent = None
class listedoublementchainee:
def __init__(liste):
liste.start_node = None
def insert_listevide(liste, donnee):
if liste.start_node is None:
nvnode = Node(donnee)
liste.start_node = nvnode
else:
print("La liste n'est pas vide")
def insert_fin(liste, donnee):
if liste.start_node is None:
nvnode = Node(element)
liste.start_node = nvnode
return
n = liste.start_node
while n.suivant is not None:
n = n.suivant
nvnode = Node(donnee)
n.suivant = nvnode
nvnode.precedent = n
def insert_avant(liste, x, donnee):
if liste.start_node is None:
print("liste est vide")
return
else:
n = liste.start_node
while n is not None:
if n.element == x:
break
n = n.suivant
if n is None:
print("élément n'existe pas dans la liste")
else:
nvnode = Node(donnee)
nvnode.suivant = n
nvnode.precedent = n.precedent
if n.precedent is not None:
n.precedent.suivant = nvnode
n.precedent = nvnode
def affiche_liste(liste):
if liste.start_node is None:
print("liste vide")
return
else:
n = liste.start_node
while n is not None:
print(n.element , " ")
n = n.suivant
def suprimer_au_debut(liste):
if liste.start_node is None:
print("la liste est vide.")
return
if liste.start_node.suivant is None:
liste.start_node = None
return
liste.start_node = liste.start_node.suivant
liste.start_precedent = None;
def suprimer_fin(liste):
if liste.start_node is None:
print("la liste est vide.")
return
if liste.start_node.suivant is None:
liste.start_node = None
return
n = liste.start_node
while n.suivant is not None:
n = n.suivant
n.precedent.suivant = None
def suprimer_valeur(liste, x):
if liste.start_node is None:
print("la liste est vide")
return
if liste.start_node.suivant is None:
if liste.start_node.element == x:
liste.start_node = None
else:
print("element indisponible")
return
if liste.start_node.element == x:
liste.start_node = liste.start_node.suivant
liste.start_node.precedent = None
return
n = liste.start_node
while n.suivant is not None:
if n.element == x:
break;
n = n.suivant
if n.precedent is not None:
n.precedent.suivant= n.suivant
n.suivant.precedent = n.precedent
else:
if n.element == x:
n.precedent.suivant = None
else:
print("element introuvable")

2. Exercice :

Exécutez le code dont vous disposez sur ce chapitre et appelez les fonctions suivantes tout en affichant les résultats :

2.1 Initialiser les class de la liste, Insérez les éléments suivants dans la liste : 10, 20, 30 et afficher les résultats.

2.2 supprimer le premier élément de la liste par la méthode suprimer_début().

2.3 par la méthode suprimer_fin(), supprimer le dernier éléments de la liste et afficher le résultats.

2.4 par la méthode suprimer_valeur() ; supprimez l’élément 20, affichez les resultats.

3. Solution :

6.1 :

Syntaxe :

Résultats de l’affichage :

6.2 méthodes suprime_au_debut :

Syntaxe :

Résultats de l’affichage :

6.3 :

Utilisation de la méthode suprime_fin()

Syntaxe :

6.4 utilisation de la méthode suprimer_valeur() :

Syntaxe :

Résultats de l’affichage :

Puisque tous les éléments de la liste sont supprimés les résultats affichent :

La liste vide.

Conclusion

Dans ce chapitre 3 des listes doublements chaînées, j’ai expliqué les différentes méthodes de suppression, et la logique utiliser pour chaque une des méthodes.

Et voilà nous sommes arrivées au dernier chapitre concernant les listes doublement chaînées.

Article publié le 09 Février 2021par Mouhtat Bilal