1. 線形リストの基本概念

線形リストはデータ構造の基本要素であり、順序を持ったデータ要素の有限列です。主に配列で実装される「配列ベースリスト」とポインタで実装される「連結リスト」の2種類があります。

特徴：

• 配列ベースリスト：ランダムアクセスが高速
• 連結リスト：挿入・削除操作が容易

2. 配列による実装の構造

連続したメモリ領域を使って要素を格納します。各要素はインデックスによって直接アクセス可能です。

構造体定義

#define MAX_SIZE 100
typedef int ElementType;
typedef struct {
    ElementType elements[MAX_SIZE];
    int currentLength;
} ArrayBasedList;

要素取得処理

ElementType getElement(ArrayBasedList *list, int index) {
    if (!list || index < 0 || index >= list->currentLength) {
        return -1; // エラーコード
    }
    return list->elements[index];
}

要素挿入処理

int insertElement(ArrayBasedList *list, ElementType value, int index) {
    if (!list || index < 0 || index > list->currentLength) {
        return 0; // 失敗
    }
    
    // 最大容量を超えないように調整
    if (index > list->currentLength) {
        index = list->currentLength;
    }
    
    // 要素を後方にシフト
    for (int i = list->currentLength; i > index; i--) {
        list->elements[i] = list->elements[i-1];
    }
    
    list->elements[index] = value;
    list->currentLength++;
    return 1; // 成功
}

要素削除処理

ElementType deleteElement(ArrayBasedList *list, int index) {
    if (!list || index < 0 || index >= list->currentLength) {
        return -1; // エラーコード
    }
    
    ElementType removed = list->elements[index];
    
    // 要素を前方にシフト
    for (int i = index; i < list->currentLength-1; i++) {
        list->elements[i] = list->elements[i+1];
    }
    
    list->currentLength--;
    return removed;
}

その他の基本操作

int getListLength(ArrayBasedList *list) {
    return list->currentLength;
}

void printList(ArrayBasedList *list) {
    if (!list || list->currentLength == 0) {
        printf("リストは空です\n");
        return;
    }
    
    printf("リスト要素：");
    for (int i = 0; i < list->currentLength; i++) {
        printf("%d ", list->elements[i]);
    }
    printf("\n");
}

void clearList(ArrayBasedList *list) {
    list->currentLength = 0;
}

3. 配列ベースリストの特徴

メリット：

• インデックスによる高速なアクセス（O(1)）
• ポインタのための追加メモリが不要

デメリット：

• 挿入・削除時の要素移動（O(n)）
• 固定サイズのための柔軟性の低さ