何回かに分けて取り扱うリスト構造の第２回です。 （ 第１回　リスト構造の概要 ）

　リスト構造は、ひとつの要素（エントリやノードなどと呼ばれます）をポインタでつなぐデータ構造です。自分と同じ型の構造体を指すポインタをメンバに持つ自己参照型構造体を使います。

リスト構造のデータ構造を考えるときは

　次のようなことを考えて構造を決めます。

• つなぐ順番（たとえば データの値の小さい順、名前順、ID番号順など）
• 追加データはリストのどこに入れるか（先頭/末尾/データを探してその前または後ろ）
• データの削除はどのようにしたいか（先頭から削除/末尾から削除/データを探して削除）
• データの探し方（たとえば 必ず前から/必ず後ろから/どちらの方向からも同じくらい）

　これらを踏まえ、プログラムで操作しやすいように自己参照型構造体にポインタを用意します。

リスト構造の種類

　１方向のポインタを持つものを「単方向リスト」、前後への２方向のポインタを持つ場合は、「双方向リスト」と呼びます。必ず１方向にデータをたどるなら単方向、逆にたどることもあるなら双方向リストを用います。双方向リストは両方向のポインタを保守するので、プログラムがやや複雑になります。

（単方向リストの例）

typedef struct entry {
    int n;
    struct entry *next; //次のデータを指すポインタ
} ent_t;

　int n; のところを取り扱うデータに応じて任意のメンバとします。
　各データエントリを next ポインタでつなぐ構造は、次の図のようなイメージです。

（双方向リストの例） 逆方向へのポインタも持つと、前にも後ろにもたどれるリストになります。

typedef struct entry {
    int n;
    struct entry *next;  //次のデータを指すポインタ
    struct entry *prior; //前のデータを指すポインタ
} ent_t;

　次の図のようなイメージです。

　上の図のような線形のリストでは、最後のデータが分かるように、その nextポインタに NULL を入れます。 リストの先頭や最後の概念が要らないなら、最後の next ポインタが先頭を指すようにすると環状につながります。 そのような環状リスト（循環リスト）にすると、どのエントリからでもリスト全体をたどることができます。
　リスト構造には、(単方向、双方向)　×　(線形リスト、環状リスト)　の各組合せで計８種類があります。

ほかに必要となる情報

　プログラムでリストをたどるとき、その始まりが分かるようにポインタ変数を用意し、リストの端を覚えます。
　たとえば、構造体を指すポインタ変数head を用意し、常に先頭のデータを指すようにします。

ent_t    *head;

　後ろから参照するなら、同様にリストの末尾を覚える tail を、両方必要な場合は、head と tail を用意します。 環状リストでも出発点が必要です。

　ここまでの検討で、（個々のデータの内容、データのつながり、リストの先頭や最後）が明確なデータ構造を考えることができると思います。

その他の配慮

　リストにまだ何も入っていない空の状態というのがありますね。 そのときと、データがあるときとで処理を分けて書くと、プログラムがゴチャゴチャします。 そこで、先頭はいつでも dummy のデータから始まるものとして、常に同じ処理ができるように書くなどの工夫をすることがあります。

　次回からは、リスト構造の操作例を紹介します。

　　（今回のクイズはありません）

[ 関連記事 ] 第１回）リスト構造の概要, 第３回）リストへの挿入, 第４回）リストからの削除
[ ご案内 ] 構造体やポインタの要点を学習できるコース：要点講座

　　（前回のクイズはありませんでした）