C言語で実装する動的配列（ベクター）

C言語におけるデータ構造の中でも、特に柔軟性の高い「動的配列」について解説します。動的配列は、プログラムの実行中に要素数が増減する可能性のあるコレクションを扱う際に非常に便利です。この記事では、C言語で動的配列、いわゆる「順序リスト」をゼロから実装する方法を詳しく見ていきます。

動的配列の基本概念

動的配列は、物理的に連続したメモリ領域にデータを格納し、必要に応じてそのサイズを自動的に変更できるデータ構造です。C言語の静的配列とは異なり、コンパイル時にサイズを確定させる必要がなく、実行時にメモリを動的に確保・解放することで、要素の追加や削除に柔軟に対応します。

• 物理的連続性: 配列の要素はメモリ上で連続して配置されます。これにより、インデックスによる高速なアクセス（O(1)）が可能です。
• 内部構造: 通常、ポインタ、現在の有効な要素数、そして現在確保されているメモリの総容量（キャパシティ）を保持する構造体として実装されます。
• 自動拡張: 要素の追加によって容量が不足した場合、より大きなメモリ領域を新たに確保し、既存のデータを新しい領域にコピーすることで、配列を拡張します。この操作にはrealloc関数がよく利用されます。

動的配列のデータ構造定義

ここでは、動的配列を「Vector」という名前で定義します。要素の型はElemTypeとしてint型に設定しますが、必要に応じて他の型に変更することも可能です。

// dynamic_vector.h
#pragma once
#include <stdio.h>   // printf, perror のために
#include <stdlib.h>  // malloc, realloc, free, exit, EXIT_FAILURE のために
#include <assert.h>  // assert のために
#include <limits.h>  // SIZE_MAX のために

// ベクターに格納される要素の型を定義
typedef int ElemType;

// 動的配列（ベクター）の構造体定義
typedef struct {
    ElemType* data;     // データを指すポインタ
    size_t capacity;    // 現在確保されているメモリの総容量
    size_t length;      // 現在格納されている有効な要素数
} Vector;

// ベクター操作のための関数プロトタイプ宣言
void Vector_Init(Vector* vec);
void Vector_Destroy(Vector* vec);
void Vector_PushBack(Vector* vec, ElemType value);
void Vector_PushFront(Vector* vec, ElemType value);
void Vector_PopBack(Vector* vec);
void Vector_PopFront(Vector* vec);
size_t Vector_Find(const Vector* vec, ElemType target);
void Vector_InsertAt(Vector* vec, size_t index, ElemType value);
void Vector_RemoveAt(Vector* vec, size_t index);
void Vector_Print(const Vector* vec);

動的配列の主要な操作と実装

上記で定義したVector構造体に対する各種操作（初期化、追加、削除、検索、表示など）の実装詳細を見ていきましょう。

メモリ管理と初期化・破棄

動的配列の柔軟性は、そのメモリ管理にあります。特に、Vector_EnsureCapacity関数は、要素を追加する前に十分なメモリがあるかを確認し、必要に応じて拡張する重要な役割を担います。

// dynamic_vector.c
#include "dynamic_vector.h"

// 内部ヘルパー関数：ベクターの容量が不足している場合に拡張する
// 容量は通常2倍に増加させる。初期容量は8とする。
static void Vector_EnsureCapacity(Vector* vec) {
    if (vec->length == vec->capacity) {
        // 容量が0の場合は初期容量を8に設定、それ以外は現在の容量を2倍に拡張
        size_t newCapacity = (vec->capacity == 0) ? 8 : vec->capacity * 2;
        ElemType* newData = (ElemType*)realloc(vec->data, newCapacity * sizeof(ElemType));

        if (newData == NULL) {
            perror("メモリ割り当てエラー: Vector_EnsureCapacity");
            exit(EXIT_FAILURE); // 致命的なエラーとしてプログラムを終了
        }
        vec->data = newData;
        vec->capacity = newCapacity;
    }
}

// ベクターの初期化
void Vector_Init(Vector* vec) {
    assert(vec != NULL); // NULLポインタチェック
    vec->data = NULL;
    vec->capacity = 0;
    vec->length = 0;
}

// ベクターの破棄（動的に確保されたメモリの解放）
void Vector_Destroy(Vector* vec) {
    assert(vec != NULL);
    if (vec->data != NULL) {
        free(vec->data); // メモリを解放
        vec->data = NULL;
    }
    vec->capacity = 0;
    vec->length = 0;
}

要素の追加操作

動的配列への要素の追加は、末尾、先頭、または任意のインデックスに対して行えます。先頭や中間に挿入する場合、既存の要素をシフトする必要があるため、時間計算量はO(N)となります。

// dynamic_vector.c (続き)

// ベクターの末尾に要素を追加する
void Vector_PushBack(Vector* vec, ElemType value) {
    assert(vec != NULL);
    Vector_EnsureCapacity(vec); // 必要であれば容量を拡張
    vec->data[vec->length++] = value; // 末尾に要素を追加し、要素数をインクリメント
}

// ベクターの先頭に要素を追加する
void Vector_PushFront(Vector* vec, ElemType value) {
    assert(vec != NULL);
    Vector_EnsureCapacity(vec); // 必要であれば容量を拡張
    // 既存の要素を後方に1つずつシフト
    for (size_t i = vec->length; i > 0; --i) {
        vec->data[i] = vec->data[i - 1];
    }
    vec->data[0] = value; // 新しい要素を先頭に挿入
    vec->length++;
}

