Instrucciones
Escribe una lista doblemente enlazada usando Rust unsafe, que incluya un iterador sobre la lista y un cursor para modificarla de forma eficiente.
La lista doblemente enlazada es una estructura de datos fundamental en informática.
Cada nodo de una lista doblemente enlazada contiene datos y punteros al nodo siguiente y al anterior, si los hay.
Se pueden añadir nodos nuevos de forma eficiente en cualquier punto de la lista, siempre que ya se tenga una referencia a esa posición. Del mismo modo, todos los elementos de otra lista se pueden insertar en cualquier punto en tiempo constante.
En Rust, las listas enlazadas se usan muy rara vez, pero a veces hacen tropezar a los principiantes cuando intentan implementar una. A menudo les resulta inesperadamente difícil trabajar con el borrow checker, que todavía no conocen bien.
Una nota sobre unsafe
Recuerda: el objetivo del Rust unsafe es escribir código seguro en los casos en que el compilador no puede ayudarnos a garantizar la corrección. No debe ser posible que quien use el código provoque ningún tipo de inseguridad de memoria usando únicamente las interfaces seguras que exponemos.
Documenta los invariantes críticos para la seguridad que debes mantener y comenta cada bloque unsafe explicando por qué es seguro.
Toda función en la que quien llama tenga que mantener invariantes críticos para la seguridad debe marcarse como unsafe. Esto incluye las funciones privadas.
Paso 1
Implementa la funcionalidad para añadir y eliminar elementos (push y pop) por delante y por detrás. Con esto basta para usar la lista como una cola de doble extremo. Implementa también las funciones len e is_empty.
En la implementación final, todas las modificaciones de la lista deben hacerse a través de la estructura del cursor para minimizar la duplicación. Los métodos push_* y pop_* de LinkedList están definidos en términos de los métodos de cursor requeridos en el módulo pre_implemented. Si quieres, puedes saltarte por ahora la estructura Cursor y sobrescribir los métodos, pero vuelve a dejarlos como estaban al final.
Paso 2
Implementa la iteración sobre la lista de principio a fin con la estructura Iter.
Paso 3
Completa la funcionalidad del cursor. Debe poder moverse a cualquier posición e insertar o eliminar elementos allí.
Paso 4
Implementa el trait Drop para tu LinkedList para liberar recursos.
Paso 5 (avanzado y opcional)
Los tests de estas dos últimas cosas se compilan de forma condicional mediante el indicador de funcionalidad advanced. Añade la clave default = ["advanced"] al archivo Cargo.toml, dentro de [features], para activarlos.
Para dar a quienes usen tu estructura la máxima flexibilidad, asegúrate de que tu LinkedList<T> sea covariante respecto a T. Esto significa, por ejemplo, que un LinkedList<&'static T> también puede usarse como un LinkedList<&'a T>. Consulta el Rustonomicon para ver una explicación de la varianza en Rust.
Asegúrate de que tu lista se pueda enviar y compartir entre hilos de forma segura y comunícalo al sistema de tipos implementando Send y Sync manualmente. Estos traits suelen derivarse automáticamente, pero aquí no se implementan de forma automática debido al uso de punteros crudos. Consulta la documentación de Send y Sync y el capítulo del Rustonomicon sobre ellos para obtener más detalles sobre su importancia.
