線形リストとは

線形リストとは、同じ型のデータ要素が有限個並んだデータ構造であり、論理的には直線状の構造を持ちます。代表的な線形リストには、順序表（配列実装）、スタック、連結リスト、キューなどがあります。物理的なメモリ配置は直列であるとは限りませんが、順序表の場合は実際のメモリ配置も連続しています。

順序表

順序表は線形リストの一種で、論理的・物理的両方の構造が連続しています。内部的には動的配列として実装され、基本的な配列操作に加えて、データの挿入・削除・検索といった操作が容易に行えるように拡張されています。

実装には静的順序表（固定長配列）と動的順序表（可変長配列）がありますが、ここでは柔軟性が高くメモリ効率も良い動的順序表を対象とします。

動的順序表の型定義

typedef int ElementType; // 要素の型をまとって変更可能にする
typedef struct {
    ElementType* data;  // 要素を格納する動的配列
    size_t capacity;    // 確保済みの配列サイズ
    size_t count;       // 有効な要素数
} DynamicList;

初期化

void initList(DynamicList* list) {
    list->data = NULL;
    list->capacity = 0;
    list->count = 0;
}

後処理（解放）

void destroyList(DynamicList* list) {
    if (list->data != NULL) {
        free(list->data);
    }
    list->data = NULL;
    list->capacity = 0;
    list->count = 0;
}

出力（デバッグ用）

void printList(const DynamicList* list) {
    for (size_t i = 0; i < list->count; ++i) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

容量確認と拡張

void ensureCapacity(DynamicList* list) {
    if (list->count == list->capacity) {
        size_t newCap = (list->capacity == 0) ? 8 : list->capacity * 2;
        ElementType* tmp = realloc(list->data, sizeof(ElementType) * newCap);
        if (tmp == NULL) {
            fprintf(stderr, "Memory allocation failed.\n");
            exit(EXIT_FAILURE);
        }
        list->data = tmp;
        list->capacity = newCap;
    }
}

末尾への挿入

void appendBack(DynamicList* list, ElementType value) {
    ensureCapacity(list);
    list->data[list->count++] = value;
}

先頭への挿入

void prependFront(DynamicList* list, ElementType value) {
    ensureCapacity(list);
    for (size_t i = list->count; i > 0; --i) {
        list->data[i] = list->data[i - 1];
    }
    list->data[0] = value;
    ++list->count;
}

末尾の削除

void removeBack(DynamicList* list) {
    if (list->count > 0) {
        --list->count;
    }
}

先頭の削除

void removeFront(DynamicList* list) {
    if (list->count > 0) {
        for (size_t i = 0; i < list->count - 1; ++i) {
            list->data[i] = list->data[i + 1];
        }
        --list->count;
    }
}

指定位置への挿入

void insertAt(DynamicList* list, size_t index, ElementType value) {
    if (index > list->count) return;
    ensureCapacity(list);
    for (size_t i = list->count; i > index; --i) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;
    ++list->count;
}

指定位置の削除

void eraseAt(DynamicList* list, size_t index) {
    if (index >= list->count) return;
    for (size_t i = index; i < list->count - 1; ++i) {
        list->data[i] = list->data[i + 1];
    }
    --list->count;
}

データの検索

int findElement(const DynamicList* list, ElementType target) {
    for (size_t i = 0; i < list->count; ++i) {
        if (list->data[i] == target) {
            return (int)i;
        }
    }
    return -1; // not found
}