昔、C 言語のプログラムで、チェーン リストというのを使っていた。こんな感じ。

typedef struct _chainList {
    struct _chainList *next;
    /* その他のデータ
    ...
    */
} ChainList;

ChainList* AllocateChainList(void)
{
    ChainList* ret = (ChainList*) malloc(sizeof(ChainList));
    if (ret != NULL) {
        memset(ret, 0, sizeof(ChainList));
        ret->next = NULL;
    }
    return ret;
}

ChainList* IndexedChainList(ChainList* top, int index)
{
    ChainList* now = top;
    for (int i = 0; i < index; i++) {
        if (now == NULL) {
            return NULL;
        }
        now = now->next;
    }
    return now;
}

void FreeChainList(ChainList* list)
{
    while (list != NULL) {
        ChainList* n = list->next;
        free(list);
        list = n;
    }
}

このコードを見て、「どうして配列で取らないのですか？」と尋ねたことがある。配列だったら、インデックスで指定できるから楽じゃない。ソートも、qsort でできるし。チェーンでするから、これだけをセットでコーディングしなければいけない。

それの答えが、「配列だと、メモリがあるのに取れない場合があるでしょ」だった。？マークが飛び交う中、何のことか、調べることになった。

プログラム コードから使えるメモリには、ヒープとスタックがある。スタックには、ローカル変数が置かれる。malloc で割り当てられるのは、ヒープの方だ。

メモリ マネージャは、割り当ての要求がくると、ヒープの先頭から順番に要求された量だけ割り当てる。こんな感じ。

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

ここに、「3つ分のメモリをください」と要求がくると、3つを割り当てる。

■■■｜□□□□□□□□□□□□□□□□□□□□□□□□□□□

次に、「5つ分のメモリをください」と要求がくると、5つを割り当てる。

■■■｜■■■■■｜□□□□□□□□□□□□□□□□□□□□□□

次に、「10個分のメモリをください」と要求がくると、10個を割り当てる。

■■■｜■■■■■｜■■■■■■■■■■｜□□□□□□□□□□□□

さて、こうして割り当てられたメモリも、いつかは free によって解放される。解放しないと、メモリ リークという状態になるわけだ。では、解放する。

■■■｜■■■■■｜■■■■■■■■■■｜□□□□□□□□□□□□

「5つ分のところがいらなくなりました。返します。」と、要求がくると、5つ分のところを「空き」とマークする。

■■■｜□□□□□｜■■■■■■■■■■｜□□□□□□□□□□□□

さて、この状態で、「3つもらっているところですが、7つに拡張させてください」と要求がくると、どうなるか。つまり、realloc ですね。すると、こうなる。

■■■■■■■｜□｜■■■■■■■■■■｜□□□□□□□□□□□□

さらに、「やっぱり10個分必要なんです」、と要求がくると、こうなる。

□□□□□□□□｜■■■■■■■■■■｜■■■■■■■■■■｜□□

さて、今、メモリすべての容量は30個で、使用しているのは20個。空いているのは10個となっています。この状態で、「１．メモリを5個ください」「２．メモリを10個ください」「３．10個もらっていますが、やっぱり15個必要なんです」という要求があったとき、メモリがもらえるのは、どれ？

ガーベッジコレクタを持っている処理系なら、どれも返してもらえるけど、持っていない処理系では、1のみ。

チェーンでするのは、こういう、「空いているのに空きがない」という状況になりにくいからなんですね。必ず、「1つください」という要求しか出しません。そのため、全部使っていない限り、必ず確保できます。1つの大きさを考慮していませんが、その辺はわかってもらえると思っています。また、再確保時にメモリが移動することで発生するコピーもないため、時間を短縮できます。アドレスがコピーされている場合、アドレスが変わったことで不具合が発生することもありません。

難しいからと敬遠せず、「なぜそうするんだろう？」と考えることが必要ですね。

ついでに書いておく。FreeChainList ですが、次のように書いた場合、同じコンパイラ（VC7.1）を使っても、XP だと希望通り処理してくれますが、Vista では実行時エラーが発生します。コード自体、処理系に強く依存する間違ったコードなので、こんな書き方をしている人は居ないと思いますが、、、居ないと思いたかったけど居たので、念のため。

void FreeChainList(ChainList* list)
{
    while (list != NULL) {
        free(list);
        list = list->next;      // next にアクセスできない
    }
}