Linuxを生み出したリーナス・トーバルズが考える「優れたコード」とは何か？

この連結リストからあるボックスを消去する処理について、スタンフォード大学の計算機科学講義「Computer Science 101(CS101)」で紹介されていたコードが以下とのこと。

上のコードが行っている処理はこんな感じ。まずはコードの以下の部分で「消去したいボックス」をリストの先頭から探索します。連結リストはリストの先頭からしか値をたどることができないので、まずリスト先頭のボックスのアドレスを「cur」ポインタに格納し、「prev」ポインタはNULLで初期化。curポインタが消去したいボックスのアドレスと一致するまで、curポインタを次のボックスのアドレスへと移しながら照合していきます。

先ほどの処理のイメージを図で表したものが以下。ちょうどprevポインタとcurポインタがリスト後部のボックスへスライドしていくようなイメージです。

curポインタが消去対象のボックスのアドレスと一致したら、次はボックスを消去します。以下の処理では、もし消去対象のボックスがリストの先頭でない場合は、消去対象のボックスの前のボックスが持つnextポインタに消去対象のボックスの次のボックスのアドレスを格納します。消去対象のボックスがリストの先頭である場合は、リストの先頭を指すheadポインタに消去対象のボックスの次のボックスのアドレスを格納します。

消去対象のボックスがリストの先頭でない場合の処理を図で説明するとこんな感じ。消去対象の前のボックスが持つnextポインタが、消去対象の次のボックスを指すようになるため、消去対象のボックスはどのボックスからも参照されなくなり、リストから消去されるというわけです。以下の図では「12」を値に持つボックスが消去されています。

消去対象のボックスがリストの先頭の場合は、以下のようにheadポインタがリストから2つめのボックスのアドレスを指すように処理します。

確かにCS101で紹介されているコードでもリストから要素を削除することは可能。しかし、トーバルズ氏は2016年のTEDでのインタビューにて、さらに優れたコードを紹介しています。

トーバルズ氏によるコードが以下。先ほどのコードにはあったif文が消え、シンプルなコードになっています。

C101のコードとトーバルズ氏のコードの大きな違いは「ボックスのポインタのポインタ」という、新しいポインタ「**p」が導入されている点。まず「**p」は「headポインタのポインタ」として初期化されています。

ボックスのポインタ「*p」が消去対象のボックスのアドレスと一致しない場合は、「次のボックスのポインタのポインタ」に変更。

図に表すとこんな感じで、「ボックスのポインタのポインタ」がリスト後方のボックスへと移動していきます。

消去対象のボックスが見つかるとwhile文を抜け、ボックスのポインタを消去対象の次のボックスのアドレスへと移動させることで、対象のボックスをリストから除外します。

削除処理はこんな感じ。

トーバルズ氏による改善後のコードでは、「ポインタのポインタ」を導入することで、headポインタの状態による条件分岐が不要になっています。また、curとprevの2変数による代入を行う必要もなくなり、処理がシンプルになっています。

トーバルズ氏はTEDのインタビュー内で「時には問題を別の角度から見て、特殊なケースを通常のケースに落とし込んでコードを書き直せることもあるということを理解して欲しいのです、それが優れたコードなのです」とコメント。また、mkirchner氏はトーバルズ氏によるコードを応用したボックスを追加するコードを実装し、GitHubに公開しています。