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, nous te demandons ici d'implémenter ta liste chaînée de façon orientée objet.
Dans le fichier linked_list_test.cpp, tu verras qu'une classe List template est appelée.
Tu dois écrire cette classe avec les fonctions membres suivantes :
-
push ajoute un élément à la fin de la liste,
-
pop supprime et renvoie le dernier élément de la liste,
-
shift supprime et renvoie le premier élément de la liste,
-
unshift ajoute un élément au début de la liste, et
-
count renvoie le nombre total d'éléments de la liste actuelle.
Pour finir, nous aimerions que tu implémentes erase en plus des méthodes décrites ci-dessus.
erase 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.
Elle doit renvoyer si un élément a été supprimé ou non.
Bien que ce ne soit pas testé, tu voudras peut-être lever une exception si pop et shift sont appelées sur une List vide.
Source
Un classique de l'informatique.
