Numérique et Sciences Informatiques > Algorithmique : Structures de Données Avancées > Listes Chaînées > Implémentation (simplement et doublement chaînées)
Implémentation des Listes Chaînées : Simples et Doubles
Apprenez à implémenter les listes chaînées simples et doubles en Python. Ce guide détaille la structure, les opérations fondamentales et des exemples pratiques adaptés aux élèves de lycée.
Introduction aux Listes Chaînées
Les listes chaînées sont des structures de données fondamentales en informatique. Contrairement aux tableaux (listes en Python), les éléments ne sont pas stockés de manière contiguë en mémoire. Au lieu de cela, chaque élément, appelé nœud, contient une donnée et un pointeur (ou référence) vers le nœud suivant dans la séquence. Ceci permet une allocation de mémoire dynamique et des insertions/suppressions efficaces, mais au prix d'un accès plus lent aux éléments individuels par rapport aux tableaux.
Nœuds : Les Blocs de Construction
Un nœud est l'unité de base d'une liste chaînée. Il se compose généralement de deux parties :
En Python, on peut représenter un nœud avec une classe :
class Node:
def __init__(self, data):
self.data = data
self.next = None
Dans ce code, data stocke la valeur du nœud, et next est initialisé à None. next pointera vers un autre nœud lorsqu'il sera inséré dans la liste.
Liste Chaînée Simplement Chaînée
Une liste chaînée simplement chaînée est la forme la plus simple. Chaque nœud possède un pointeur vers le nœud suivant, mais pas vers le nœud précédent. Cela permet de parcourir la liste dans une seule direction. Voici une implémentation de base en Python :
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Exemple d'utilisation
linked_list = LinkedList()
linked_list.insert_at_beginning(3)
linked_list.insert_at_beginning(7)
linked_list.insert_at_beginning(10)
linked_list.display() # Output: 10 -> 7 -> 3 -> None
Dans cet exemple :
head pointe vers le premier nœud de la liste.insert_at_beginning ajoute un nouveau nœud au début de la liste.display affiche le contenu de la liste en parcourant chaque nœud.
Liste Chaînée Doublement Chaînée
Une liste chaînée doublement chaînée est une variante où chaque nœud possède deux pointeurs : un vers le nœud suivant (comme dans la liste simplement chaînée) et un vers le nœud précédent. Cela permet de parcourir la liste dans les deux directions, ce qui peut être utile pour certaines opérations. Voici une implémentation en Python :
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
new_node.prev = None
def display(self):
current = self.head
while current:
print(current.data, end=" <-> ")
current = current.next
print("None")
# Exemple d'utilisation
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.insert_at_beginning(3)
doubly_linked_list.insert_at_beginning(7)
doubly_linked_list.insert_at_beginning(10)
doubly_linked_list.display() # Output: 10 <-> 7 <-> 3 <-> None
Principales différences par rapport à la liste simplement chaînée :
Bien que les listes doublement chaînées utilisent plus de mémoire (en raison du pointeur supplémentaire), elles offrent une plus grande flexibilité pour certaines opérations, comme la suppression d'un nœud en connaissant seulement sa référence.prev pour pointer vers le nœud précédent.prev du nœud précédent et du nouveau nœud.
Opérations Fondamentales
Les opérations de base sur les listes chaînées incluent :
L'implémentation de ces opérations varie légèrement entre les listes simplement et doublement chaînées.
Avantages et Inconvénients
Avantages des Listes Chaînées :
Inconvénients des Listes Chaînées :
Ce qu'il faut retenir
FAQ
-
Quelle est la différence entre une liste chaînée simplement chaînée et une liste chaînée doublement chaînée ?
La principale différence est qu'une liste chaînée doublement chaînée a un pointeur vers le nœud précédent en plus du pointeur vers le nœud suivant, ce qui permet de parcourir la liste dans les deux sens. Une liste simplement chaînée ne possède qu'un pointeur vers le nœud suivant. -
Quand devrais-je utiliser une liste chaînée plutôt qu'un tableau (liste en Python) ?
Utilisez une liste chaînée lorsque vous avez besoin d'insérer ou de supprimer fréquemment des éléments, en particulier au milieu de la liste, et que l'accès rapide aux éléments par index n'est pas une priorité. Utilisez un tableau lorsque vous avez besoin d'un accès rapide aux éléments par index et que les insertions et suppressions sont moins fréquentes.