Instruções
Escreva uma lista duplamente encadeada usando unsafe em Rust, incluindo um iterador sobre a lista e um cursor para mutação eficiente.
A lista duplamente encadeada é uma estrutura de dados fundamental na ciência da computação.
Cada nó de uma lista duplamente encadeada contém dados e ponteiros para o próximo nó e para o nó anterior, caso existam.
Novos nós podem ser adicionados com eficiência em qualquer ponto da lista, desde que você já tenha uma referência para a posição. Da mesma forma, todos os elementos de outra lista podem ser inseridos em qualquer ponto em tempo constante.
Em Rust, listas encadeadas são usadas muito raramente, mas às vezes pegam os iniciantes de surpresa quando eles tentam implementar uma. Muitas vezes, eles acham inesperadamente difícil lidar com o borrow checker, que ainda não conhecem bem.
Uma observação sobre unsafe
Lembre-se: o objetivo do unsafe em Rust é escrever código seguro nos casos em que o compilador não consegue nos ajudar a garantir a correção. Não pode ser possível que um usuário cause qualquer tipo de insegurança de memória usando apenas as interfaces seguras que expomos.
Documente as invariantes críticas de segurança que você precisa manter e comente cada bloco unsafe explicando por que ele é seguro.
Qualquer função em que quem chama precise manter invariantes críticas de segurança deve ser marcada como unsafe. Isso inclui funções privadas.
Passo 1
Implemente a funcionalidade de adicionar e remover elementos (push e pop) no início e no fim. Isso já basta para usar a lista como uma fila de duas pontas. Implemente também as funções len e is_empty.
Na implementação final, todas as modificações da lista devem ser feitas através da struct do cursor, para minimizar a duplicação. Os métodos push_* e pop_* de LinkedList são definidos em termos dos métodos de cursor necessários no módulo pre_implemented. Se você quiser, pode pular a struct Cursor por enquanto e sobrescrever os métodos, mas reverta isso no final.
Passo 2
Implemente a iteração sobre a lista do início ao fim com a struct Iter.
Passo 3
Complete a funcionalidade do cursor. Ele deve conseguir se mover para qualquer posição e inserir ou remover elementos ali.
Passo 4
Implemente a trait Drop para sua LinkedList para liberar os recursos.
Passo 5 (avançado e opcional)
Os testes para essas duas últimas coisas são compilados condicionalmente através da feature flag advanced. Adicione a chave default = ["advanced"] ao arquivo Cargo.toml, em [features], para ativá-los.
Para dar aos usuários da sua estrutura o máximo de flexibilidade, garanta que sua LinkedList<T> seja covariante em T. Isso significa, por exemplo, que uma LinkedList<&'static T> também pode ser usada como uma LinkedList<&'a T>. Consulte o Rustonomicon para uma explicação sobre variância em Rust.
Garanta que sua lista seja segura para enviar e compartilhar entre limites de threads e sinalize isso ao sistema de tipos implementando Send e Sync manualmente. Essas traits geralmente são derivadas automaticamente, mas aqui não são implementadas automaticamente, por causa do uso de ponteiros brutos. Consulte a documentação de Send e Sync e o capítulo do Rustonomicon sobre elas para detalhes sobre sua importância.
