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.
Implémentation
Tu vas écrire l'implémentation d'une liste doublement chaînée.
Implémente un Node pour stocker une valeur et des pointeurs vers le nœud suivant et le nœud précédent.
Implémente ensuite une List qui contient des références au premier et au dernier nœud et propose des fonctions pour ajouter et supprimer des éléments.
Ton Node doit avoir les champs et méthodes suivants :
-
Value : la valeur du nœud (on utilisera any).
-
Next() *Node : un pointeur vers le nœud suivant.
-
Prev() *Node : un pointeur vers le nœud précédent.
Tu dois avoir une fonction NewList() qui crée et renvoie une List :
-
NewList(args ...any) *List : crée une nouvelle liste chaînée en préservant l'ordre des valeurs.
Ta List doit avoir les méthodes suivantes :
-
First() *Node : renvoie un pointeur vers le premier nœud (la tête).
-
Last() *Node : renvoie un pointeur vers le dernier nœud (la queue).
-
Push(v any) : insère une valeur à la fin de la liste.
-
Pop() (any, error) : supprime une valeur à la fin de la liste.
-
Unshift(v any) : insère une valeur au début de la liste.
-
Shift() (any, error) : supprime une valeur au début de la liste.
-
Reverse() : inverse la liste chaînée.
Source
Un classique de l'informatique.
