構造体に自分自身の型へのポインタをメンバーとして持たせる「自己参照構造体」は，様々な使い方ができる便利なデータ型だ。複数の構造体をポインタで一列につないだ「リスト構造」は，構造体を格納するメモリーを動的に生成することで，いくらでも必要なだけ伸ばしていくことができる。このため，何件のデータが入力されるかわからない場合にも柔軟に対応できる。
さらに，自分自身へのポインタを2個持つ構造体を利用すると，先頭方向にもたどれる「二方向リスト」や，木構造などによる様々なデータ操作が可能になる。今月はそれら自己参照構造体の様々な応用について調査した。
データの個数が不定でも対応できる「リスト」
前回，Cの構造体で作る「リスト」というデータ構造を紹介した。自身の型へのポインタをメンバーとして持つ構造体（「自己参照構造体」と呼ぶ）で構造体同士をつないで構成する（リスト1）。このメンバーには「次の構造体」を指し示す値を格納していく。先頭の構造体から順に「次の構造体」を示すメンバーをたどることで，すべての構造体を次々とたどっていくことができるわけだ（図1）。
typedef struct _staff {
int id; /* 社員ID */
char name[20]; /* 氏名 */
～略～ /* その他のデータ */
struct _staff *next; /* staffへのポインタ */
} staff;
しかし，今来た道を戻る――逆にたどる――ことはできない。例えば，あるメンバーの値が100である構造体を知ることは，リストを先頭から調べていけば判明する。さらに，その次の構造体の同じメンバーの値もすぐにわかる。が，当該構造体の一つ前の構造体を調べることはできない。配列で言えば，添え字を加算することはできても，減算して前に戻ることができない状態である。
前後につながりを持たせる「二方向リスト」
そこで，「次の構造体」を示すポインタnextに加えて，「一つ前の構造体」へのポインタprevもメンバーに持つ構造体を考えてみる（リスト2）。このような構造体でリストを作れば，メンバーprevを頼りにして，リストを逆方向にもたどれるようになる（図2）。これを「二方向リスト」と呼ぶ。
typedef struct _staff {
struct _staff *prev; /* 前の構造体を示すポインタ */
int id; /* 社員ID */
char name[20]; /* 氏名 */
～略～ /* その他 */
struct _staff *next; /* 次の構造体を示すポインタ */
} staff;
