Les structures de données constituent un fondement essentiel de la programmation. Elles facilitent l’organisation des données, permettant ainsi une manipulation et un accès efficaces.
Dans ce guide, nous allons explorer en détail les listes simplement chaînées et les listes doublement chaînées, deux structures de données fondamentales.
Une liste chaînée est une structure de données linéaire où les éléments ne sont pas stockés de manière contiguë en mémoire, contrairement aux tableaux. Chaque élément, appelé nœud, est lié au suivant par l’intermédiaire de pointeurs. Le premier nœud de la liste est désigné comme la tête.
La taille d’une liste chaînée est dynamique, ce qui signifie qu’elle peut contenir autant de nœuds que nécessaire, dans la limite de la mémoire disponible.
Il existe principalement deux types de listes chaînées. Examinons-les en détail.
#1. Liste Simplement Chaînée
Une liste simplement chaînée contient un unique pointeur qui relie chaque nœud au nœud suivant dans la séquence. Chaque nœud doit contenir les données et un pointeur vers le nœud suivant.
Le dernier nœud de la liste possède un pointeur suivant qui est nul, signalant la fin de la liste.
Vous trouverez ci-dessous une représentation visuelle d’une liste simplement chaînée.
Maintenant que nous avons une bonne compréhension de la liste simplement chaînée, examinons les étapes pour l’implémenter en Python.
Implémentation d’une Liste Simplement Chaînée
1. La première étape consiste à définir la structure d’un nœud.
Comment créer un nœud ?
En Python, la création d’un nœud est facilitée par l’utilisation d’une classe. Cette classe contiendra les données du nœud et un pointeur vers le nœud suivant.
Voici le code pour un nœud :
class Node: def __init__(self, data): ## données du nœud self.data = data ## pointeur vers le nœud suivant self.next = None
Avec cette classe, nous pouvons créer des nœuds contenant n’importe quel type de données. Nous verrons cela plus en détail dans un instant.
Maintenant que nous avons notre nœud, nous allons créer une liste chaînée composée de plusieurs nœuds. Pour ce faire, définissons une classe pour la liste chaînée.
2. Créons une classe nommée `LinkedList`, dans laquelle la tête est initialisée à `None`. Voici le code correspondant :
class LinkedList: def __init__(self): ## initialisation de la tête à None self.head = None
3. Nous avons maintenant les classes `Node` et `LinkedList`. Comment insérer un nouveau nœud dans la liste chaînée ? Une approche simple consiste à utiliser une méthode de la classe `LinkedList`. C’est effectivement une bonne idée. Écrivons donc une méthode pour insérer un nouveau nœud dans la liste.
Pour insérer un nouveau nœud dans la liste chaînée, nous devons suivre quelques étapes :
Voici les étapes :
- Vérifier si la tête est vide ou non.
- Si la tête est vide, affecter le nouveau nœud comme tête.
- Si la tête n’est pas vide, trouver le dernier nœud de la liste chaînée.
- Affecter le nouveau nœud au pointeur suivant du dernier nœud.
Voici le code pour insérer un nouveau nœud dans la liste chaînée :
class LinkedList: #### def insert(self, new_node): ## vérification si la tête est vide ou non if self.head: ## récupération du dernier nœud last_node = self.head while last_node.next != None: last_node = last_node.next ## affectation du nouveau nœud au pointeur suivant du dernier nœud last_node.next = new_node else: ## la tête est vide ## affectation du nœud comme tête self.head = new_node
Félicitations ! Nous avons créé la méthode pour insérer un nouveau nœud dans la liste chaînée. Maintenant, comment pouvons-nous accéder aux données des nœuds à partir de la liste ?
Pour accéder aux données de la liste, nous devons parcourir la liste à l’aide du pointeur suivant, comme nous l’avons fait pour trouver le dernier nœud dans la méthode d’insertion. Écrivons une méthode dans la classe `LinkedList` pour afficher toutes les données des nœuds dans la liste.
4. Suivez ces étapes pour afficher toutes les données des nœuds dans la liste :
- Initialiser une variable avec la tête.
- Écrire une boucle qui itère jusqu’à la fin de la liste chaînée.
- Afficher les données du nœud.
- Passer au nœud suivant en utilisant le pointeur suivant.
Voici le code :
class LinkedList:
####
def display(self):
## variable pour l'itération
temp_node = self.head
## itération jusqu'à la fin de la liste chaînée
while temp_node != None:
## affichage des données du nœud
print(temp_node.data, end='->')
## passage au nœud suivant
temp_node = temp_node.next
print('Null')
Voilà ! Nous avons terminé la création de la liste chaînée avec les méthodes nécessaires. Testons maintenant la liste chaînée en l’instanciant avec des données.
Nous pouvons créer un nœud avec le code `Node(1)`. Voici le code complet pour l’implémentation de la liste chaînée avec un exemple d’utilisation :
class Node:
def __init__(self, data):
## données du nœud
self.data = data
## pointeur vers le nœud suivant
self.next = None
class LinkedList:
def __init__(self):
## initialisation de la tête à None
self.head = None
def insert(self, new_node):
## vérification si la tête est vide ou non
if self.head:
## récupération du dernier nœud
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## affectation du nouveau nœud au pointeur suivant du dernier nœud
last_node.next = new_node
else:
## la tête est vide
## affectation du nœud comme tête
self.head = new_node
def display(self):
## variable pour l'itération
temp_node = self.head
## itération jusqu'à la fin de la liste chaînée
while temp_node != None:
## affichage des données du nœud
print(temp_node.data, end='->')
## passage au nœud suivant
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instanciation de la liste chaînée
linked_list = LinkedList()
## insertion de données dans la liste chaînée
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## affichage de la liste chaînée
linked_list.display()
Exécutez ce programme pour obtenir le résultat suivant :
1->2->3->4->5->6->7->Null
C’est tout pour les listes simplement chaînées. Vous savez maintenant comment implémenter une liste simplement chaînée. Avec cette connaissance, l’implémentation d’une liste doublement chaînée devrait être plus facile. Passons à la section suivante.
#2. Liste Doublement Chaînée
Une liste doublement chaînée contient deux pointeurs : l’un connecte le nœud au nœud précédent, et l’autre au nœud suivant dans la séquence. Chaque nœud doit contenir les données, un pointeur vers le nœud précédent et un pointeur vers le nœud suivant.
Le pointeur précédent du premier nœud est nul, et le pointeur suivant du dernier nœud est également nul, indiquant les deux extrémités de la liste.
Voici une illustration d’une liste doublement chaînée :
La création d’une liste doublement chaînée suit des étapes similaires à celles de la liste simplement chaînée. Cependant, répéter les mêmes explications pourrait être lassant. Parcourez attentivement le code suivant, et vous comprendrez rapidement. Allons-y.
Implémentation d’une Liste Doublement Chaînée
1. Création d’un nœud pour la liste doublement chaînée avec un pointeur vers le nœud précédent, les données et un pointeur vers le nœud suivant.
class Node: def __init__(self, data): ## pointeur vers le nœud précédent self.prev = None ## données du nœud self.data = data ## pointeur vers le nœud suivant self.next = None
2. La classe de la liste doublement chaînée.
class LinkedList: def __init__(self): ## initialisation de la tête à None self.head = None
3. Une méthode pour insérer un nouveau nœud dans la liste doublement chaînée.
class LinkedList: #### def insert(self, new_node): ## vérification si la tête est vide ou non if self.head: ## récupération du dernier nœud last_node = self.head while last_node.next != None: last_node = last_node.next ## affectation du dernier nœud au pointeur précédent du nouveau nœud new_node.prev = last_node ## affectation du nouveau nœud au pointeur suivant du dernier nœud last_node.next = new_node
4. Une méthode pour afficher les données de la liste doublement chaînée.
class LinkedList:
####
def display(self):
## affichage des données dans l'ordre normal
print("Ordre Normal: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## affichage des données dans l'ordre inverse en utilisant le pointeur précédent
print("Ordre Inverse: ", end='')
## récupération du dernier nœud
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Nous avons examiné le code de la liste doublement chaînée. Il manque un exemple d’utilisation de la classe de liste doublement chaînée. C’est à vous de jouer. Utilisez la classe de liste doublement chaînée de la même manière que la liste simplement chaînée. Amusez-vous bien 😊
Conclusion
Vous rencontrerez de nombreux problèmes basés sur les listes chaînées. Mais, il est essentiel de comprendre l’implémentation de base que vous avez apprise dans ce guide. J’espère que vous avez apprécié l’apprentissage de ce nouveau concept.
Bon codage 😊