Introduction
Tu travailles sur un projet de développement d'un système de planification des trains pour un réseau ferroviaire très fréquenté.
On t'a demandé de développer un prototype pour les itinéraires de train du système de planification.
Chaque itinéraire est constitué d'une suite de gares où s'arrête un train donné.
Instructions
Ton équipe a décidé d'utiliser une liste doublement chaînée pour représenter chaque ligne de train de l'horaire.
Chaque gare le long de la ligne de train sera représentée par un nœud dans la liste chaînée.
Pas besoin de te soucier des heures d'arrivée et de départ dans les gares.
Chaque gare sera simplement représentée par un nombre.
Les lignes peuvent être prolongées, en ajoutant des gares au début ou à la fin d'une ligne.
Elles peuvent aussi être raccourcies en supprimant des gares au début ou à la fin d'une ligne.
Il arrive qu'une gare ferme, et dans ce cas elle doit être retirée de la ligne, même si elle ne se trouve ni au début ni à la fin de celle-ci.
La taille d'une ligne ne se mesure pas à la distance parcourue par le train, mais au nombre de gares où il s'arrête.
La liste chaînée est une structure de données fondamentale en informatique, souvent utilisée pour implémenter d'autres structures de données.
Comme son nom l'indique, c'est une liste de nœuds reliés entre eux.
C'est une liste de « nœuds », où chaque nœud est relié à son ou ses voisins.
Dans une liste simplement chaînée, chaque nœud n'est relié qu'au nœud qui le suit.
Dans une liste doublement chaînée, chaque nœud est relié à la fois au nœud qui le précède et à celui qui le suit.
Si tu veux approfondir les listes chaînées, jette un œil à cet article qui les explique avec de jolis dessins.
Bien que les listes chaînées puissent être implémentées de diverses manières, avec diverses structures de données sous-jacentes, on te demande ici d'implémenter ta liste chaînée dans un style orienté objet.
Dans le fichier stub, tu verras le début d'une classe Node, ainsi qu'une classe LinkedList.
Ta classe Node doit garder la trace de sa valeur, ainsi que des nœuds qui la précèdent ou qui la suivent.
Tes push, pop, shift, unshift, ainsi que la méthode spéciale pour len, doivent être implémentés dans la classe LinkedList.
Tu trouveras peut-être aussi utile d'implémenter une méthode spéciale iter pour l'itération.
Contrairement à l'exercice de base, on testera les cas d'erreur en appelant pop et shift sur des LinkedLists vides : tu devras donc raise les erreurs de façon appropriée.
Pour finir, en plus des méthodes présentées ci-dessus, on aimerait que tu implémentes delete.
delete prendra un argument, qui est la valeur à supprimer de la liste chaînée.
Si la valeur apparaît plusieurs fois, seule la première occurrence doit être supprimée.
Messages d'exception
Il est parfois nécessaire de lever une exception. Quand tu le fais, tu dois toujours inclure un message d'erreur explicite pour indiquer l'origine de l'erreur.
Cela rend ton code plus lisible et facilite grandement le débogage.
Dans les cas où tu sais que l'origine de l'erreur sera d'un certain type, tu peux choisir de lever l'un des types d'erreur intégrés, mais tu dois tout de même inclure un message explicite.
Cet exercice particulier exige que tu utilises l'instruction raise pour « lever » une ValueError lorsqu'une valeur de nœud en cours de delete() est introuvable dans la liste chaînée.
De plus, une IndexError doit être levée s'il ne reste aucun nœud à pop().
Les tests ne réussiront que si tu raise ces exceptions et que tu les accompagnes de messages.
Pour lever une ValueError avec un message, écris le message comme argument du type exception :
# When the value passed to `delete()` is not found.
if not found:
raise ValueError("Value not found")
Pour lever une IndexError avec un message, écris le message comme argument du type exception :
# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
raise IndexError("List is empty")
Les méthodes spéciales en Python
Les tests de cet exercice appelleront aussi len() sur ta LinkedList.
Pour que len() fonctionne, tu devras créer une méthode spéciale __len__.
Pour plus de détails sur l'implémentation des méthodes spéciales ou « dunder » en Python, consulte Docs Python : personnalisation de base des objets et Docs Python : object.len(self).
On te recommande aussi de créer une méthode spéciale __iter__ pour t'aider à parcourir ta liste chaînée.
Source
Un classique de l'informatique.
