Tuto Python : Liste simplement chaînée : Créer, parcourir, inserer, supprimer

Table des matières

Introduction :

Dans la première partie de ce chapitre, avant d’entamer les listes doublement chaînées on va tout d’abord découvrir les listes simplement chaînées.

Premièrement on va voire la définition, ensuite comment créer une liste simplement chaînée, deuxièmement, on va voir comment parcourir la liste, et comment afficher les éléments de la liste, troisièmement, comment ajouter et supprimer dans une liste par la création et l’appellation des fonction.

Et finalement continuer vers le chapitre suivant pour comprendre les liste doublements chaînées.

1. Listes simplement chaînées :

Comme les tableaux, la liste chaînée est une structure de données linéaire. Contrairement aux tableaux, les éléments de liste chaînée ne sont pas stockés à un endroit contigu ; les éléments sont liés à l'aide de pointeurs.

Pourquoi une liste chaînée ?

Les tableaux peuvent être utilisés pour stocker des données linéaires de types similaires, mais ils présentent les limites suivantes.

1) La taille des tableaux est fixe : nous devons donc connaître à l'avance la limite supérieure du nombre d'éléments. De plus, en général, la mémoire allouée est égale à la limite supérieure, quelle que soit l'utilisation.

2) L'insertion d'un nouvel élément dans un tableau d'éléments est coûteuse car il faut créer de la place pour les nouveaux éléments et pour créer de la place, les éléments existants doivent être déplacés.

Avantages par rapport aux tableaux

1) Taille dynamique

2) Facilité d'insertion/suppression

Les inconvénients :

1) L'accès aléatoire n'est pas autorisé. Nous devons accéder aux éléments de manière séquentielle à partir du premier nœud. Nous ne pouvons donc pas faire de recherche binaire avec des listes chaînées efficacement avec son implémentation par défaut. Pour en savoir plus, cliquez ici.

2) Un espace mémoire supplémentaire pour un pointeur est nécessaire pour chaque élément de la liste.

3) N'est pas compatible avec la mémoire cache. Comme les éléments de tableau sont des emplacements contigus, il y a une localité de référence qui n'existe pas dans le cas des listes chaînées.

Représentation :

Une liste chaînée est représentée par un pointeur vers le premier nœud de la liste chaînée. Le premier nœud est appelé la tête. Si la liste chaînée est vide, alors la valeur de la tête est NULL.

Chaque nœud d'une liste est constitué d'au moins deux parties :

1) les données

2) Pointeur (ou référence) vers le nœud suivant

En C, nous pouvons représenter un nœud à l'aide de structures.

En Java ou en C#, la liste chaînée peut être représentée comme une classe et un nœud comme une classe séparée. La classe de liste chaînée contient une référence de type classe Node.

1.1. Création d'une liste simplement chaînée :

Une liste chaînée est créée en utilisant la classe de nœuds. On crée un objet Node et on crée une autre classe pour utiliser cet objet Node. Nous passons les valeurs appropriées à travers l'objet Node pour pointer les éléments de données suivants. Le programme ci-dessous crée la liste chaînée avec trois éléments de données. Dans la section suivante, nous verrons comment parcourir la liste chaînée.

Exemple de syntaxe :

class Node:
def __init__(liste, dataval=None):
liste.dataval = dataval
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.teteval = None
liste1 = listechainee()
liste1.teteval = Node("lundi")
e2 = Node("mardi")
e3 = Node("mercredi")
# Relier le premier nœud au deuxième nœud
liste1.teteval.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3

1.2. Parcourir une liste chaînée :

Les listes simplement chaînées peuvent être parcourues dans le sens inverse à partir du premier élément de données. Nous imprimons simplement la valeur de l'élément de données suivant en associant le pointeur du nœud suivant à l'élément de données actuel.

Syntaxe :

class Node:
def __init__(liste, dataval=None):
liste.dataval = dataval
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.teteval = None
def listeaffiche(liste):
printval = liste.teteval
while printval is not None:
print (printval.dataval)
printval = printval.valsuivant
liste1 = listechainee()
liste1.teteval = Node("lundi")
e2 = Node("mardi")
e3 = Node("mercredi")
# Relier le premier nœud au deuxième nœud
liste1.teteval.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3
liste1.listeaffiche()

Résultats de l’exécution :

1.3. Insertion dans une liste simplement chaînée :

L'insertion d'un élément dans la liste chaînée implique la réaffectation des pointeurs des nœuds existants au nœud nouvellement inséré. Selon que le nouvel élément de données est inséré au début, au milieu ou à la fin de la liste chaînée, nous avons les scénarios suivants.

Insertion au début de la liste chaînée :

