Was ist der idiomatische Weg, eine verknüpfte Liste mit einem Tail-Zeiger zu schreiben?

Question

Als Lernprojekt für Rust habe ich eine sehr einfache (funktionierende, wenn auch unvollständige) Implementierung einer einfach verknüpften Liste. Die Deklaration der structs sieht wie folgt aus:

type NodePtr<T> = Option<Box<Node<T>>>; 

struct Node<T> { 
    data: T, 
    next: NodePtr<T>, 
} 

pub struct LinkedList<T> { 
    head: NodePtr<T>, 
} 

Implementierung size und push_front beide einigermaßen geradlinig waren, obwohl tun Größe iterativ einige beinhaltete „Kampf mit dem Borge-Checker.“ Das nächste, was ich versuchen wollte, war ein tail Zeiger auf die LinkedList Struktur hinzufügen. um eine effiziente push_back Operation zu ermöglichen. Hier bin ich in eine kleine Mauer gelaufen. Zuerst versuchte ich Option<&Box<Node<T>>> und dann Option<&Node<T>> zu verwenden. Beides führte dazu, dass man überall sträubte, aber immer noch nicht in der Lage war, dem Lebensdauertest zuzustimmen, dass tail gültig wäre.

Ich habe zu dem vorläufigen Schluss, da gekommen, dass es mit diesen Definitionen nicht möglich ist: dass es keine Möglichkeit gibt zu Garantie an den Compiler, die tail in den Orten gültig wäre, dass ich denke, dass es gültig ist. Die einzige Möglichkeit, dies zu erreichen, ist, alle meine Zeiger Rc<_> oder Rc<RefCell<_>> zu haben, denn das sind die einzigen sicheren Möglichkeiten, zwei Dinge auf dasselbe Objekt (den letzten Knoten) zu richten.

Meine Frage: Ist das die richtige Schlussfolgerung? Allgemeiner ausgedrückt: Was ist die idiomatische Rust-Lösung für nicht-pointierte Zeiger in Datenstrukturen? In meinen Augen scheint Referenzzählen für so etwas so schwer zu sein, dass ich etwas verpassen muss. (Oder vielleicht habe ich meine Meinung in die richtige Einstellung nur noch nicht für die Speichersicherheit bekommen.)

Answer 1

Ja, wenn Sie eine einfach verknüpfte-Liste mit einem Schwanz-Zeiger schreiben möchten haben Sie drei Möglichkeiten:

• Sicher und Veränderliche: Verwenden Sie NodePtr = Option<Rc<RefCell<Node<T>>>>
• Sicher und Immutable: Verwenden Sie NodePtr = Option<Rc<Node<T>>>
• Unsichere und Veränderliche: Verwenden Sie tail: *mut Node<T>

Die *mut wird effizienter sein, und es ist nicht wie die Rc geht tatsächlich zu verhindern Sie von der Produktion völlig unsinnigen Staaten (wie Sie richtig abgeleitet). Es wird nur garantieren, dass sie keine segfaults verursachen (und mit RefCell kann es immer noch zu Laufzeitabstürzen führen ...).

Letztendlich hat jede verknüpfte Liste, die komplexer als vanilla single-linked ist, eine Eigentumsgeschichte, die zu komplex ist, um in Rusts Besitzsystem sicher und effizient zu verschlüsseln (es ist kein Baum). Ich persönlich bevorzuge es, die Unsicherheit an diesem Punkt zu akzeptieren und mich auf Komponententests zu stützen, um die Ziellinie in einem Stück zu erreichen (warum schreibe ich eine suboptimale Datenstruktur ...?).