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.
Implementierung
Du schreibst eine Implementierung einer doppelt verketteten Liste.
Implementiere einen Node, der einen Wert und Zeiger auf den nächsten und vorherigen Knoten speichert.
Dann implementiere eine List, die Referenzen auf den ersten und letzten Knoten enthält und Funktionen zum Hinzufügen und Entfernen von Elementen bietet.
Dein Node sollte die folgenden Felder und Methoden haben:
-
Value: der Wert des Knotens (wir verwenden any).
-
Next() *Node: Zeiger auf den nächsten Knoten.
-
Prev() *Node: Zeiger auf den vorherigen Knoten.
Du solltest eine Funktion NewList() haben, die eine List erstellt und zurückgibt:
-
NewList(args ...any) *List: erstellt eine neue verkettete Liste, die die Reihenfolge der Werte beibehält.
Deine List sollte die folgenden Methoden haben:
-
First() *Node: gibt einen Zeiger auf den ersten Knoten zurück (Kopf).
-
Last() *Node: gibt einen Zeiger auf den letzten Knoten zurück (Ende).
-
Push(v any): fügt einen Wert am Ende der Liste ein.
-
Pop() (any, error): entfernt einen Wert vom Ende der Liste.
-
Unshift(v any): fügt einen Wert am Anfang der Liste ein.
-
Shift() (any, error): entfernt einen Wert vom Anfang der Liste.
-
Reverse(): kehrt die verkettete Liste um.
Quelle
Klassisches Thema der Informatik
