Liste chaînée

Instructions

Implémente une liste doublement chaînée.

Comme un tableau, une liste chaînée est une structure de données linéaire simple. Plusieurs types de données courants peuvent être implémentés à l'aide de listes chaînées, comme les files, les piles et les tableaux associatifs.

Une liste chaînée est un ensemble d'éléments de données appelés nœuds. Dans une liste simplement chaînée, chaque nœud contient une valeur et un lien vers le nœud suivant. Dans une liste doublement chaînée, chaque nœud contient en plus un lien vers le nœud précédent.

Tu vas écrire une implémentation d'une liste doublement chaînée. Implémente un Node qui contient une valeur et des pointeurs vers les nœuds suivant et précédent. Implémente ensuite une List qui contient des références au premier et au dernier nœud et qui offre une interface semblable à celle d'un tableau pour ajouter et supprimer des éléments :

• push (insérer une valeur à la fin) ;
• pop (supprimer la valeur à la fin) ;
• shift (supprimer la valeur au début).
• unshift (insérer une valeur au début) ;

Pour simplifier ton implémentation, les tests ne couvriront pas les cas d'erreur. Plus précisément : pop et shift ne seront jamais appelés sur une liste vide.

Pour en savoir plus, consulte les listes chaînées sur Wikipédia.