1. リストの初歩

リストのアイデアは単純であるが、それ故に非常に柔軟な構造を有している。 最初に述べたように、数が予め分かっていないアドレスをどうやって保有する のかという問題に対する最も簡単は方法がリストであるのだが、ここで重要 なのはアドレスはそれ自体で必要とされるのではなく、確保されたメモリと 共に記憶する必要があるという点である。リストではこれを次のようにして 解決している。つまり、メモリを確保する際に余分にメモリを確保して、 その余分なメモリにアドレスを入れておくのである。勿論、自分自身のアドレス を入れても意味はないので、次のメモリを確保した際に前のメモリオブジェクト 中にその新しく確保したメモリへのアドレスを入れておく。このようにする ことで、先頭のオブジェクトへのアドレスを覚えていれば、次のアドレスは そのオブジェクト中に埋めこまれているので、芋づる式に全てのオブジェクト が探索出来る訳である。この意味において、リストは直線的に繋がっている のであるから、線形リストとも呼ばれる(図 ) 。

図: 片方向リンクトリスト

これを実現するために次のような構造体を定義する。

    struct LIST {
        struct LIST * next;
        char   body[20];
    };

この定義で重要なのは、struct LIST * next; である。通常、構造体 の定義に自分自身を用いてはならないが、この場合はポインタ（つまりアドレス を入れておくための変数）なのでこの限りではない（アドレスの大きさは予め 分かっているから）。 このようにして用意した next には、もしそのオブジェクトが最後のオブジェクト ならば次のデータは存在しないので、例えば NULL を入れておく。 新しいオブジェクトを確保するには常に以下のような関数を呼び出すことで 確保するようにする。 (但し、ここでは簡単のためにデータ本体には配列を使っている。)