Listes : listes simplement chaînées et doublement chaînées

5.1 Définition d'une liste et ses types

Une liste est une structure de données dynamique composée d'éléments (nœuds), où chaque nœud contient des données et des liens vers d'autres nœuds. Contrairement aux tableaux, les listes peuvent changer de taille pendant l'exécution du programme.

Important ! Ici, on ne parle pas de la classe list de Python, mais d'une structure de données tirée de la théorie des algorithmes.

Types de listes :

• Liste simplement chaînée (Singly Linked List) : Chaque nœud contient des données et un lien vers le nœud suivant.
• Liste doublement chaînée (Doubly Linked List) : Chaque nœud contient des données, un lien vers le nœud suivant et un lien vers le nœud précédent.

5.2 Principe de fonctionnement d'une liste simplement chaînée

Structure d'une liste simplement chaînée :

• Nœud (Node) : Composé de deux parties : données et lien vers le nœud suivant.
• Tête (Head) : Pointeur vers le premier nœud de la liste.

Principe de fonctionnement :

• Ajout d'un nœud : Se fait en créant un nouveau nœud et en mettant à jour le lien du dernier nœud vers le nouveau nœud.
• Suppression d'un nœud : Nécessite la mise à jour du lien du nœud précédent vers le nœud suivant celui à supprimer.

Exemple d'implémentation :

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Exemple d'utilisation :
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Affichage : 1 -> 2 -> 3 -> None

5.3 Principe de fonctionnement d'une liste doublement chaînée

Structure d'une liste doublement chaînée :

• Nœud (Node) : Composé de trois parties : données, lien vers le nœud suivant et lien vers le nœud précédent.
• Tête (Head) : Pointeur vers le premier nœud de la liste.
• Queue (Tail) : Pointeur vers le dernier nœud de la liste (non obligatoire, mais souvent utilisé).

Principe de fonctionnement :

• Ajout d'un nœud : Se fait en créant un nouveau nœud et en mettant à jour les liens du dernier nœud et du nouveau nœud.
• Suppression d'un nœud : Nécessite la mise à jour des liens des nœuds adjacent à celui à supprimer.

Exemple d'implémentation :

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Exemple d'utilisation :
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Affichage : 1 <-> 2 <-> 3 <-> None

5.4 Opérations de base

Opérations de base : insertion, suppression, recherche

Insertion :

• Liste simplement chaînée : L'insertion d'un nouveau nœud à la fin de la liste requiert de parcourir tous les nœuds jusqu'au dernier et de mettre à jour le lien du dernier nœud.
• Liste doublement chaînée : L'insertion d'un nouveau nœud à la fin de la liste est similaire à celle d'une liste simplement chaînée, mais nécessite aussi de mettre à jour le lien prev du nouveau nœud au nœud précédent.

Suppression :

• Liste simplement chaînée : La suppression d'un nœud requiert de parcourir la liste jusqu'au nœud à supprimer et de mettre à jour le lien du nœud précédent vers le nœud suivant celui à supprimer.
• Liste doublement chaînée : La suppression d'un nœud nécessite la mise à jour des liens next et prev des nœuds adjacents à celui à supprimer.

Recherche : Parcours de la liste de la tête à la queue et comparaison des données de chaque nœud avec la valeur recherchée. La complexité temporelle est de O(n).

5.5 Exemple d'utilisation des listes

Prenons un exemple pour implémenter une pile basée sur une liste simplement chaînée.

Une pile peut être facilement implémentée à l'aide d'une liste simplement chaînée, utilisant les méthodes d'ajout push et de suppression pop d'éléments. Elle doit avoir 2 méthodes :

• push — ajout d'un nouvel élément à la fin de la liste
• pop — retrait du dernier élément à la fin de la liste

Exemple d'implémentation :

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Exemple d'utilisation :
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Affichage : 3 -> 2 -> 1 -> None
print(stack.pop())  # Affichage : 3
stack.display()  # Affichage : 2 -> 1 -> None