あまりにも超大量の連結リストで学ぶRust

困ったことがあったり，最終的なコードを全部見たいときはGithubを見てください！
訳に関する文句などはこちら

注意: この本は rustc 1.31 (Dec 8, 2018) でリリースされた Rust 2018 向けに書かれています．もしあなたのRustツールチェインが十分に新しければ，cargo new で作られた Cargo.toml ファイルはedition = "2018"という行を含んでいるはずです（もしあなたが遠い未来にこれを読んでいるなら，もっと新しい数字かもしれません）．古いツールチェインを使うこともできますが，秘密のハードモードが解除され，あなたはこの本に全く書かれていないコンパイルエラーに見舞われるでしょう．楽しそうですね．

私はよくRustでの連結リストの実装について質問を受けます．正直答えはあなたの要件によりますし，その場合ごとのちょうどいい答えを出すのは明らかに簡単ではありません．そんなわけで，そういった質問に一発でまるっと答えられるようにこの本を書きました．

この本では，6つの連結リストの実装を通してRustのプログラミングを基本から応用までお教えします．あなたはこんなことを学ぶでしょう：

ポインタ型：&, &mut, Box, Rc, Arc, *const, *mut
所有権，借用，継承可変性，内部可変性，Copy
用語：struct, enum, fn, pub, impl, use, ...
パターンマッチング，ジェネリクス，デストラクタ
テスト
unsafeの基本

そう，連結リストはこれ全部に触れなくては実装できないくらい本当に恐ろしい代物です．

サイドバーにありますが（モバイルデバイスで見ると畳まれてるかも），こういうものを実装します：

皆さんがちゃんとついてこられるように，私がターミナルに入力するコマンドは全部書いておきます．パッケージマネージャーもRust標準のCargoを使います．Cargoは Rustを書くのに必要不可欠というわけではありませんが，rustcディレクトリを使うよりかなりいいです．ちょっとRustを試してみるくらいのつもりなら， play.rust-lang.orgでブラウザから簡単なコードを実行することもできます．

では手始めにプロジェクトを作りましょう:

> cargo new --lib lists
> cd lists

作ったものに上書きしてしまわないように，それぞれのリストを別々のファイルに作ります．

本物のRustの学習には，コードを書いて，コンパイラにクソ怒られて，それが何を意味するかを解き明かそうとする体験がつきものです．私はそうした状況がなるべく沢山起こるようにしました．Rustのコンパイラが出す（たいてい）有用なエラーメッセージを読んで理解することは，能力あるRustプログラマになるために超重要なことです．

...というのは実は嘘です．これを書く間，私はお見せするよりずっとたくさんのコンパイルエラーにぶち当たりました．特に後ろの方の章ではどんな言語でもあるようなタイプミス/コピペミスのエラーをいちいち見せていません．これはコンパイラに怒られるコースをゆくガイド付きツアーです．

このツアーはゆっくり進みます．そして，正直なところクソ真面目にやるつもりはすこしもありません．プログラミングは楽しいものですよね，クソが！もしあなたが冗長さを嫌う，まじめで格式高い方ならこの本はあなた向きではありません．私が作る何もかもがあなた向きではありません．あなたの人生は間違っています．

どうしても要る公共広告

まず100%はっきりさせておきましょう．私は連結リストが大嫌いです．心の底から．連結リストはマジでひどいデータ構造です．もちろん連結リストが有用な場合もあります：

長大なリストを何回も分割したりくっつけたりするとき．何回も．
めっちゃすごいLockしたりFreeしたりする同期処理をするとき．
侵入型¹リストを使ってカーネルや組み込み系を実装するとき．
純粋な関数型言語を使っていて，セマンティクスが限定されていて可変性がないので連結リストが使いやすいとき．
... とか！

でも上のような場合はRustを書く人にとってはごくまれです．99%の場合Vec（配列スタック）でいいですし，残った1%のうちの99%はVecDeque（配列両端キュー）でいいです．Vecや VecDequeはメモリ割当頻度が少なく，メモリオーバーヘッドが小さく，ランダムアクセスができ，キャッシュ局所性があり，明らかにより優れたデータ構造です．

連結リストはトライ木と同じくらいニッチなデータ構造です．トライ木がニッチじゃないと言ってくる人はほとんどいないでしょう．あなたがエンジニアとしてやっていく分には一生学ばなくてすむのですから．それにもかかわらず連結リストはなぜか優遇されています．私達は学生達全員に連結リストの書き方を教えています．私はこいつだけを std::collectionsから消し損ないました．C++ではリストといえばこいつです！

私達は団結して連結リストが標準的なデータ構造として扱われることに反対すべきです．特定の状況ではいいデータ構造ですが，そういう状況は例外的で，誰もが遭遇するわけではありません．

何人かの人はこの公共広告の１段落目で読むのをやめて，私が挙げた連結リストの 素晴らしい用法を持ち出して私に反論しようとするでしょう．それは次の段落に書いてあるっての！

詳細な議論のために，私が今まで見た反論とそれに対する回答を書いておきます． Rustを学びたい方は遠慮なく一章へどうぞ！

パフォーマンスがいつも重要なわけじゃないだろ

そうですね！多分あなたのアプリケーションにI/O待ちがあるとか，とにかく関係ない感じなんでしょう．でもそれは連結リストを使うかどうかという問題じゃないですよね．それはあらゆるものを使うかどうかという問題です．なんで連結リストを使うんですか？連結ハッシュマップを使いましょう！

パフォーマンスが関係ないならもちろん素の配列を使ってもいいはずです．