Cela implique de pointer le pointeur suivant du nouveau nœud de données vers la tête actuelle de la liste chaînée. Ainsi, la tête actuelle de la liste chaînée devient le deuxième élément de données et le nouveau nœud devient la tête de la liste chaînée.

Syntaxe :

class Node:
def __init__(liste, dataval=None):
liste.dataval = dataval
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.teteval = None
def listeaffiche(liste):
printval = liste.teteval
while printval is not None:
print (printval.dataval)
printval = printval.valsuivant
def audebut(liste,nouveaudata):
Nvnode = Node(nouveaudata)
#mettre à jour les nouveaux nœuds à la suite du nœud existant
Nvnode.valsuivant = liste.teteval
liste.teteval = Nvnode
liste1 = listechainee()
liste1.teteval = Node("lundi")
e2 = Node("mardi")
e3 = Node("mercredi")
# Relier le premier nœud au deuxième nœud
liste1.teteval.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3
liste1.audebut("samedi")
liste1.listeaffiche()

Résultats de l’exécution :

Insertion à la fin de la liste :

Cela implique de pointer le pointeur suivant du dernier nœud actuel de la liste chaînée vers le nouveau nœud de données. Ainsi, le dernier nœud actuel de la liste chaînée devient l'avant-dernier nœud de données et le nouveau nœud devient le dernier nœud de la liste chaînée.

Syntaxe :

class Node:
def __init__(liste, dataval=None):
liste.dataval = dataval
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.teteval = None
#fonction pour l'affichage
def listeaffiche(liste):
printval = liste.teteval
while printval is not None:
print (printval.dataval)
printval = printval.valsuivant
# fonction pour ajouter à la fin de la liste
def alafin(liste,nouveaudata):
Nvnode = Node(nouveaudata)
if liste.teteval is None:
liste.teteval = Nvnode
return
dernier = liste.teteval
while(dernier.valsuivant):
dernier = dernier.valsuivant
dernier.valsuivant=Nvnode
#fonction pour ajouter au debut
def audebut(liste,nouveaudata):
Nvnode = Node(nouveaudata)
#mettre à jour les nouveaux nœuds à la suite du nœud existant
Nvnode.valsuivant = liste.teteval
liste.teteval = Nvnode
liste1 = listechainee()
liste1.teteval = Node("lundi")
e2 = Node("mardi")
e3 = Node("mercredi")
# Relier le premier nœud au deuxième nœud
liste1.teteval.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3
liste1.audebut("samedi")
liste1.alafin("jeudi")
liste1.listeaffiche()

Insertion entre deux nœuds de données :

Il s'agit d'utiliser le pointeur d'un nœud spécifique pour pointer vers le nouveau nœud. Cela est possible en passant à la fois par le nouveau nœud et le nœud existant, après quoi le nouveau nœud sera inséré. Nous définissons donc une classe supplémentaire qui fera passer le pointeur suivant du nouveau nœud au pointeur suivant du nœud central. Ensuite, nous assignons le nouveau nœud au pointeur suivant du nœud central.

Syntaxe :

class Node:
def __init__(liste, dataval=None):
liste.dataval = dataval
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.teteval = None
#fonction pour l'affichage
def listeaffiche(liste):
printval = liste.teteval
while printval is not None:
print (printval.dataval)
printval = printval.valsuivant
#fonction pour ajouter entre deux
def entre(liste,millieux,nouveaudata):
if millieux is None:
print("le node mentioner est absents")
return
Nvnode = Node(nouveaudata)
Nvnode.valsuivant = millieux.valsuivant
millieux.valsuivant = Nvnode
liste1 = listechainee()
liste1.teteval = Node("lundi")
e2 = Node("mardi")
e3 = Node("jeudi")
# Relier le premier nœud au deuxième nœud
liste1.teteval.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3
liste1.entre(liste1.teteval.valsuivant, "mercredi")
liste1.listeaffiche()

1.4. Suppression d'un élément d'une liste chaînée :

Nous pouvons supprimer un nœud existant en utilisant la clé de ce nœud. Dans le programme ci-dessous, nous localisons le nœud précédent du nœud qui doit être supprimé. Ensuite, nous dirigeons le pointeur suivant de ce nœud vers le nœud suivant du nœud à supprimer.

Syntaxe :

class Node:
def __init__(liste, dataval=None):
liste.dataval = dataval
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.teteval = None
#fonction pour l'affichage
def listeaffiche(liste):
printval = liste.teteval
while printval is not None:
print (printval.dataval)
printval = printval.valsuivant
#fonction pour suprimer
def supr(liste, clesupr):
valsup = liste.teteval
if (valsup is not None):
if(valsup.dataval == clesupr):
liste.teteval = valsup.valsuivant
valsup = None
return
while (valsup is not None):
if valsup.dataval == clesupr:
break
prev = valsup
valsup = valsup.valsuivant
if (valsup == None):
return
prev.valsuivant = valsup.valsuivant
valsup = None
liste1 = listechainee()
liste1.teteval = Node("lundi")
e2 = Node("mardi")
e3 = Node("jeudi")
# Relier le premier nœud au deuxième nœud
liste1.teteval.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3
liste1.supr("jeudi")
liste1.listeaffiche()

