説明
unsafeなRustを使って双方向連結リストを書きましょう。リストをたどるイテレーターと、効率よく変更するためのカーソルも実装します。
双方向連結リストは、コンピューターサイエンスにおける基本的なデータ構造です。
双方向連結リストの各ノードは、データと、存在する場合は次のノードと前のノードへのポインターを保持します。
その位置への参照をすでに持っていれば、新しいノードはリストの任意の位置に効率よく追加できます。同様に、別のリストのすべての要素を、任意の位置に定数時間で挿入できます。
Rustでは、連結リストが使われることはごくまれですが、初心者が自分で実装しようとしてつまずくことがあります。まだよく知らない借用チェッカーの扱いに、思いのほか苦労しがちです。
unsafeに関する注意
unsafeなRustの目的は、コンパイラーが正しさを保証できない場面で安全なコードを書くことにある、という点を忘れないでください。利用者が、私たちが公開する安全なインターフェースだけを使って、いかなる種類のメモリ安全性の問題も引き起こせないようにしなければなりません。
守るべき安全性上重要な不変条件を文書化し、それぞれのunsafeブロックに、なぜ安全なのかを説明するコメントを付けましょう。
呼び出し側が安全性上重要な不変条件を維持しなければならない関数は、unsafeとしてマークする必要があります。プライベートな関数も同様です。
ステップ1
先頭と末尾で要素を追加・削除する（プッシュとポップ）機能を実装します。これだけで、リストを両端キューとして使えます。あわせて、lenとis_empty関数も実装しましょう。
完成した実装では、重複を最小限に抑えるため、リストへの変更はすべてカーソル構造体を通して行います。LinkedListのpush_*とpop_*メソッドは、モジュールpre_implementedにある必要なカーソルメソッドを土台として定義されています。よければ、今のところはCursor構造体をとばしてこれらのメソッドをオーバーライドしてもかまいませんが、最後には元に戻してください。
ステップ2
Iter構造体を使って、リストを先頭から末尾へたどる繰り返しを実装します。
ステップ3
カーソルの機能を完成させます。任意の位置に移動し、そこで要素を挿入したり削除したりできるようにしましょう。
ステップ4
リソースを解放するために、LinkedListにDropトレイトを実装します。
ステップ5（上級・任意）
この最後の2つのテストは、フィーチャーフラグadvancedによって条件付きでコンパイルされます。有効にするには、Cargo.tomlファイルの[features]の下にdefault = ["advanced"]というキーを追加します。
構造体の利用者に最大限の柔軟性を持たせるために、LinkedList<T>がTに対して共変であることを確認しましょう。これはたとえば、LinkedList<&'static T>をLinkedList<&'a T>としても使えるということです。Rustにおける変性の説明については、Rustonomiconを参照してください。
リストがスレッドの境界を越えて安全に送信・共有できることを確認し、SendとSyncを手動で実装してそのことを型システムに伝えましょう。これらのトレイトは通常は自動導出されますが、生ポインターを使っているため、ここでは自動的に実装されません。その意義の詳細については、SendとSyncのドキュメント、およびそれらについてのRustonomiconの章を参照してください。