// 指定したインデックスに要素を挿入する
void Vector_InsertAt(Vector* vec, size_t index, ElemType value) {
    assert(vec != NULL);
    assert(index <= vec->length); // インデックスは有効範囲内 (lengthも含む)

    Vector_EnsureCapacity(vec); // 必要であれば容量を拡張

    // 挿入位置から末尾までの要素を後方に1つずつシフト
    for (size_t i = vec->length; i > index; --i) {
        vec->data[i] = vec->data[i - 1];
    }
    vec->data[index] = value; // 新しい要素を挿入
    vec->length++;
}

要素の削除操作

要素の削除も、末尾、先頭、または任意のインデックスに対して可能です。先頭や中間から削除する場合も、後続の要素をシフトする必要があるため、時間計算量はO(N)となります。

// dynamic_vector.c (続き)

// ベクターの末尾の要素を削除する
void Vector_PopBack(Vector* vec) {
    assert(vec != NULL);
    assert(vec->length > 0); // ベクターが空でないことを確認
    vec->length--; // 論理的に要素数を減らす
}

// ベクターの先頭の要素を削除する
void Vector_PopFront(Vector* vec) {
    assert(vec != NULL);
    assert(vec->length > 0); // ベクターが空でないことを確認
    // 先頭から削除位置まで、要素を前方に1つずつシフト
    for (size_t i = 0; i < vec->length - 1; ++i) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->length--;
}

// 指定したインデックスの要素を削除する
void Vector_RemoveAt(Vector* vec, size_t index) {
    assert(vec != NULL);
    assert(vec->length > 0);        // ベクターが空でないことを確認
    assert(index < vec->length);    // インデックスは有効範囲内

    // 削除位置の次から末尾までの要素を前方に1つずつシフト
    for (size_t i = index; i < vec->length - 1; ++i) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->length--;
}

要素の検索と表示

ベクター内の特定の要素を検索したり、現在の内容をコンソールに出力したりする機能も重要です。

// dynamic_vector.c (続き)

// 要素の検索
// ターゲットが見つかった場合、そのインデックスを返す。見つからない場合は SIZE_MAX を返す。
size_t Vector_Find(const Vector* vec, ElemType target) {
    assert(vec != NULL);
    for (size_t i = 0; i < vec->length; ++i) {
        if (vec->data[i] == target) {
            return i; // 見つかったインデックスを返す
        }
    }
    return SIZE_MAX; // 見つからなかった場合は特別な値 (最大値) を返す
}

// ベクターの内容をコンソールに表示
void Vector_Print(const Vector* vec) {
    assert(vec != NULL);
    printf("Vector 内容 (長さ: %zu, 容量: %zu): [", vec->length, vec->capacity);
    for (size_t i = 0; i < vec->length; ++i) {
        printf("%d", vec->data[i]);
        if (i < vec->length - 1) {
            printf(", ");
        }
    }
    printf("]\n");
}

使用例

実装した動的配列（ベクター）を実際に使用する簡単な例です。

// main.c
#include "dynamic_vector.h"
#include <stdio.h>
#include <limits.h> // SIZE_MAX のために

int main() {
    Vector myVector;
    Vector_Init(&myVector); // ベクターを初期化

    printf("--- 末尾追加テスト ---\n");
    Vector_PushBack(&myVector, 10);
    Vector_PushBack(&myVector, 20);
    Vector_PushBack(&myVector, 30);
    Vector_Print(&myVector); // 結果: [10, 20, 30]

    printf("\n--- 先頭追加テスト ---\n");
    Vector_PushFront(&myVector, 5);
    Vector_PushFront(&myVector, 1);
    Vector_Print(&myVector); // 結果: [1, 5, 10, 20, 30]

    printf("\n--- インデックス挿入テスト (インデックス3に15を挿入) ---\n");
    Vector_InsertAt(&myVector, 3, 15);
    Vector_Print(&myVector); // 結果: [1, 5, 10, 15, 20, 30]

    printf("\n--- 末尾削除テスト ---\n");
    Vector_PopBack(&myVector);
    Vector_Print(&myVector); // 結果: [1, 5, 10, 15, 20]

    printf("\n--- 先頭削除テスト ---\n");
    Vector_PopFront(&myVector);
    Vector_Print(&myVector); // 結果: [5, 10, 15, 20]

    printf("\n--- インデックス削除テスト (インデックス1の要素(10)を削除) ---\n");
    Vector_RemoveAt(&myVector, 1);
    Vector_Print(&myVector); // 結果: [5, 15, 20]

    printf("\n--- 検索テスト ---\n");
    size_t found_idx = Vector_Find(&myVector, 15);
    if (found_idx != SIZE_MAX) {
        printf("値 %d はインデックス %zu で見つかりました。\n", 15, found_idx);
    } else {
        printf("値 %d は見つかりませんでした。\n", 15);
    }

    found_idx = Vector_Find(&myVector, 100);
    if (found_idx != SIZE_MAX) {
        printf("値 %d はインデックス %zu で見つかりました。\n", 100, found_idx);
    } else {
        printf("値 %d は見つかりませんでした。\n", 100);
    }

    Vector_Destroy(&myVector); // 動的に確保したメモリを解放
    printf("\nベクターを破棄しました。\n");

    return 0;
}