連結リストまみれでRustを学ぶ

何か問題を見つけましたか？または，最終的なコードを一気にチェックしたいですか？すべてGitHubにあります！

訳注: 日本語版のリポジトリはこちらです

注意: 本書の現行版は，rustc 1.31 (2018年12月8日) に初めてリリースされた Rust 2018 に基づいて書かれています． あなたの Rust ツールチェインが十分に新しい場合，cargo new が生成する Cargo.toml ファイルには edition = "2018" (あるいは，あなたが遠い未来に読んでいるなら，もっと大きな数字！) という行が含まれているはずです． 古いツールチェインを利用することも可能ですが，それをすると秘密のハードモードが解除され， 本書の本文ではまったく触れられないコンパイルエラーが発生します．ウワー，楽しそう！

Rustで連結リストを実装するにはどうしたらいいか，という質問をよく受けます．正直なところ，答えはお客様のご要望によりますし，その場ですらすらお答えできるものではありません．そこで，そうした疑問をまとめて解決するためにこの本を書くことにしました．

これから６つの連結リストの実装を通して，Rust でのプログラミングの基礎と応用をまるごとお教えします．あなたが学んでいく内容は以下の通り：

  • 次のポインタ型: &, &mut, Box, Rc, Arc, *const, *mut, NonNull(?)
  • 所有権，借用，継承可変性, 内部可変性，コピー
  • 次のキーワードすべて: 構造体，列挙型，fn, pub, impl, use,...
  • パターンマッチング，ジェネリクス，デストラクタ
  • テスト，新しいツールチェインのインストール，miri の使用
  • アンセーフなRust: 生ポインタ，エイリアス，借用のスタック, UnsafeCell, バリアンス

そう，連結リストというのは本当にやばいものなので，実装しようとするとこういった概念を全部扱わないといけないのです．

すべてサイドバーにありますが（モバイルなら折りたたまれているかもしれませんけど）ご参考までに簡単にこれから作るものを紹介します．

  1. A Bad Singly-Linked Stack
  2. An Ok Singly-Linked Stack
  3. A Persistent Singly-Linked Stack
  4. A Bad But Safe Doubly-Linked Deque
  5. An Unsafe Singly-Linked Queue
  6. TODO: An Ok Unsafe Doubly-Linked Deque
  7. Bonus: A Bunch of Silly Lists

同じ結果を得られるように，私はこれからターミナルで打つコマンドはすべて書き出すつもりです．また開発には Rust の標準パッケージマネージャである Cargo を使うことにします．Cargo を使わなくても Rust プログラムは書けますが，rustc を直接使うよりもずっといいです．ただいじくり回したいだけなら，Rust プレイグラウンドを使ってブラウザ上で実行することもできます．

この後の章では，rustup を使って追加の Rust ツールをインストールしていきます．Rust のツールチェインはすべてrustup を用いてインストールすることを強くお勧めします．

さっそくプロジェクトを作っていきましょう:

> cargo new --lib lists
> cd lists

各リストを別ファイルにまとめ，作業内容が失われないようにします．

次のことは言っておかねばならないでしょう: Rust を本当に学ぶつもりなら，コードを書き，コンパイラに怒られ，それが何を意味するかを理解するということは避けて通れません．皆さんにお見せするために，ふんだんにエラーを出すようにするつもりです．つよい Rust プログラマになるためには，Rust の優れたコンパイラエラーやドキュメントを読み，理解できるようになることがとても重要なのです．

ごめんなさい嘘をつきました．私が実際に遭遇したコンパイルエラーの数はこんなものではなく，ここでお見せするのは氷山の一角です．どの言語でも遭遇するようなコピー&ペーストのエラーなどは紹介していません．これはコンパイラに怒られるためのツアーなのです．

かなりスローペースで進めていくので，正直に言ってまじめな目的にはそぐわないでしょう．プログラミングは楽しくなきゃダメだと思うんです，いやほんとに．もしあなたがきまじめなタイプなら，情報がぱんぱんに詰まったお堅くてきっちりしたものを書いてほしいと思われるかもしれませんが，そんな人のために書いているわけではないんです．あなたは間違ってる．

