Suppression de noeuds dans les listes chainées

Introduction à la suppression de nœuds

La suppression de nœuds est une opération fondamentale dans les listes chaînées. Elle consiste à retirer un nœud de la liste tout en maintenant l'intégrité de la structure. La méthode de suppression diffère légèrement entre les listes simplement chaînées et doublement chaînées en raison de la présence ou de l'absence de pointeurs vers le nœud précédent.

Suppression dans une liste simplement chaînée

Dans une liste simplement chaînée, la suppression d'un nœud nécessite de modifier le pointeur next du nœud précédent celui qu'on souhaite supprimer pour qu'il pointe vers le nœud suivant celui qu'on supprime. Voici un exemple en Python : class LinkedList: def __init__(self): self.head = None #... les autres methodes comme insert_at_beginning et display sont omises pour la clarté def delete_node(self, key): current = self.head previous = None # Si le noeud à supprimer est la tete if current is not None and current.data == key: self.head = current.next current = None return # Recherche de la clé à supprimer while current is not None and current.data != key: previous = current current = current.next # Si la clé n'est pas trouvée if current is None: return # Suppression du noeud previous.next = current.next current = 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.delete_node(7) linked_list.display() #Output : 10 -> 3 -> None Explication

• On parcourt la liste avec current et previous.
• Si le nœud à supprimer est la tête, on met à jour la tête de la liste.
• Sinon, on cherche le nœud à supprimer et on met à jour le pointeur next du nœud précédent.

Suppression dans une liste doublement chaînée

La suppression dans une liste doublement chaînée est plus simple car on a accès au nœud précédent. Il faut mettre à jour les pointeurs next et prev des nœuds adjacents. Voici un exemple en Python : class DoublyLinkedList: def __init__(self): self.head = None #... les autres methodes comme insert_at_beginning et display sont omises pour la clarté def delete_node(self, key): current = self.head # Si le noeud à supprimer est la tete if current is not None and current.data == key: self.head = current.next if self.head is not None: self.head.prev = None return # Recherche de la clé à supprimer while current is not None and current.data != key: current = current.next # Si la clé n'est pas trouvée if current is None: return # Suppression du noeud if current.next is not None: current.next.prev = current.prev if current.prev is not None: current.prev.next = current.next # 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.delete_node(7) doubly_linked_list.display() #Output: 10 <-> 3 <-> None Explication:

• Si le noeud à supprimer est la tête, on met à jour la tête et le pointeur prev de la nouvelle tête si elle existe.
• Sinon, on met à jour le pointeur prev du nœud suivant et le pointeur next du nœud précédent pour contourner le nœud à supprimer.

Cas particuliers

Il faut considérer les cas particuliers suivants :

• Liste vide : La suppression ne peut pas être effectuée si la liste est vide.
• Nœud à supprimer non trouvé : Il faut gérer le cas où le nœud à supprimer n'est pas présent dans la liste.
• Suppression du premier nœud (tête) : Il faut mettre à jour le pointeur head de la liste.

Ce qu'il faut retenir

• La suppression de nœuds est une opération essentielle dans les listes chaînées.
• La suppression dans une liste simplement chaînée nécessite de modifier le pointeur next du nœud précédent.
• La suppression dans une liste doublement chaînée nécessite de modifier les pointeurs next et prev des nœuds adjacents.
• Il faut gérer les cas particuliers comme la liste vide, le nœud non trouvé et la suppression de la tête.