Instrucciones
Escribe una lista doblemente enlazada usando Rust unsafe, que incluya un iterador sobre la lista y un cursor para mutarla de forma eficiente.
La lista doblemente enlazada es una estructura de datos fundamental en las ciencias de la computación.
Cada nodo de una lista doblemente enlazada contiene datos y punteros al siguiente nodo y al anterior, si existen.
Se pueden agregar nuevos nodos de forma eficiente en cualquier punto de la lista, siempre que ya se tenga una referencia a la posición. Asimismo, 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 de vez en cuando tropiezan con los principiantes que intentan implementar una. A menudo les resulta sorprendentemente difícil trabajar con el todavía desconocido verificador de préstamos.
Una nota sobre unsafe
Recuerda que el objetivo de 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 un usuario provoque ningún tipo de inseguridad de memoria usando solo las interfaces seguras que exponemos.
Documenta las invariantes críticas para la seguridad que debes mantener y comenta cada bloque unsafe explicando por qué es seguro.
Toda función en la que quien la llama deba mantener invariantes críticas para la seguridad debe marcarse como unsafe. Esto incluye las funciones privadas.
Paso 1
Implementa la funcionalidad para agregar y quitar elementos (push y pop) al frente y al final. Con esto basta para usar la lista como una cola de doble extremo. También implementa las funciones len e is_empty.
En la implementación terminada, 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 requeridos del cursor en el módulo pre_implemented. Si quieres, puedes omitir la estructura Cursor por ahora y sobrescribir los métodos, pero por favor revierte esos cambios 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 quitar elementos ahí.
Paso 4
Implementa el trait Drop para tu LinkedList con el fin de liberar recursos.
Paso 5 (avanzado y opcional)
Las pruebas para estas dos últimas cosas se compilan de forma condicional mediante la bandera de funcionalidad advanced. Agrega la clave default = ["advanced"] al archivo Cargo.toml bajo [features] para activarlas.
Para dar la máxima flexibilidad a quienes usen tu estructura, asegúrate de que tu LinkedList<T> sea covariante respecto de T. Esto significa, por ejemplo, que un LinkedList<&'static T> también se puede usar como un LinkedList<&'a T>. Consulta el Rustonomicon para obtener una explicación de la varianza en Rust.
Asegúrate de que tu lista sea segura para enviarse y compartirse entre límites de hilos, y comunícalo al sistema de tipos implementando Send y Sync manualmente. Estos traits normalmente se derivan de forma automática, pero aquí no se implementan de forma automática debido al uso de punteros sin procesar. Consulta la documentación de Send y Sync, así como el capítulo del Rustonomicon sobre ellos, para más detalles acerca de su importancia.
