でTED 2016でのインタビュー（14:10）、Linus Torvalds氏は語る良いコーディングスタイル。例として、彼は単一リンクリストから要素を削除するための2つのオプションを提供します（以下を参照）。最初のオプションには特別なケースがありますが、他のオプションにはありません。Linusは後者を好みます。

彼のコメント：

[...]ここにifステートメントがない理由を考える必要はありません。問題を別の観点から見て、特殊なケースが消えて通常のケースになるように書き直すことが重要です。これは良いコードです。-L。Torvalds

Linusは、例としてかなり単純なCスタイルの疑似コードを示しています。ただし、概念的な説明は提供していません。したがって、間接ポインタがどのように機能するかはすぐにはわかりません。

このソリューションとその利点を詳しく見てみましょう。ボーナスとして、削除だけでなく、間接アドレス指定による要素の挿入も表示されます。

コード

単一リンクされた整数のリストの基本的なデータ構造を図1に示します。1.

図。1.単一にリンク

された整数のリスト数値はランダムに選択された整数値であり、矢印はポインターに対応します。-head

これはタイプポインターでありIntListItem*

、すべてのブロックは構造のインスタンスでありIntListItem

、それぞれが次の要素を指すnext

タイプの独自の変数（コード内）を持ちますIntListItem*

。

Cでのデータ構造の実装：

struct IntListItem {
    int value;
    struct IntListItem* next;
};
typedef struct IntListItem IntListItem;

struct IntList {
    IntListItem* head;
};
typedef struct IntList IntList;

また、（最小限の）API：

/* The textbook version */
void remove_cs101(IntList* l, IntListItem* target);
/* A more elegant solution */
void remove_elegant(IntList* l, IntListItem* target);

それでは、実装remove_cs101()

とを見てみましょうremove_elegant()

。例のコードは、Linusの例の疑似コードと矛盾しませんが、コンパイルして実行します。

ベーシックバージョン

図：2.基本アルゴリズムにおけるリストデータ構造の概念モデル

void remove_cs101(IntList *l, IntListItem *target)
{
    IntListItem *cur = l->head, *prev = NULL;
    while (cur != target) {
        prev = cur;
        cur = cur->next;
    }
    if (prev) {
        prev->next = cur->next;
    } else {
        l->head = cur->next;
    }
}

標準的なアプローチでは、リスト内の現在と前のトラバーサル位置をそれぞれマークする2つのトラバーサルポインターcur

とprev

。cur

リストの先頭から開始し、head

ターゲットが見つかるまで前に進みます。次に、それprev

は最初に始まり、NULL

その後、cur

前進するたびに前の値に更新されます。ターゲットが見つかると、アルゴリズムはそれがprev

ゼロでないかどうかをチェックします。その場合cur

、リストの最初の項目を指します。その場合、削除とはリストの先頭を前方に移動することを意味します。

よりエレガントなソリューション

よりエレガントなバージョンはコードが少なく、リストの最初の項目を削除するために別のブランチを必要としません。

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) != target) {
        p = &(*p)->next;
    }
    *p = target->next;
}

このコードは、p

アドレスで始まるリストアイテムへのポインタのアドレスを含む間接ポインタを使用しますhead

。各反復で、このポインターは、リスト内の次のアイテムへのポインターのアドレス、つまりnext

現在のアイテム内のアイテムのアドレスを含むように展開されますIntListItem

。リストアイテムへのポインタ(*p)

が等しい場合target

、検索ループを終了し、リストからアイテムを削除します。

使い方？

間接ポインタには、p

2つの概念上の利点があります。

ポインタhead

がデータ構造の不可欠な部分になるように、リンクされたリストを解釈できます。これにより、最初のアイテムを削除するための特別なケースが不要になります。
また、をwhile

指すポインタを離さなくても、ループの状態を評価できますtarget

。これは、あなたがへのポインタを変更することができますtarget

とは異なり、単一のイテレータで周りを取得prev

してcur

。

各項目を順番に見ていきましょう。

ヘッドポインターの統合

標準モデルは、リンクされたリストを一連のインスタンスとして解釈しますIntListItem

。シーケンスの開始は、ポインタを使用して取得できますhead

