🔗 Listes Chaînées : Introduction aux Linked Lists

Imaginez une chasse au trésor où chaque indice vous mène au suivant. Les Listes Chaînées fonctionnent de la même manière ! Chaque élément connaît l'emplacement du suivant, formant ainsi une chaîne d'éléments reliés.

🚧 Structure de Base d'une Linked List

Chaque nœud dans une liste chaînée est comme une petite boîte contenant :

📦 Valeur : Le trésor ou la donnée que le nœud représente.
🧭 Lien : Le chemin vers le prochain nœud (comme un indice vers le prochain trésor).

📖 Types de Linked Lists

Liste Chaînée Simple : Chaque nœud pointe uniquement vers le suivant.
Liste Doublement Chaînée : Chaque nœud pointe vers le suivant et le précédent.
Liste Circulaire : Le dernier nœud pointe vers le premier, formant une boucle.

🌟 Avantages des Linked Lists

Pourquoi utiliser des listes chaînées ? Voici quelques super-pouvoirs :

⚡ Insertion et Suppression Rapides : Idéal pour les applications nécessitant des modifications fréquentes.
🎈 Taille Dynamique : Pas besoin de connaître la taille à l'avance !
🧩 Allocation Flexible : Les nœuds peuvent être stockés n'importe où en mémoire.

🚫 Inconvénients des Linked Lists

🐢 Accès Lent aux Éléments : Vous devez parcourir la liste depuis le début pour accéder à un élément.
📉 Utilisation de Mémoire Supplémentaire : Chaque nœud stocke une référence supplémentaire.

🎯 Cas d'Utilisation des Linked Lists

Les listes chaînées brillent dans des situations comme :

📚 Gestion de l'historique (navigateurs web, annulations dans les éditeurs).
🎵 Lecteurs de musique avec playlists dynamiques.
🕹️ Implémentation de structures comme les piles et les files d'attente.

📝 Implémentation en Python

1️⃣ Liste Chaînée Simple

Voici comment créer une liste chaînée simple en Python :

class Node:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None

class SinglyLinkedList:
    def __init__(self):
        self.tete = None

    def append(self, valeur):
        nouveau_noeud = Node(valeur)
        if not self.tete:
            self.tete = nouveau_noeud
            return
        dernier = self.tete
        while dernier.suivant:
            dernier = dernier.suivant
        dernier.suivant = nouveau_noeud

    def afficher(self):
        noeud_actuel = self.tete
        while noeud_actuel:
            print(noeud_actuel.valeur, end=" -> ")
            noeud_actuel = noeud_actuel.suivant
        print("None")

# Utilisation de la liste chaînée simple
ma_liste = SinglyLinkedList()
ma_liste.append(10)
ma_liste.append(20)
ma_liste.append(30)
ma_liste.afficher()  # Sortie : 10 -> 20 -> 30 -> None

2️⃣ Liste Doublement Chaînée

Pour naviguer dans les deux sens, utilisez une liste doublement chaînée :

class DoubleNode:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None
        self.precedent = None

class DoublyLinkedList:
    def __init__(self):
        self.tete = None

    def append(self, valeur):
        nouveau_noeud = DoubleNode(valeur)
        if not self.tete:
            self.tete = nouveau_noeud
            return
        dernier = self.tete
        while dernier.suivant:
            dernier = dernier.suivant
        dernier.suivant = nouveau_noeud
        nouveau_noeud.precedent = dernier

    def afficher(self):
        noeud_actuel = self.tete
        while noeud_actuel:
            print(noeud_actuel.valeur, end=" <-> ")
            noeud_actuel = noeud_actuel.suivant
        print("None")

# Utilisation de la liste doublement chaînée
ma_liste_double = DoublyLinkedList()
ma_liste_double.append(10)
ma_liste_double.append(20)
ma_liste_double.append(30)
ma_liste_double.afficher()  # Sortie : 10 <-> 20 <-> 30 <-> None

🔄 3️⃣ Liste Circulaire

Pour créer une boucle sans fin, voici la liste circulaire :

class CircularNode:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None

class CircularLinkedList:
    def __init__(self):
        self.tete = None

    def append(self, valeur):
        nouveau_noeud = CircularNode(valeur)
        if not self.tete:
            self.tete = nouveau_noeud
            nouveau_noeud.suivant = self.tete
            return
        dernier = self.tete
        while dernier.suivant != self.tete:
            dernier = dernier.suivant
        dernier.suivant = nouveau_noeud
        nouveau_noeud.suivant = self.tete

    def afficher(self):
        noeud_actuel = self.tete
        if not self.tete:
            return
        while True:
            print(noeud_actuel.valeur, end=" -> ")
            noeud_actuel = noeud_actuel.suivant
            if noeud_actuel == self.tete:
                break
        print("(retour au début)")

# Utilisation de la liste circulaire
ma_liste_circulaire = CircularLinkedList()
ma_liste_circulaire.append(10)
ma_liste_circulaire.append(20)
ma_liste_circulaire.append(30)
ma_liste_circulaire.afficher()  # Sortie : 10 -> 20 -> 30 -> (retour au début)

💪 Exercices

Mettez en pratique ce que vous avez appris avec ces exercices :

# Exercices :

# 1. Implémentez une fonction pour insérer un nœud au début d'une liste chaînée simple.

# 2. Écrivez une méthode pour supprimer un nœud avec une valeur donnée dans une liste chaînée simple.

# 3. Créez une fonction qui inverse une liste chaînée simple.

# 4. Implémentez une liste doublement chaînée qui permet d'insérer et de supprimer des nœuds à n'importe quelle position.

# 5. Écrivez un programme qui détecte s'il y a une boucle dans une liste chaînée (liste circulaire).

# 6. Créez une liste chaînée circulaire qui modélise une playlist musicale en boucle, avec la possibilité de passer à la chanson suivante ou précédente.

🎉 Conclusion

Les Listes Chaînées sont comme des trains où chaque wagon est relié au suivant. Elles offrent une grande flexibilité pour gérer des données dynamiques. Choisissez le type de liste chaînée qui convient le mieux à votre situation :

🚂 Liste Chaînée Simple : Pour des séquences simples.
🚃 Liste Doublement Chaînée : Quand vous devez aller en avant et en arrière.
🔁 Liste Circulaire : Pour des cycles sans fin, comme une playlist en boucle.

Maintenant, vous êtes prêt à intégrer les Linked Lists dans vos projets et à profiter de leur puissance pour gérer des données dynamiques !

Leçons