線形リストについておしえてください。

[ちなつ]

単方向リストでダミーありの場合とダミーなしの場合がありますが
これはどういうことですか？
たとえばどんな感じかお願いします。_ _

[beatle]

ダミーは番兵のことだと思います。
番兵についてはこちら http://ja.wikipedia.org/wiki/%E7%95%AA%E5%85%B5

[ちなつ]

返信ありがとうございます。

番兵ですか！
セルなどは関係ないんですか？

[box]

セルなどは関係ないんですか？

何について言及されているのか、よくわからないです。

ところで、ダミーなしのリスト構造の場合、リストの先頭（あるいは末尾の場合もあるかも）に
挿入しようとする際、「挿入したノードを新たな先頭（あるいは末尾）とする」という、
ちょっと特別な処理が入ります。

一方、ダミーありの場合は、実質的な先頭（あるいは末尾）であってもその前（あるいは後ろ）にダミーがあるわけですから、
とにかくリスト構造の「途中に」挿入することだけを考えればよい、というメリットがあります。

[beatle]

「セル」ってなんのことでしょうか？
ドラゴンボールのキャラクタ、エクセルのマス目、細胞など色々意味があります。

仮に、ちなつさんが
http://dixq.net/forum/viewtopic.php?f=3&t=9483
の若槻さんまたは若月さんと同一人物だと仮定すれば、セルは

コード:

struct cell {
    struct cell *next;
    int data;
};

のことですね。
この場合のセルってのは、要するに「リストの要素1つ分」のことです。

番兵ってのは、使わないダミーのセルをリストの最後尾に置いておくことです。
まずは番兵を使わない場合を想像しましょう。

コード:

struct slist {
    struct cell* head;
};
struct slist list;

このリストlistの場合、リストに入っている要素の数が0のとき、list.headをNULLにするのが一般的だと思います。
リストに1つ以上の要素が入ってるとき、list.headは先頭の要素（セル）へのポインタを保持するようにします。

こうすると、リストが空かどうかで、list.headがNULLかそうでないかが変わるので、
いろいろな場所で if (list.head == NULL) { ... } else { ... } などと場合分けしなければ
なりません。

次に番兵を使う場合、リストには初めから一つ、ダミー要素を入れておきます。
そして、リストに要素を追加するときはダミー要素より前に追加するようにします。

こうすると、list.headは絶対にNULLにならず、list.headは常に
「ダミー要素を末尾とするセルの列」
を指し示すことになります。

よって、ifで場合分けする必要がなくなるのです。
これが番兵。

と、書いてるうちにboxさんに先を越されてしまいましたが、せっかく書いたので投稿。

[ちなつ]

詳しい説明ありがとうございました！