linked list - simples - ¿Cuál es la forma idiomática de escribir una lista vinculada con un puntero de cola?

listas simples estructura de datos

Question

Como un proyecto de aprendizaje para Rust, tengo una implementación muy simple (trabajando, si no completa) de una lista individualmente vinculada. La declaración de las estructuras se ve así:

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

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

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

El size implementación y el push_front fueron bastante sencillos, aunque el tamaño iterativo implicó algunas "peleas con el corrector de préstamos".

Lo siguiente que quise probar fue agregar un puntero de tail a la estructura LinkedList . para habilitar una operación push_back eficiente. Aquí me encontré con un poco de una pared. Primero intenté usar Option<&Box<Node<T>>> y luego Option<&Node<T>> . Ambos llevaron a rociar ''a s en todas partes, pero todavía no pueden prometerle al verificador de por vida que la tail sería válida.

Desde entonces llegué a la conclusión provisional de que es imposible con estas definiciones: que no hay forma de garantizarle al compilador que la tail sería válida en los lugares que creo que es válida. La única forma en que puedo lograr esto es hacer que todos mis punteros sean Rc<_> o Rc<RefCell<_>> , porque esas son las únicas formas seguras de tener dos cosas apuntando al mismo objeto (el nodo final).

Mi pregunta: ¿es esta la conclusión correcta? En términos más generales: ¿cuál es la solución idiomática de Rust para los indicadores sin propietario dentro de las estructuras de datos? En mi opinión, el recuento de referencias parece demasiado pesado para algo tan simple, así que creo que me falta algo. (O quizás todavía no me he metido en la mentalidad correcta para la seguridad de la memoria).

Answer 1

Sí, si desea escribir una lista enlazada individualmente con un puntero de cola, tiene tres opciones:

• Seguro y mutable: use NodePtr = Option<Rc<RefCell<Node<T>>>>
• Seguro e Inmutable: Use NodePtr = Option<Rc<Node<T>>>
• Inseguro y mutable: utilice la tail: *mut Node<T>

The *mut va a ser más eficiente, y no es como si el Rc verdad fuera a evitar que usted produzca estados completamente sin sentido (como dedujo correctamente). Solo va a garantizar que no causen segfaults (y con RefCell aún puede causar bloqueos en tiempo de ejecución ...).

En definitiva, cualquier lista vinculada más compleja que vanilla con enlaces únicos tiene una historia de propiedad que es demasiado compleja para codificar en el sistema de propiedad de Rust de manera segura y eficiente (no es un árbol). Yo personalmente prefiero abrazar la inseguridad en ese punto y apoyándome en pruebas unitarias para llegar a la línea de llegada de una sola pieza (¿por qué escribir una estructura de datos subóptima ...?).