注意事項

はっきり言っておきますが，私は連結リストが大嫌いです．吐き気を催すほど．連結リストはひどいデータ構造です．もちろん連結リストには以下のようなときには良い選択です:

  • 大きなリストの分割や結合をたくさん，たくさん，たくさん！行いたいとき
  • 同時並行で複数スレッドがロックせずに進行するようなものを書いているとき
  • カーネルまたは埋め込みの開発を行っていて，intrusive list を使いたいとき
  • 純粋な関数型言語を使っているとき．この場合はセマンティクスが限定されているしデータが不変なので，連結リストの扱いが簡単

しかし Rust プログラマにとってはこういったことはすべて超レアなケースです．99% のケースでは Vec (可変長配列，スタック) を使えば済みますし，残りの 1% のケースも VecDeque (両端キュー) で十分です．Vec や VecDeque は割り当ての頻度が少なく，メモリのオーバーヘッドも小さく，真のランダムアクセスとキャッシュの局所性を備えており，ほとんどの場合に適切なデータ構造です．

連結リストはトライ木と同じくらいニッチで，頼りないデータ構造です．トライ木はめったに使用されない構造で，平均的なプログラマが開発の中で使うことはないだろうと主張しても反論はほとんどないと思います．しかし連結リストは奇妙にも名前がよく知られています．学部生の全員が連結リストの書き方を教わりますものね．std::collections の中で私が唯一殺すことができなかったニッチなコレクションなんです．C++ のリストなんですよ！

私たちはコミュニティとして，連結リストを「標準的な」データ構造として認めるべきではないと思います．連結リストはいくつかの場合には素晴らしいデータ構造ですが，それは例外的なケースあって，一般的に有用というわけではありません．

この節の最初の段落を読んだだけで，この本を読むのをやめてしまうひとがいます．例えば，私が2段落目で示した連結リストの素晴らしい使用例の一つを挙げて，反論してこようとするのです．

私に対するいくつかの反論と，それに対する私からの再反論の詳細を以下に示しておきますが，Rust を学びたい方は第1章まで読み飛ばしてください．

パフォーマンスは必ずしも問題ではない

そうですね！ もしかしたら，あなたのアプリは I/O バウンドになっているのかもしれませんし， 問題のコードはめったに呼び出されないどうでもいい部分かもしれません． しかし，それは連結リストを使う理由にはなりません． これは，どんなものでも使うべきだという主張なのです． 連結リストにこだわる理由は何でしょう？ linked hash map (順序つきの辞書) を使えばいいじゃないですか！

パフォーマンスが問題でないのであれば，配列をそのまま使っても 全然 問題ないでしょう．

ポインタがそこにあれば，O(1) 時間で分割・追加・挿入・削除が可能

その通りですね！しかし Bjarne Stroustrup で指摘されているように，この利点は実際には重要ではありません． 配列のすべての要素をコピーするより，連結リストのポインタを取得する方がずっと多くの時間がかかるものだからです． 配列のコピーは実際には非常に高速です．

分割や結合のコストが作業負荷の大半を占めるような場合でない限り， キャッシュ効果やコードの複雑さによって 他のすべて の操作が受けるペナルティが，あらゆる理論的なメリットを上回ってしまいます．

しかしまぁ，分割や結合に多くの時間を費やすようなアプリを開発しているのであれば，連結リストにも利点があるかもしれませんね．

償却の余裕がない

かなりニッチな領域に足を踏み入れているようですね．ほとんどの場合は償却の余裕があります． 確かに，配列は 最悪の場合, 償却されます． 配列を使用しているからといって，コストも償却されているとは限りません． もし格納する要素の数が予測できるなら（あるいは上限を決めておけば），必要なスペースをあらかじめ確保することができます． 私の経験では，必要な要素の数を予測できるのは ごく普通 のことです． 特に Rust では，すべてのイテレータがまさにこのような場合のために size_hint メソッドを持っています．

そうすると, push と pop はまさに O(1) 演算になります． そして，連結リストの push と pop よりもかなり高速になります． ポインタのオフセットを行い，バイトを書き込み，整数をインクリメントします． アロケータの類を使う必要はありません．

