linked list good taste
1.0.0
2016年のTEDインタビュー（14:10）では、Linus Torvaldsは、彼がコーディングで良い味を考えていることについて語っています。例として、彼は単独でリンクされたリストでアイテム削除の2つの実装を提示します（以下に再現します）。最初のアイテムをリストから削除するためには、実装の1つに特別なケースが必要であり、もう1つは特別なケースを必要としません。 Linusは、明らかに後者を好みます。
彼のコメントは次のとおりです。
[...] IFステートメントがない理由を理解してほしくありません。しかし、私はあなたが時々あなたが別の方法で問題を見てそれを書き直すことができることを理解してほしい。 [...] - L. Torvalds
彼が提示するコードスニペットは、Cスタイルの擬似コードであり、従うのに十分なシンプルです。しかし、Linusがコメントで言及しているように、スニペットは概念的な説明を欠いており、よりエレガントなソリューションが実際にどのように機能するかはすぐにはわかりません。
次の2つのセクションでは、技術的アプローチを詳細に調べ、間接的なアドレス指定アプローチがどのように、そしてなぜこれが非常にきれいであるかを示します。最後のセクションでは、ソリューションをアイテムの削除から挿入まで拡張します。
整数の単独でリンクされたリストの基本的なデータ構造を図1に示します。
図1 ：整数の単独でリンクされたリスト。
数字は任意に選択されており、矢印はポインターを示しています。 headタイプlist_item *のポインターであり、各ボックスはlist_item structのインスタンスであり、それぞれが次の項目を指すタイプlist_item *のメンバー変数（コードのnext呼ばれる）を備えています。
データ構造のC実装は次のとおりです。
struct list_item {
int value ;
struct list_item * next ;
};
typedef struct list_item list_item ;
struct list {
struct list_item * head ;
};
typedef struct list list ;（最小）APIも含めます。
/* The textbook version */
void remove_cs101 ( list * l , list_item * target );
/* A more elegant solution */
void remove_elegant ( list * l , list_item * target );それを整備して、 remove_cs101()とremove_elegant()の実装を見てみましょう。これらの例のコードは、Linusの例からの擬似コードに忠実であり、コンパイルや実行もあります。
図2 ：CS101アルゴリズムのリストデータ構造の概念モデル。
void remove_cs101 ( list * l , list_item * target )
{
list_item * cur = l -> head , * prev = NULL ;
while ( cur != target ) {
prev = cur ;
cur = cur -> next ;
}
if ( prev )
prev -> next = cur -> next ;
else
l -> head = cur -> next ;
}標準のCS101アプローチでは、2つのトラバーサルポインターcurとprevを使用して、それぞれリスト内の現在および以前のトラバーサル位置をマークします。 curリストヘッドheadから始まり、ターゲットが見つかるまで進みます。 prevはNULLから始まり、その後、 cur進むたびにcurの以前の値で更新されます。ターゲットが見つかった後、アルゴリズムはprev NULLであるかどうかをテストします。はいの場合、アイテムはリストの先頭になく、削除はcurの周りにリンクされたリストを再ルーティングすることで構成されます。 prevがNULLの場合、 curはリストの最初の要素を指しています。その場合、削除とはリストを前方に移動することを意味します。
よりエレガントなバージョンのコードは少なく、リスト内の最初の要素の削除を扱うために別のブランチを必要としません。
void remove_elegant ( list * l , list_item * target )
{
list_item * * p = & l -> head ;
while ( * p != target )
p = & ( * p ) -> next ;
* p = target -> next ;
}コードは、 headのアドレスから始まるリスト項目へのポインターのアドレスを保持する間接的なポインターpを使用します。すべての反復で、そのポインターは、次のリスト項目へのポインターのアドレス、つまり現在のlist_itemのnext要素のアドレスを保持するために進められます。リストアイテムへのポインターが*p target等しい場合、検索ループを終了し、リストからアイテムを削除します。
重要な洞察は、間接ポインターp使用することには2つの概念的利点があることです。
headポインターを積分部分にデータ構造にする方法で解釈できます。これにより、最初のアイテムを削除するための特別なケースが必要になります。targetを指すポインターを手放すことなく、 whileループの状態を評価することもできます。これにより、 targetを指すポインターを変更し、 prevとcurとは対照的に、単一のイテレーターで逃げることができます。これらの各ポイントを順番に見てみましょう。
headポインターの統合標準モデルは、リンクされたリストをlist_itemインスタンスのシーケンスとして解釈します。シーケンスの開始は、 headポインターからアクセスできます。これは、上記の図2に示されている概念モデルにつながります。 headポインターは、リストの開始にアクセスするためのハンドルと見なされるだけです。 prevとcur 、タイプlist_item *のポインターであり、常にアイテムまたはNULLを指しています。
エレガントな実装では、データ構造に関する異なる見解をもたらす間接的なアドレス指定スキームを使用します。
図3 ：よりエレガントなアプローチでのリストデータ構造の概念モデル。
ここで、 pはタイプlist_item **であり、現在のリスト項目へのポインターのアドレスを保持します。ポインターを前進させるとき、次のリスト項目にポインターのアドレスに転送します。
コードでは、これはp = &(*p)->nextへと変換されます。
(*p) ：現在のリスト項目へのポインターへのアドレスを控除します->next ：そのポインタを再度再審理し、次のリスト項目のアドレスを保持するフィールドを選択します& ：そのアドレスフィールドのアドレスを取得します（つまり、ポインターを取得します）これは、リストがlist_item sのポインターのシーケンスであるデータ構造の解釈に対応します（図3を参照）。
その特定の解釈の追加の利点は、トラバーサル全体を通して現在のアイテムの前身のnextポインターの編集をサポートすることです。
リスト項目へのポインターのアドレスをpすると、検索ループの比較は
while ( * p != target ) *p targetに等しい場合、検索ループは終了します。また、アドレスpを保持しているため、 *p変更することができます。したがって、 targetに達するまでループを繰り返しているにもかかわらず、アイテムを指すポインターを直接変更するために使用できるハンドル（ nextフィールドまたはheadポインターのアドレス）を維持します。
これが、 *p = target->next別の場所を指すために、アイテムへの入ってくるポインターを変更できる理由です。また、アイテムの削除のためにリストを通過するためにprevとcurポインターを必要としない理由です。
remove_elegant()の背後にあるアイデアを適用して、List API： insert_before()に別の関数の特に簡潔な実装を生成し、別のアイテムの前に特定のアイテムを挿入することができます。
まず、 list.hのリストAPIに次の宣言を追加しましょう：
void insert_before ( list * l , list_item * before , list_item * item );この関数は、リストlへのポインター、そのリストのアイテムへbeforeポインター、および関数がbeforeに挿入する新しいリストitemへのポインターを取ります。
先に進む前に、検索ループを別の機能にリファクタリングします
static inline list_item * * find_indirect ( list * l , list_item * target )
{
list_item * * p = & l -> head ;
while ( * p != target )
p = & ( * p ) -> next ;
return p ;
}そして、その機能をremove_elegant()で使用します
void remove_elegant ( list * l , list_item * target )
{
list_item * * p = find_indirect ( l , target );
* p = target -> next ;
}insert_before()の実装find_indirect()を使用すると、 insert_before()実装するのは簡単です。
void insert_before ( list * l , list_item * before , list_item * item )
{
list_item * * p = find_indirect ( l , before );
* p = item ;
item -> next = before ;
}特に美しい結果は、実装にはエッジケースの一貫したセマンティクスがあることです。リストヘッドのポイントbefore 、リストの先頭に新しいアイテムが挿入される場合、 before NULLまたは無効な場合（つまり、アイテムがlに存在しない場合）、新しいアイテムは最後に追加されます。
アイテムの削除のためのよりエレガントなソリューションの前提は、単一の単純な変更です。間接list_item **ポインターを使用して、ポインターをリスト項目に反復します。他のすべてがそこから流れます：特別なケースや分岐は必要ありません。また、ターゲットアイテムを見つけて削除するには、単一のイテレーターで十分です。また、同じアプローチが、一般的なアイテムの挿入と、特に既存のアイテムの前に挿入するためのエレガントなソリューションを提供することがわかりました。
それで、Linusの最初のコメントに戻る：それは良い味ですか？言うのは難しいですが、それは確かに、有名なCSタスクに対する別の、創造的で非常にエレガントなソリューションです。