ポインタを握ってればO(1)で分割して連結して挿入して削除できるじゃん

はい！Bjarne Stroustrup氏が書かれているように，これは実はどうもいいことです．ポインタを取得する時間が配列の要素を全部コピーする時間より大して速くない場合には．そして配列のコピーはかなり速いです．

分割・連結のコストがめちゃくちゃ大きくない限り，他のあらゆる操作がキャッシュやコードの煩雑さによってダメダメになり，長所を消してしまいます．

でもそうですね，もしあなたのアプリケーションが配列の分割・連結に大きな時間を使っているなら連結リストを使ううま味があるでしょう．

償却 2 する余裕ないんだけど

あなたはすでにニッチな話をしています――ほとんどの人は償却の余裕があります．しかも配列が償却されるのは最悪の場合で，あなたが配列を使うからと言って必ず償却が行われるとは限りません．配列の要素数を予め知ることができるなら（そうでなくても要素の上限を知ることができるなら）必要なメモリ空間をとっておくことができます．経験上，要素数を予め知ることはたいていできます．特にRustではすべてのイテレータがこのためのメソッドsize_hintを持っています．

この前提に立てば，pushとpopは例外なくO(1)の操作で，連結リストのpushとpop よりかなり速い操作になります．ただポインタを動かして，バイトデータを書き込んで， Integerをインクリメントすればいいだけです．データを割り当てる必要なんかありません．

で，連結リストが低遅延だから使うんでしたっけ？

でももしデータ長が予測できないなら，連結リストで償却を回避できます！

連結リストは消費メモリが少ない

うーん，これはちょっと込み入った話ですね．「標準的な」配列のリサイズ戦略は配列の半分が空になるように伸縮することです．たしかにこれは相当なメモリ空間を無駄にしています．特にRustでは，collectionの要素を削除しても自動的に縮めたりしません（なのでもう一度詰め込まない限り無駄になります）．したがって無駄にしてるメモリ空間と時間の積は無限に膨れていきます！

しかしこれは最悪の場合です．最良の場合では，配列スタックはたった3つのポインタぶんのオーバーヘッドしかありません．基本的にはないと言っていいでしょう．

一方で連結リストは，無条件に要素一個ごとにオーバーヘッドがあります．片方向リストではポインタ1つ，双方向リストではポインタ2つ分です．この場合配列と違い，オーバーヘッドの割合は要素のデータサイズと関係してきます．もしリストの要素がどデカい場合，オーバーヘッドはほぼ無視できるでしょう．一方要素が小さい場合（1バイトとか），ポインタのオーバヘッドは要素自体の 16倍です！（要素が32bitのときは8倍です）

実際は要素全体の長さを揃えるためパディングが付加されるので23倍（32bitのとき11倍）のことが多いでしょう．

ところでこれはアロケータの動きが最良の場合です．つまり，メモリの割当と解放が密に行われ，断片化によってメモリが無駄にならない場合です．

でも，そうです．もしバカでかい要素を扱っていて，操作の頻度が予測できて，賢いアロケータを使っているなら，メモリを節約できるでしょう！

いつも<関数型言語>で連結リスト使ってたんだよね

いいですね！連結リストは関数型言語では超いいですよね．ミューテーションなしで操作できて，再帰的に表現できて，遅延評価の魔法のおかでげで無限長のリストを扱えます．

特に優れている点は状態を持たずにイテレーションができる点です．イテレーションの次のステップに行くためにはただ次のノードに行けばよいのです．

しかし，Rustでは配列のパターンマッチができて，スライスを使って配列のサブセットを扱うことができることは言っておくべきでしょう．これらの機能は実際関数型言語のリストより表現の幅が大きいです．なぜなら配列の最後の要素や，「ある配列の最初と最後と最後から二番目の要素を除いた配列」などの狂った表現をを何でも扱えるからです．

でもスライスでリストを作ることができないのは確かです．分割することしかできません．

遅延評価についてはイテレータがあります．イテレータは無限の要素を持てて， map，filter，reverse，結合などの操作を関数型のリストのように行なえますし，これらの操作全てに遅延評価が適用されています．驚かないでいただきたいのですがスライスはすべてイテレータとして扱うことができます．

でもそうです．もし不変のセマンティクスしか使えなければ，連結リストはとてもよい選択でしょう．

誤解しないでいただきたいのですが，関数型言語が必ずしも雑魚いとか悪いとか言っているわけではありません．しかし基本的にセマンティクスが制限されているのは事実です．関数型言語においては，あるものがどのようであるかについて記述できますが どのように行われるかについて記述することができません．これは機能であり，それによっていろいろな変テコな操作ができるようになったり，あなたを煩わせることなく物事を成し遂げる最良の手段を取ることができるようになったりします．しかし，それはあなたの手を煩わせることができるという選択肢と引き換えに，です．たいてい緊急回避手段がありますが，そうでなければ手続き型コードを書くことになるでしょう．

関数型言語といえども，目的にあったデータ構造を選択する努力は行われるべきです．確かに片方向連結リストは制御フローの記述には適していますが，データを保存して検索するという目的には本当に向いていません．

連結リストは並列データ構造を作るのに適している！

そうですね！並列データ構造を書くということはまた別の問題であり，軽い問題でもありませんが，明らかに多くの人にとっては取り組もうとは思いもしないことでしょう．そして一度実装してしまったら，あなたは連結リストではなくMPSCキュー³なりなんなりを使うことになります．この場合連結リストはどっか遠くに行ってしまっています！

でもそうですね，並列処理の暗黒の世界において，連結リストは実績あるヒーローです．