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.
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.
Du schreibst eine Implementierung einer doppelt verketteten Liste.
Implementiere einen Node, der einen Wert und Zeiger auf den nächsten und vorherigen Knoten enthält.
Implementiere dann eine LinkedList, die Referenzen auf den ersten und letzten Knoten hält und eine array-ähnliche Schnittstelle zum Hinzufügen und Entfernen von Elementen bietet:
push (Wert hinten einfügen);pop (Wert hinten entfernen);shift (Wert vorne entfernen);unshift (Wert vorne einfügen);delete (den ersten passenden Knoten entfernen)Um deine Implementierung einfach zu halten, decken die Tests keine Fehlerfälle ab. Konkret: pop oder shift werden nie auf einer leeren Liste aufgerufen.
Melde dich bei Exercism an, um Tcl mit 135 Übungen und echtem menschlichen Mentoring zu lernen und zu meistern, alles kostenlos.