ノード構造体についての解説

typedef int data_t;

typedef struct nodetag {
    data_t data;
    struct nodetag *next;
} node_t;

この構造体について，もう少し詳しく解説する．

この定義中の nodetag は構造体タグ名である．
通常，構造体を定義するときには，構造体タグ名は必要不可欠なものではない．しかし，この構造体は，その構造体型 struct notetag 自身を指すポインタ struct nodetag * next をメンバとして含んでいるため，そのことを記述するために，構造体タグ名 nodetag が必要となる．

また， next は次のノードを指すポインタであり，次のノードそのものではない． 次のノードそのものを next にしようとすると， next のタイプは struct node * ではなく strut node になるが，これでは struct node という構造体の中に，それ自身が入ることになり，これは矛盾したものとなる（全体はその一部分と同じにはなれないから）．当然，コンパイルエラーとなる．

ところで，この構造体型を node という型名で定義しているのだから， 次のようにすれば良いのではないか，とも思われる．

typedef int data_t;

typedef struct {
    data_t data;
    node_t * next;
} node_t;

理論的にはこれで合っていて，我々が定義したい構造体は正にこれであるのだが，これではコンパイルエラーとなる．
なぜなら，コンパイラがソースコードを上から見て行き，３行目の node_t * next; を読んだときには，まだ node_t という単語（トークン）が出て来ていなので，これが何なのか，コンパイラにとっては不明であるからである．

これは，Ｃコンパイラが１パスでコンパイルを行うために生じる．１パスとは，コンパイラがソースコードを最初から一度だけ読み込む過程で逐次にコンパイルされたコードを吐き出す，という意味である．したがって，Ｃコンパイラは現在コンパイルしているソースコードの先の方を考慮することはない．（これに対して，パスカルコンパイラのように，２パス型のものもある）

それゆえ，今まさに定義しようとしている構造体を指すために，nodetag という構造体タグ名が定義に先立って必要となるのである．