Résultats de l’affichage :

2. Exercice :

Exercice :

Créer une liste simplement chaînée avec les étapes suivante :

Class nom, class listechaînée
Initialiser 3 premier éléments : « amine » « ayman » « mina »
Créer ensuite une fonction pour l’affichage « afficher »
Par la fonction « afficher » affiche les 3 éléments déjà initialiser
Insérer à la fin de la liste « mary »

3. Solution :

3.1. :

Création des deux class nom et listechainee :

Syntaxe :

class nom:
def __init__(liste, valeur=None):
liste.valeur = valeur
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.tetevaleur = None

Résultats de l’affichage :

le code n’affiche rien car on a pas encore initialiser les éléments dans la liste, et la fonction de l’affichage n’est pas disponible encore .

3.2. :

Initialisation de 3 éléments dans la liste :

Syntaxe :

class nom:
def __init__(liste, valeur=None):
liste.valeur = valeur
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.tetevaleur = None
listenom = listechainee()
listenom.tetevaleur = nom("amine")
e2 = nom("ayman")
e3 = nom("mina")
# Relier le premier nœud au deuxième nœud
listenom.tetevaleur.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3

Résultats de l’affichage :

Le code n’affiche rien parce qu’on n’a pas encore créé une fonction d’affichage, mais les éléments sont initialisés dans la liste.

3.3. :

Création de la fonction « afficher » :

Syntaxe :

#fonction pour l'affichage
def afficher(liste):
printvaleur = liste.tetevaleur
while printvaleur is not None:
print (printvaleur.valeur)
printvaleur = printvaleur.valsuivant

L’emplacement de la fonction dans le code:

Syntaxe :

class nom:
def __init__(liste, valeur=None):
liste.valeur = valeur
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.tetevaleur = None
#fonction pour l'affichage
def afficher(liste):
printvaleur = liste.tetevaleur
while printvaleur is not None:
print (printvaleur.valeur)
printvaleur = printvaleur.valsuivant
listenom = listechainee()
listenom.tetevaleur = nom("amine")
e2 = nom("ayman")
e3 = nom("mina")
# Relier le premier nœud au deuxième nœud
listenom.tetevaleur.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3

L’exécution du code ne donne aucun résultat, car nous n’avons pas encore appeler la fonction « afficher »

3.4. :

Affichage des éléments par la fonction « afficher » :

Syntaxe :

Résultats de l’exécution :

Dans cette partie de code les éléments sont afficher car nous avons appelé la fonction « afficher »

3.5. :

Ajouter l’éléments « mary » à la fin de la liste :

Syntaxe de la fonction :

#fonction d'ajoute à la fin
def fin(liste,nouveaunom):
nvnom = nom(nouveaunom)
if liste.tetevaleur is None:
liste.tetevaleur = nvnom
return
dernier = liste.tetevaleur
while (dernier.valsuivant):
dernier = dernier.valsuivant
dernier.valsuivant=nvnom

Syntaxe du code complet :

class nom:
def __init__(liste, valeur=None):
liste.valeur = valeur
liste.valsuivant = None
class listechainee:
def __init__(liste):
liste.tetevaleur = None
#fonction d'ajoute à la fin
def fin(liste,nouveaunom):
nvnom = nom(nouveaunom)
if liste.tetevaleur is None:
liste.tetevaleur = nvnom
return
dernier = liste.tetevaleur
while (dernier.valsuivant):
dernier = dernier.valsuivant
dernier.valsuivant=nvnom
#fonction pour l'affichage
def afficher(liste):
printvaleur = liste.tetevaleur
while printvaleur is not None:
print (printvaleur.valeur)
printvaleur = printvaleur.valsuivant
listenom = listechainee()
listenom.tetevaleur = nom("amine")
e2 = nom("ayman")
e3 = nom("mina")
# Relier le premier nœud au deuxième nœud
listenom.tetevaleur.valsuivant = e2
# Relier le deuxième nœud au troisième nœud
e2.valsuivant = e3
listenom.fin("mary")
listenom.afficher()

Résultats :

Conclusion

J’espère que vous avez compris le fonctionnement des listes simplement chaînées, la création et l’initialisation des éléments, les fonctions d’ajouts et de suppression. Continuer vers le chapitre suivant pour voire la relation entres les listes simplement chaînées et les listes doublements chaînées.

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