Einführung
Du arbeitest für ein Musik-Streaming-Unternehmen.
Du hast die Aufgabe bekommen, ein Playlist-Feature für deine Musikplayer-App zu entwickeln.
Anleitung
Schreib einen Prototyp einer Musikplayer-Anwendung.
Für den Prototyp wird jeder Song einfach durch eine Zahl dargestellt.
Erstelle aus einem Bereich von Zahlen (den Song-IDs) eine einfach verkettete Liste.
Bei einer einfach verketteten Liste solltest du die Liste umkehren können, um die Songs in umgekehrter Reihenfolge abzuspielen.
Die verkettete Liste ist eine grundlegende Datenstruktur in der Informatik und wird oft bei der Implementierung anderer Datenstrukturen verwendet.
Die einfachste Art der verketteten Liste ist die einfach verkettete Liste.
Das bedeutet, dass jedes Element (oder „Knoten“) Daten enthält, zusammen mit etwas, das auf den nächsten Knoten in der Liste zeigt.
Wenn du tiefer in verkettete Listen eintauchen möchtest, schau dir diesen Artikel an, der sie mit schönen Zeichnungen erklärt.
Wie diese Übung in Python aufgebaut ist
Während stacks und queues mit lists, collections.deque, queue.LifoQueue und multiprocessing.Queue implementiert werden können, erwartet diese Übung einen „Last in, First Out"-(LIFO)-Stack mit einer selbstgebauten einfach verketteten Liste:
Das sollte nicht mit einem LIFO-Stack verwechselt werden, der auf einem dynamischen Array oder einer Liste basiert und darunter eine list, queue oder ein array verwenden kann.
Auf dynamischen Arrays basierende stacks haben eine andere head-Position und eine andere Zeitkomplexität (Big-O) sowie einen anderen Speicherbedarf.
Zu einigen Überlegungen sieh dir diese beiden Stack-Overflow-Fragen an: Array-basierte vs. listenbasierte Stacks und Queues und Unterschiede zwischen Array-Stack, verkettetem Stack und Stack.
Mehr Details zu verketteten Listen, LIFO-Stacks und anderen abstrakten Datentypen (ADT) in Python findest du hier:
Klassen in Python
Die „kanonische" Implementierung einer verketteten Liste in Python erfordert normalerweise eine oder mehrere classes.
Für eine gute Einführung in classes schau dir classes und die begleitende Übung ellens-alien-game an, oder den Abschnitt über Klassen im offiziellen Python-Tutorial.
Spezielle Methoden in Python
Die Tests für diese Übung rufen len() für deine LinkedList auf.
Damit len() funktioniert, musst du eine spezielle Methode __len__ erstellen.
Details zur Implementierung spezieller oder „Dunder"-Methoden in Python findest du unter Python Docs: Grundlegende Anpassung von Objekten und Python Docs: object.len(self).
Einen Iterator erstellen
Damit du deine LinkedList durchlaufen oder umkehren kannst, musst du die spezielle Methode __iter__ implementieren.
Details zur Implementierung findest du unter einen Iterator für eine Klasse implementieren.
Ausnahmen anpassen und auslösen
Manchmal ist es nötig, Ausnahmen in deinem Code sowohl anzupassen als auch sie mit raise auszulösen.
Dabei solltest du immer eine aussagekräftige Fehlermeldung angeben, die angibt, wo die Fehlerquelle liegt.
Das macht deinen Code lesbarer und hilft beim Debuggen erheblich.
Eigene Ausnahmen lassen sich über neue Ausnahmeklassen erstellen (siehe classes für mehr Details), die typischerweise Unterklassen von Exception sind.
Wenn du weißt, dass die Fehlerquelle von einem bestimmten Ausnahme-Typ abgeleitet ist, kannst du von einem der built in error types unter der Exception-Klasse erben.
Wenn du den Fehler auslöst, solltest du trotzdem eine aussagekräftige Meldung angeben.
Diese Übung verlangt, dass du eine eigene Ausnahme erstellst, die ausgelöst/„geworfen" wird, wenn deine verkettete Liste leer ist.
Die Tests bestehen nur, wenn du passende Ausnahmen anpasst, diese Ausnahmen mit raise auslöst und passende Fehlermeldungen angibst.
Um eine generische Ausnahme anzupassen, erstelle eine class, die von Exception erbt.
Wenn du die eigene Ausnahme mit einer Meldung auslöst, schreibst du die Meldung als Argument für den exception-Typ:
# 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.")
