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

Table des matières

Introduction :

Dans le chapitre précèdent, nous avons vu les listes simplement chaînées, car elles sont importants avants de découvrir les listes doublement chaînées ; dans cette partie on va voir les listes doublements chaînées.

Comment les créer, avec les classes, les fonctions d’ajout dans une liste vide, au début et à a fin, entre deux éléments.

Et finalement suivez le chapitre 3, pour voir plus des fonctions telle que la suppression.

1. Listes doublements chaînées :

Dans une liste simplement chaînée, chaque nœud de la liste a deux composantes, la valeur réelle du nœud et la référence au nœud suivant dans la liste chaînée. Dans la liste doublement chaînée, chaque nœud a trois composantes : la valeur du nœud, la référence au nœud précédent et la référence au nœud suivant. Pour le nœud de départ de la liste chaînée, la référence au nœud précédent est nulle. De même, pour le dernier nœud de la liste chaînée, la référence au nœud suivant est nulle.

Avantages et inconvénients d'une liste doublement chaînée :

Voici quelques-uns des avantages et des inconvénients d'une liste doublement chaînée :

Avantages :

Contrairement à une liste simplement chaînée, la liste doublement chaînée peut être parcourue et recherchée dans les deux sens. La référence au nœud suivant aide à parcourir le nœud dans le sens de l'avance tandis que les références aux nœuds précédents permettent de le parcourir dans le sens du recul.

Les opérations de base telles que l'insertion et la suppression sont plus faciles à mettre en œuvre dans les listes doublement chaînées car, contrairement aux listes chaînées simples, nous n'avons pas besoin de passer au nœud précédent et de stocker sa référence. Au contraire, dans une liste doublement chaînée, la référence du nœud précédent peut être récupérée à partir du nœud que nous voulons supprimer.

Inconvénients :

L'un des principaux inconvénients de la liste chaînée doublement est qu'il faut plus d'espace mémoire pour stocker une référence supplémentaire pour chaque nœud.

Quelques étapes supplémentaires sont nécessaires pour effectuer les opérations d'insertion et de suppression.

2. Implanter la liste doublement chaînée avec Python :

Dans cette section, nous verrons comment nous pouvons créer une liste chaînée doublement simple en Python.

Comme toujours, commençons par créer une classe pour le nœud unique de la liste.

Exemple de syntaxe :

class Node:
def __init__(liste, donnee):
liste.element = donnee
liste.suivant = None
liste.precedent = None

Vous pouvez voir dans le code ci-dessus, nous créons une classe Node avec trois variablesmembres : "element", "suivant", et "precedent". La variable "element" va stocker les donnéesréelles du nœud. La variable "suivant" stocke la référence au nœud suivant, tandis que la variable"precedent" stocke la référence au nœud précédent dans la liste doublement chaînée.

Ensuite, nous devons créer la classe « listedoublementchainee », qui contient différentes fonctions liées à la liste chaînée doublement. Ajoutez le code suivant :

Exemple de syntaxe :

class listedoublementchainee:
def __init__(liste):
liste.start_node = None

Tout au long de cet article, nous continuerons à ajouter des fonctions à cette classe.

3. Insertion d'articles dans une liste doublement chaînée :

Dans cette section, nous verrons les différentes façons d'insérer des éléments dans une liste doublement chaînée.

3.1. Insertion d'articles dans une liste vide :

La façon la plus simple d'insérer un élément dans une liste doublement chaînée est d'insérer un élément dans la liste vide. Le script suivant permet d'insérer un élément au début de la liste doublement liée :

Syntaxe :

Dans le script ci-dessus, nous définissons une méthode insert_listevide(). La méthode vérifie d'abord si la variable liste.start_node est None ou non. Si la variable est None, cela signifie que la liste est en fait vide. Ensuite, un nouveau nœud est créé et sa valeur est initialisée par la valeur passée en paramètre au paramètre de données de la fonction insert_listevide(). Enfin, la valeur de la variable liste.start_node est fixée au nouveau nœud. Dans le cas où la liste n'est pas vide, un message est simplement affiché à l'utilisateur pour l'informer que la liste n'est pas vide.

3.2. Insertion d'éléments au départ :

Pour insérer un élément au début de la liste doublement chaînée, nous devons d'abord vérifier si la liste est vide ou non. Si la liste est vide, nous pouvons simplement utiliser la logique définie dans la fonction insert_listevide() pour insérer l'élément puisque dans une liste vide, le premier élément est toujours au début.

