Einführung
Du arbeitest an einem Projekt, um ein Zugplanungssystem für ein stark befahrenes Schienennetz zu entwickeln.
Du sollst einen Prototyp für die Zugstrecken im Planungssystem entwickeln. Jede Strecke besteht aus einer Abfolge von Bahnhöfen, an denen ein bestimmter Zug hält.
Anleitung
Dein Team hat beschlossen, jede Zugstrecke im Fahrplan durch eine doppelt verkettete Liste darzustellen.
Jeder Bahnhof entlang der Strecke des Zuges wird durch einen Knoten in der verketteten Liste dargestellt.
Du brauchst dir keine Gedanken über Ankunfts- und Abfahrtszeiten an den Bahnhöfen zu machen.
Jeder Bahnhof wird einfach durch eine Zahl dargestellt.
Strecken können erweitert werden, indem du Bahnhöfe am Anfang oder Ende einer Strecke hinzufügst.
Sie können auch verkürzt werden, indem du Bahnhöfe am Anfang oder Ende einer Strecke entfernst.
Manchmal wird ein Bahnhof geschlossen, und in diesem Fall muss er aus der Strecke entfernt werden, auch wenn er nicht am Anfang oder Ende der Strecke liegt.
Die Größe einer Strecke bemisst sich nicht danach, wie weit der Zug fährt, sondern danach, an wie vielen Bahnhöfen er hält.
Die verkettete Liste ist eine grundlegende Datenstruktur in der Informatik und wird oft bei der Implementierung anderer Datenstrukturen verwendet.
Wie der Name schon sagt, ist sie eine Liste von Knoten, die miteinander verknüpft sind.
Sie ist eine Liste von „Knoten“, wobei jeder Knoten mit seinem Nachbarn oder seinen Nachbarn verknüpft ist.
In einer einfach verketteten Liste ist jeder Knoten nur mit dem Knoten verknüpft, der auf ihn folgt.
In einer doppelt verketteten Liste ist jeder Knoten sowohl mit dem Knoten verknüpft, der vor ihm kommt, als auch mit dem Knoten, der nach ihm kommt.
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
Verkettete Listen lassen sich auf verschiedenste Weise und mit verschiedensten zugrunde liegenden Datenstrukturen umsetzen. Wir bitten dich hier jedoch, deine verkettete Liste objektorientiert (OOP) zu implementieren.
In der Stub-Datei siehst du den Anfang einer Node-Klasse sowie einer LinkedList-Klasse.
Deine Node-Klasse sollte sowohl ihren Wert als auch die Knoten verwalten, die ihr vorausgehen oder folgen.
Deine Methoden push, pop, shift und unshift sowie die spezielle Methode für len solltest du in der LinkedList-Klasse implementieren.
Außerdem kann es hilfreich sein, eine spezielle iter-Methode für die Iteration zu implementieren.
Anders als in der Kernübung testen wir hier Fehlerbedingungen, indem wir pop und shift auf leeren LinkedLists aufrufen. Du musst also Fehler passend mit raise auslösen.
Zum Schluss möchten wir, dass du zusätzlich zu den oben genannten Methoden noch delete implementierst.
delete nimmt ein Argument entgegen, nämlich den Wert, der aus der verketteten Liste entfernt werden soll.
Kommt der Wert mehrfach vor, soll nur das erste Vorkommen entfernt werden.
Fehlermeldungen
Manchmal ist es notwendig, eine Exception auszulösen. Dabei solltest du immer eine aussagekräftige Fehlermeldung angeben, die zeigt, woher der Fehler kommt.
Das macht deinen Code lesbarer und erleichtert das Debugging erheblich.
Wenn du weißt, dass die Fehlerquelle von einem bestimmten Typ ist, kannst du einen der eingebauten Fehlertypen auslösen, solltest aber trotzdem eine aussagekräftige Nachricht mitgeben.
In dieser Übung musst du die raise-Anweisung verwenden, um einen ValueError zu „werfen“, wenn ein Knotenwert, der mit delete() gelöscht werden soll, nicht in der verketteten Liste gefunden wird.
Außerdem sollte ein IndexError ausgelöst werden, wenn keine Knoten mehr zum pop() übrig sind.
Die Tests bestehen nur, wenn du diese exceptions mit raise auslöst und ihnen Nachrichten mitgibst.
Um einen ValueError mit einer Nachricht auszulösen, schreibst du die Nachricht als Argument des exception-Typs:
# When the value passed to `delete()` is not found.
if not found:
raise ValueError("Value not found")
Um einen IndexError mit einer Nachricht auszulösen, schreibst du die Nachricht als Argument des exception-Typs:
# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
raise IndexError("List is empty")
Spezielle Methoden in Python
Die Tests für diese Übung rufen außerdem len() auf deiner LinkedList auf.
Damit len() funktioniert, musst du eine spezielle Methode __len__ erstellen.
Details zur Implementierung spezieller bzw. „dunder“-Methoden in Python findest du unter Python Docs: Basic Object Customization und Python Docs: object.len(self).
Wir empfehlen außerdem, eine spezielle Methode __iter__ zu erstellen, die dir beim Iterieren über deine verkettete Liste hilft.
Quelle
Klassisches Thema der Informatik
