Introduction
Tu travailles pour une entreprise de streaming musical.
On t'a confié la création d'une fonctionnalité de playlist pour ton lecteur de musique.
Instructions
Écris le prototype d'une application de lecteur de musique.
Pour ce prototype, chaque chanson sera simplement représentée par un nombre.
À partir d'une plage de nombres (les identifiants des chansons), crée une liste simplement chaînée.
À partir d'une liste simplement chaînée, tu dois pouvoir inverser la liste pour lire les chansons dans l'ordre inverse.
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.
Le type de liste chaînée le plus simple est la liste simplement chaînée.
Cela signifie que chaque élément (ou « nœud ») contient une donnée, ainsi qu'une référence qui pointe vers le nœud suivant de la liste.
Si tu veux approfondir les listes chaînées, jette un œil à cet article qui les explique à l'aide de jolis schémas.
Bien que les stacks et les queues puissent être implémentés à l'aide de lists, collections.deque, queue.LifoQueue et multiprocessing.Queue, cet exercice attend une pile « dernier entré, premier sorti » (LIFO) reposant sur une liste simplement chaînée faite maison :
Il ne faut pas la confondre avec une pile LIFO reposant sur un tableau dynamique, qui peut s'appuyer en interne sur une list, une queue ou un array.
Les stacks basées sur un tableau dynamique ont une position de head, une complexité temporelle (Big-O) et une empreinte mémoire différentes.
Consulte ces deux questions sur Stack Overflow pour quelques points de réflexion : Piles et files basées sur un tableau vs sur une liste et Différences entre pile sur tableau, pile chaînée et pile.
Pour plus de détails sur les listes chaînées, les piles LIFO et les autres types de données abstraits (ADT) en Python :
Les classes en Python
L'implémentation « canonique » d'une liste chaînée en Python nécessite généralement une ou plusieurs classes.
Pour une bonne introduction aux classes, consulte classes et l'exercice complémentaire ellens-alien-game, ou la section sur les classes du tutoriel officiel de Python.
Les méthodes spéciales en Python
Les tests de cet exercice appelleront 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 la documentation Python : personnalisation de base des objets et la documentation Python : object.len(self).
Construis un itérateur
Pour pouvoir parcourir ou inverser ta LinkedList, tu devras implémenter la méthode spéciale __iter__.
Consulte implémenter un itérateur pour une classe pour les détails d'implémentation.
Personnalise et lève des exceptions
Il est parfois nécessaire à la fois de personnaliser et de raise des exceptions dans ton code.
Quand tu le fais, tu dois toujours inclure un message d'erreur explicite indiquant quelle est la source de l'erreur.
Cela rend le code plus lisible et aide beaucoup lors du débogage.
On peut créer des exceptions personnalisées au moyen de nouvelles classes d'exception (voir classes pour plus de détails), qui sont généralement des sous-classes de Exception.
Dans les cas où tu sais que la source de l'erreur sera dérivée d'un certain type d'exception, tu peux choisir d'hériter de l'un des built in error types sous la classe Exception.
Au moment de lever l'erreur, tu dois quand même inclure un message explicite.
Cet exercice particulier demande de créer une exception personnalisée qui sera levée ou « lancée » quand la liste chaînée est vide.
Les tests ne réussiront que si tu personnalises les exceptions appropriées, que tu raise ces exceptions et que tu inclus des messages d'erreur appropriés.
Pour personnaliser une exception générique, crée une class qui hérite de Exception.
Quand tu lèves l'exception personnalisée avec un message, écris ce message comme argument du type exception :
# subclassing Exception to create EmptyListException
class EmptyListException(Exception):
"""Exception raised when the linked list is empty.
message: explanation of the error.
"""
def __init__(self, message):
self.message = message
# raising an EmptyListException
raise EmptyListException("The list is empty.")