低遅延はどうでしょうか？

しかし，そうですね，負荷が予測できない場合は，連結リストを使用することで最悪の場合の遅延を抑えることができるでしょうね！

連結リストはメモリ使用量が少ない

あー，これややこしいんですよね． 「標準的な」配列のリサイズ戦略は，配列の最大半分が空になるように拡大または縮小することです． これは実に多くのスペースを無駄にします． 特に Rust では，（また埋め戻すだけだともったいないから）コレクションを自動的に縮小しませんので， いくらでも多くのスペースが無駄になりえます．

But this is a worst-case scenario. In the best-case, an array stack only has three pointers of overhead for the entire array. Basically no overhead.

Linked lists on the other hand unconditionally waste space per element. A singly-linked list wastes one pointer while a doubly-linked list wastes two. Unlike an array, the relative wasteage is proportional to the size of the element. If you have huge elements this approaches 0 waste. If you have tiny elements (say, bytes), then this can be as much as 16x memory overhead (8x on 32-bit)!

Actually, it's more like 23x (11x on 32-bit) because padding will be added to the byte to align the whole node's size to a pointer.

This is also assuming the best-case for your allocator: that allocating and deallocating nodes is being done densely and you're not losing memory to fragmentation.

But yes, if you have huge elements, can't predict your load, and have a decent allocator, there are memory savings to be had!

I use linked lists all the time in <functional language>

Great! Linked lists are super elegant to use in functional languages because you can manipulate them without any mutation, can describe them recursively, and also work with infinite lists due to the magic of laziness.

Specifically, linked lists are nice because they represent an iteration without the need for any mutable state. The next step is just visiting the next sublist.

Rust mostly does this kind of thing with iterators. They can be infinite and you can map, filter, reverse, and concatenate them just like a functional list, and it will all be done just as lazily!

Rust also lets you easily talk about sub-arrays with slices. Your usual head/tail split in a functional language is just slice.split_at_mut(1). For a long time, Rust had an experimental system for pattern matching on slices which was super cool, but the feature was simplified when it was stabilized. Still, basic slice patterns are neat! And of course, slices can be turned into iterators!

But yes, if you're limited to immutable semantics, linked lists can be very nice.

Note that I'm not saying that functional programming is necessarily weak or bad. However it is fundamentally semantically limited: you're largely only allowed to talk about how things are, and not how they should be done. This is actually a feature, because it enables the compiler to do tons of exotic transformations and potentially figure out the best way to do things without you having to worry about it. However this comes at the cost of being able to worry about it. There are usually escape hatches, but at some limit you're just writing procedural code again.

Even in functional languages, you should endeavour to use the appropriate data structure for the job when you actually need a data structure. Yes, singly-linked lists are your primary tool for control flow, but they're a really poor way to actually store a bunch of data and query it.

Linked lists are great for building concurrent data structures!

Yes! Although writing a concurrent data structure is really a whole different beast, and isn't something that should be taken lightly. Certainly not something many people will even consider doing. Once one's been written, you're also not really choosing to use a linked list. You're choosing to use an MPSC queue or whatever. The implementation strategy is pretty far removed in this case!

But yes, linked lists are the defacto heroes of the dark world of lock-free concurrency.

Mumble mumble kernel embedded something something intrusive.

It's niche. You're talking about a situation where you're not even using your language's runtime. Is that not a red flag that you're doing something strange?

It's also wildly unsafe.

But sure. Build your awesome zero-allocation lists on the stack.

Iterators don't get invalidated by unrelated insertions/removals

That's a delicate dance you're playing. Especially if you don't have a garbage collector. I might argue that your control flow and ownership patterns are probably a bit too tangled, depending on the details.

But yes, you can do some really cool crazy stuff with cursors.

They're simple and great for teaching!

Well, yeah. You're reading a book dedicated to that premise. Well, singly-linked lists are pretty simple. Doubly-linked lists can get kinda gnarly, as we'll see.

Take a Breath

Ok. That's out of the way. Let's write a bajillion linked lists.

On to the first chapter!