。これにより、図に示す概念モデルが導き出されます。 2.ポインタはhead

、リストの先頭にアクセスするためのハンドルとして扱われます。prev

およびcur

はタイプポインタでIntListItem*

あり、常にまたはを指しますNULL

。

エレガントな実装では、間接アドレス指定スキームを使用します。これにより、データ構造の異なるビューが得られ

ます。 3.より洗練されたソリューションにおけるリストデータ構造の概念モデル

ここでp

は、タイプを表しますIntListItem**

現在のリストアイテムへのポインタのアドレスが含まれています。ポインタが前方に移動すると、そのアドレスは次の要素に変わります。

コードでは、次のようになりますp = &(*p)->next

。

(*p)

：現在のリストアイテムへのポインタのアドレスを逆参照します。
->next

：このポインタを再度参照解除し、次の要素のアドレスを持つフィールドを選択します。
&

：このフィールドのアドレスを取得します（つまり、このフィールドへのポインターを取得します）。

これは、データ構造の解釈に従います。ここで、リストは要素への一連のポインターですIntListItem

（図3）。

仕上げタッチ

この特定の解釈の追加の利点は、トラバーサル全体でnext

現在の要素の前の要素のポインターを編集できることです。リストの要素へのポインタのアドレスが含まれている

場合p

、検索ループでの比較は次のようになります。

while ((*p) != target) {
    ...
}

(*p)

等しい場合target

、検索サイクルは終了(*p)

しますp

。これが発生するとすぐに、アドレスを保持しているため、を変更できます。したがって、ループが最後まで繰り返されても、要素へのポインタを直接変更するために使用できる記述子（フィールドアドレスnext

またはポインタhead

）が格納されます。

そのため、を使用して、要素ポインターへの入力を変更して別の場所を指すようにする*p = target->next

ことができます。したがって、バイパスポインターprev

を使用cur

したり、アイテムを削除したりする必要はありません。

新しいアプリ

同じアイデアを、リンクされたリスト内のさらに別の関数の非常に簡潔な実装に適用できることがわかりましたinsert_before()

。つまり、この要素を別の要素の前に挿入します。

既存の要素の前に挿入

まず、次の宣言をに追加しましょうlist.h

：

void insert_before(IntList *l, IntListItem *before, IntListItem *item);

関数は、リストlへのポインター、このリスト内の項目の前のポインター、および関数がその前に挿入する新しいリスト項目へのポインターを取ります。

高速リファクタリング

先に進む前に、検索ループを別の関数にしましょう。

static inline IntListItem **find_indirect(IntList *l, IntListItem *target)
{
    IntListItem **p = &l->head;
    while ((*p) && (*p) != target) {
        p = &(*p)->next;
    }
    return p;
}

で使用しremove_elegant()

ます：

void remove_elegant(IntList *l, IntListItem *target)
{
    IntListItem **p = find_indirect(l, target);
    *p = target->next;
}

Insert_before（）の実装

find_indirect()

それを使用すると実装が簡単insert_before()

です：

void insert_before(IntList *l, IntListItem *before, IntListItem *item)
{
    IntListItem **p = find_indirect(l, before);
    *p = item;
    item->next = before;
}

特に喜ばしいのは、エッジケースの堅実なセマンティクスです。before

リストの先頭を指している場合、新しい要素が最初に挿入され、before

nullまたは無効（つまり、に存在しないl

）の場合、新しい要素が最後に追加されます。

結論

要素を削除するためのより洗練されたソリューションの前提条件は、1つの簡単な変更ですIntListItem**

。つまり、リスト要素へのポインターを反復処理するための間接ポインターです。他のすべてはそこから流れます。特別なケースやブランチは必要ありません。ターゲット要素を見つけて削除するには、1つのイテレーターで十分です。そして、同じアプローチが、一般的に挿入し、特に既存の要素の前に挿入するための洗練されたソリューションを提供することがわかりました。

それで、ライナスの最初の発言に戻って、これは良い味の指標ですか？言いにくい。しかし、よく知られている問題には明らかに創造的で非常にエレガントな解決策があります。

リンクされたリスト、ポインターのトリック、そして良い味

コード