Istruzioni
Scrivi una lista doppiamente concatenata usando il Rust unsafe, con un iteratore sulla lista e un cursore per una mutazione efficiente.
La lista doppiamente concatenata è una struttura dati fondamentale dell'informatica.
Ogni nodo di una lista doppiamente concatenata contiene dei dati e i puntatori al nodo successivo e a quello precedente, se esistono.
Nuovi nodi possono essere aggiunti in modo efficiente in qualsiasi punto della lista, se si ha già un riferimento alla posizione. Allo stesso modo, tutti gli elementi di un'altra lista possono essere inseriti in qualsiasi punto in tempo costante.
In Rust, le liste concatenate si usano molto raramente, ma ogni tanto mettono in difficoltà i principianti, quando provano a implementarne una. Spesso scoprono che lavorare con il borrow checker, ancora poco familiare, è più difficile del previsto.
Una nota su unsafe
Ricorda: l'obiettivo del Rust unsafe è scrivere codice sicuro nei casi in cui il compilatore non può aiutarci a garantirne la correttezza. Non deve essere possibile per un utente causare problemi di sicurezza della memoria di alcun tipo usando solo le interfacce sicure che esponiamo.
Documenta gli invarianti critici per la sicurezza che devi mantenere e commenta ogni blocco unsafe spiegando perché è sicuro.
Ogni funzione in cui chi la chiama deve mantenere degli invarianti critici per la sicurezza dovrebbe essere contrassegnata come unsafe. Questo vale anche per le funzioni private.
Passo 1
Implementa le funzionalità per aggiungere e rimuovere elementi (push e pop) all'inizio e alla fine. Questo basta per usare la lista come una coda doppiamente terminata. Implementa anche le funzioni len e is_empty.
Nell'implementazione finale, tutte le modifiche alla lista dovrebbero passare attraverso la struct del cursore, per ridurre al minimo la duplicazione. I metodi push_* e pop_* di LinkedList sono definiti a partire dai metodi richiesti del cursore nel modulo pre_implemented. Se vuoi, per ora puoi saltare la struct Cursor e sovrascrivere i metodi, ma alla fine ripristinali.
Passo 2
Implementa l'iterazione sulla lista dall'inizio alla fine con la struct Iter.
Passo 3
Completa la funzionalità del cursore. Dovrebbe essere in grado di spostarsi in qualsiasi posizione e inserire o rimuovere elementi lì.
Passo 4
Implementa il trait Drop per la LinkedList per liberare le risorse.
Passo 5 (avanzato e opzionale)
I test per queste ultime due cose vengono compilati in modo condizionale tramite il flag di funzionalità advanced. Aggiungi la chiave default = ["advanced"] al file Cargo.toml, sotto [features], per attivarli.
Per dare agli utenti della struttura la massima flessibilità, assicurati che LinkedList<T> sia covariante rispetto a T. Questo significa, per esempio, che una LinkedList<&'static T> può essere usata anche come LinkedList<&'a T>. Vedi il Rustonomicon per una spiegazione della varianza in Rust.
Assicurati che la lista sia sicura da inviare e condividere oltre i confini dei thread e segnalalo al sistema dei tipi implementando manualmente Send e Sync. Questi trait di solito vengono derivati automaticamente, ma qui non sono implementati in modo automatico, a causa dell'uso di puntatori grezzi. Vedi la documentazione di Send e Sync e il capitolo del Rustonomicon che ne parla per maggiori dettagli sulla loro importanza.