Sinon, si la liste n'est pas vide, nous devons effectuer trois opérations :

Pour le nouveau nœud, la référence au nœud suivant sera fixée à liste.start_node.
Pour la liste.start_node, la référence au nœud précédent sera fixée au nœud nouvellement inséré.
Enfin, la liste.start_node deviendra le nouveau nœud inséré.

Syntaxe :

3.3. Insertion d'éléments à la fin :

L'insertion d'un élément à la fin de la liste doublement chaînée est quelque peu similaire à l'insertion d'un élément au début. Dans un premier temps, il faut vérifier si la liste est vide. Si la liste est vide, nous pouvons simplement utiliser la méthode insert_listevide() pour insérer l'élément. Si la liste contient déjà un élément, nous parcourons la liste jusqu'à ce que la référence au nœud suivant devienne Aucune. Lorsque la référence au nœud suivant devient Aucune, cela signifie que le nœud actuel est le dernier nœud.

Syntaxe :

3.4. Insertion d'un élément après un autre élément :

Pour insérer un élément après un autre, nous vérifions d'abord si la liste est vide ou non. Si la liste est effectivement vide, nous affichons simplement le message que la "liste est vide".

Dans le cas contraire, nous répétons l'opération à travers tous les nœuds de la liste doublement chaînée. Si le nœud après lequel nous voulons insérer le nouveau nœud n'est pas trouvé, nous affichons le message à l'utilisateur que l'élément n'est pas trouvé. Sinon, si le nœud est trouvé, il est sélectionné et nous effectuons quatre opérations :

1- Définissez la référence précédente du nœud nouvellement inséré au nœud sélectionné.

2- Définir la référence suivante du nœud nouvellement inséré à la référence suivante du nœud sélectionné.

3- Si le nœud sélectionné n'est pas le dernier nœud, définissez la référence précédente du nœud suivant après le nœud sélectionné au nœud nouvellement ajouté.

4- Enfin, définissez la référence suivante du nœud sélectionné au nœud nouvellement inséré.

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 insertion_debut(liste, donnee):
if liste.start_node is None:
nvnode = Node(donnee)
liste.start_node = nvnode
print("noeud inserer")
return
nvnode = Node(donnee)
nvnode.suivant = liste.start_node
liste.start_node.precedent = nvnode
liste.start_node = nvnode
def insert_fin(liste, donne):
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_apres(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("element n'existe pas dans la liste")
else:
nvnode = Node(donnee)
nvnode.precedent = n
nvnode.suivant = n.precedent
if n.suivant is not None:
n.suivant.precedent = nvnode
n.suivant = nvnode

3.5. Insertion d'un élément avant un autre élément :

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 insertion_debut(liste, donnee):
if liste.start_node is None:
nvnode = Node(donnee)
liste.start_node = nvnode
print("noeud inserer")
return
nvnode = Node(donnee)
nvnode.suivant = liste.start_node
liste.start_node.precedent = nvnode
liste.start_node = nvnode
def insert_fin(liste, donne):
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_apres(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("element n'existe pas dans la liste")
else:
nvnode = Node(donnee)
nvnode.precedent = n
nv.suivant = n.precedent
if n.suivant is not None:
n.suivant.precedent = nvnode
n.suivant = nvnode
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

4. Parcourir une liste doublement chaînée :

Parcourir une liste doublement chaînée est très similaire à parcourir une liste chaînée unique. Le programme est le suivant :

Syntaxe :

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

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

5. Exercice :

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

5.1 Initialiser les class de la liste, qu’affiche la liste vide ?

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

5.3 Insérer 15 entre 10 et 20

6. Solution :

6.1 :

Après l’initialisation, la liste est vide, alors elle affiche :

La liste est vide

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 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
nvliste = listedoublementchainee()
nvliste.affiche_liste()

Résultats de l’affichage :

6.2 :

Insertion :

Syntaxe :

Résultats de l’affichage :

6.3 :

Ajouter 15 entre 10 et 20

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
nvliste = listedoublementchainee()
nvliste.insert_listevide(10)
nvliste.insert_fin(20)
nvliste.insert_fin(30)
nvliste.insert_avant(20,15)
nvliste.affiche_liste()

Conclusion

Dans ce chapitre 2 des listes doublements chaînées, j’ai expliqué la différence entre les listes simplement chaînées et les listes doublements chaînées.

Comment créer et initialiser les class de la liste, ajouter dans une liste vide, au début à la fin, entre deux éléments.

Continuer vers la 3eme partie pour voir comment supprimer des éléments de la listes.

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