Anleitung
Schreibe eine doppelt verkettete Liste in unsafe Rust, einschließlich eines Iterators über die Liste und eines Cursors für effiziente Mutation.
Die doppelt verkettete Liste ist eine grundlegende Datenstruktur in der Informatik.
Jeder Knoten in einer doppelt verketteten Liste enthält Daten und Zeiger auf den nächsten und den vorherigen Knoten, sofern diese existieren.
Neue Knoten lassen sich effizient an jeder Stelle der Liste einfügen, wenn man bereits eine Referenz auf die Position hat. Ebenso lassen sich alle Elemente einer anderen Liste an jeder Stelle in konstanter Zeit einfügen.
In Rust werden verkettete Listen nur sehr selten verwendet, aber gelegentlich bringen sie Neueinsteiger ins Stolpern, wenn sie versuchen, eine zu implementieren. Oft fällt ihnen der Umgang mit dem noch ungewohnten Borrow-Checker unerwartet schwer.
Ein Hinweis zu unsafe
Denk daran: Das Ziel von unsafe Rust ist es, sicheren Code in Fällen zu schreiben, in denen der Compiler uns nicht helfen kann, die Korrektheit zu garantieren. Es darf nicht möglich sein, dass ein Nutzer allein mit den sicheren Schnittstellen, die wir bereitstellen, irgendeine Form von Speicherunsicherheit verursacht.
Dokumentiere die sicherheitskritischen Invarianten, die du einhalten musst, und kommentiere jeden unsafe-Block und erkläre, warum er sicher ist.
Jede Funktion, bei der der Aufrufer sicherheitskritische Invarianten einhalten muss, sollte als unsafe markiert werden. Das schließt private Funktionen ein.
Schritt 1
Implementiere die Funktionalität zum Hinzufügen und Entfernen von Elementen (Pushen und Poppen) am Anfang und am Ende. Das reicht aus, um die Liste als Deque zu verwenden. Implementiere außerdem die Funktionen len und is_empty.
In der fertigen Implementierung sollten alle Änderungen an der Liste über die Cursor-Struktur erfolgen, um Duplikate zu minimieren. Die Methoden push_* und pop_* auf LinkedList sind über die erforderlichen Cursor-Methoden im Modul pre_implemented definiert. Wenn du möchtest, kannst du die Struktur Cursor vorerst überspringen und die Methoden überschreiben, aber bitte setze sie am Ende wieder zurück.
Schritt 2
Implementiere mit der Struktur Iter die Iteration über die Liste von vorne nach hinten.
Schritt 3
Vervollständige die Funktionalität des Cursors. Er sollte sich an jede Position bewegen und dort Elemente einfügen oder entfernen können.
Schritt 4
Implementiere das Trait Drop für deine LinkedList, um Ressourcen aufzuräumen.
Schritt 5 (fortgeschritten und optional)
Die Tests für diese letzten beiden Dinge werden über das Feature-Flag advanced bedingt kompiliert. Füge den Schlüssel default = ["advanced"] in der Datei Cargo.toml unter [features] hinzu, um sie zu aktivieren.
Damit Nutzer deiner Struktur maximale Flexibilität haben, stelle sicher, dass deine LinkedList<T> kovariant über T ist. Das bedeutet zum Beispiel, dass eine LinkedList<&'static T> auch als LinkedList<&'a T> verwendet werden kann. Eine Erklärung der Varianz in Rust findest du im Rustonomicon.
Stelle sicher, dass deine Liste sicher über Thread-Grenzen hinweg gesendet und geteilt werden kann, und teile das dem Typsystem mit, indem du Send und Sync manuell implementierst. Diese Traits werden normalerweise automatisch abgeleitet, sind hier aber wegen der Verwendung von Raw Pointern nicht automatisch implementiert. Details zu ihrer Bedeutung findest du in der Dokumentation zu Send und Sync sowie im Kapitel im Rustonomicon dazu.
