Cプログラマへの道 #8

ヒープのメモリ断片化

スタックは変数の型と削除されるタイミングを知ることでメモリの断片化を防ぐことができますが、ヒープは動的に割り当てられたメモリがいつ解放されるかがわからないため、メモリの断片化を防ぐことができません。これにより、大きなデータを連続して格納するのが難しくなります。そこで、断片化されたヒープに大きな配列をどのように保存するかという問題が生じます。

連結リスト

この問題の解決策として挙げられるのが連結リストです。各要素に次の値を指すポインタを割り当てることで、断片化されたヒープにデータを個別に格納することができます。次の要素に移動したいときには、単に現在の要素が指しているアドレスに移動すればよく、隣接するアドレスに移動する必要はありません。これを構造体を使ってプログラムすることができます。

typedef struct {
    int data;
    struct Node *next;
} Node;
 
Node *head = NULL;

連結リストの個々の要素をノードと呼びます。このように連結リストを定義すると、各ノードを別々の場所に保存することができます。

挿入と削除

連結リストは、ヒープの断片化問題を解決するだけでなく、配列と比較して要素の挿入と削除において優れています。

配列の中央に要素を挿入する場合、新しい要素を挿入したいインデックスの右側にあるすべての要素を右にシフトする必要があります。同様に、配列の中央から要素を削除する場合、削除したいインデックスの右側にあるすべての要素を左にシフトする必要があります。配列が小さい場合は大きな問題ではありませんが、配列が大きくなるに従って問題になってしまいます。

しかし、連結リストに要素を挿入したい場合、指定したインデックスのノードを取得し、それを新しいノードに指し、新しいノードが元のノードが指していた場所を指すようにします。同様に、ノードを削除する場合、削除したいノードを指しているノードを次のノードに指すように変更するだけです。連結リストには要素のシフトがないため、挿入と削除においてより優れたデータ構造であると言えます。

コードの実装

まずは、連結リストを表示する方法を見てみましょう。

// 連結リストの表示
void printLinkedList (Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current -> data);
        current = current -> next;
    }
    printf("\n");
    return;
}

上記のようにポインタを使って連結リストを走査する必要があります。次に、リストの先頭にノードを追加する関数を次のように設定できます。

// 連結リストにノードを先頭に追加
Node *prependNode(Node *head, int data) {
    Node *newNode = malloc(sizeof(Node));
 
    // mallocの失敗を処理
    if (newNode == NULL) {
        return NULL;
    }
    newNode->data = data;
 
    if (head == NULL) {
        head = newNode;
        newNode->next = NULL;
    } else {
        newNode->next = head;
        head = newNode;
    }
 
    return head;
}

先ほど説明した挿入と削除のための関数も作成できます。

// 連結リストにノードを挿入
int insertNode(Node *head, int data, int pos) {
    // 新しいノードを設定
    Node *newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        return 0;
    }
    newNode->data = data;
 
    // 指定された位置までリストを走査
    Node *current = head;
    while (current != NULL && pos != 1) {
        current = current->next;
        pos--;
    }
 
    // 指定された位置が見つからなかった場合、0を返す
    if (pos != 1 || current == NULL) {
        free(newNode);
        return 0;
    }
 
    // ポインタを変更
    newNode->next = current->next;
    current->next = newNode;
    return 1;
}
 
// 連結リストからノードを削除
int removeNode(Node **head, int pos) {
    Node *current = *head;
    Node *prev = NULL;
 
    // 先頭を削除する場合、次のノードを先頭に設定
    if (pos == 0) {
        if (current == NULL) {
            return 0;
        }
        *head = current->next;
        free(current);
        return 1;
    }
 
    // 指定された位置までリストを走査
    while (current != NULL && pos != 0) {
        prev = current;
        current = current->next;
        pos--;
    }
 
    // 指定された位置が見つからなかった場合、0を返す
    if (pos != 0 || current == NULL) {
        return 0;
    }
 
    // 前のノードのポインタを次のノードに設定
    prev->next = current->next;
    free(current);
    return 1;
}

最後に、クリーンアップ関数を設定することを忘れないでください。

void freeNodes(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *cleaned = current;
        current = current->next;
        free(cleaned);
    }
    return;
}

常に批判的思考を持とう

これまでの連結リストの説明で、連結リストが配列よりも優れたデータ構造であると納得した人は、もう少し批判的思考を意識した方が良いかもしれません。上の説明では、連結リストの欠点の説明とパフォーマンスの測定結果を意図的に省略していました。

連結リストは各要素にポインタを保存しなければならないため、配列よりも多くのメモリを使用します。また、連結リストは断片化されたヒープにバラバラに格納される可能性があるため、キャッシュミスの可能性が多くなってしまいます。さらに、連結リストでは挿入や削除のために線形探索を行う必要がありますが、配列ではそれが必要ありません。C++の発明者であるビャーネ・ストロヴストルップは、連結リストの線形探索が配列の要素をシフトするよりもはるかに時間がかかることを指摘しています。

ArrayList

では、キャッシュミスと線型探索をなくしながら、断片化したヒープにできるだけ変数を格納するにはどうすればいいでしょうか。一つの解決方法として、ArrayListがあげられます。ArrayListは配列へのポインタ、格納可能な容量、現在の配列の長さをまとめて管理することで、連続的に要素を格納しながら、容量がいっぱいになりそうな時、メモリの再割り当てを行うことで、書き込むべきでないメモリを上書きするのを防ぐことができます。

typedef struct {
    int *items;
    int capacity;
    int length;
} ArrayList;

配列の長さにアクセスできることで、範囲外の値にアクセスすることを避けることができるだけでなく、ループをする際sizeofで計算しなくても良くなります。再割り当ても含めて、これらの機能はただの配列では不可能でした。

批判的思考を忘れずに

ArrayListは理論的には優れていますが、すべてのケースでうまく機能するとは限りません。この世界には万能な解決策はありません。連結リストの方がパフォーマンスが高い場合もあります。(言語によって実装も異なる)実際のプロジェクトに取り組む際には、複数の解決策をベンチマークし、十分な根拠を持って適切なデータ構造を選択しましょう。

[豆知識] Pythonにおける配列

PythonやJavaScriptのようなスクリプト言語では、コードを機械語にコンパイルする代わりに、スクリプトを実行するインタプリタを使用してリストの動作をシミュレートします。そのため、リストを宣言すると、インタプリタはその背後で異なるデータ構造を生成してリストの動作をシミュレートします。

Pythonでは、リストを宣言すると、配列やArrayListを生成するのではなく、オブジェクトポインタの配列を生成します。そのため、リストの要素にアクセスするときは、最初にそのインデックスに保存されているポインタを探し、そのポインタが指しているオブジェクトを出力します。これにより、Pythonのリストは異なる型のオブジェクトを格納できるのです。(その分メモリも多く要し、キャッシュミスも多い) JavaScriptもリストをシミュレートする非常に興味深い方法を使用していますが、そのことについてはまたどこかの記事で紹介したいと思います。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

Alessandro Stamatto. 2012. Bjarne Stroustrup: Why you should avoid Linked Lists. YouTube.
Core Dumped. 2024. ARRAYLIST VS LINKEDLIST. YouTube.

Q1: ArrayListに要素を追加する関数pushを定義して下さい。