1. 連鎖記憶方式の基本概念

線形リストを物理メモリ上に配置する際、隣接する論理要素が連続したアドレスを持つ必要はない。この配置方式は非順序記憶とも呼ばれ、任意のメモリ領域にデータを分散させ、ポインタによって前後の論理関係を維持する。これにより、要素の追加や削除が配列に比べて効率的に行える一方、インデックスによる直接アクセスは不可能となる。

1.1 基本用語

• ノード：データ要素とリンク情報を保持する最小単位。データフィールドとポインタフィールドから構成される。
• リスト構造：複数のノードをポインタで繋ぎ合わせた論理系列。
• リストの分類：
  • 単方向リスト：次ノードへの参照のみを持つ。
  • 双方向リスト：次と前の双方への参照を持つ。
  • 循環リスト：終端ノードのポインタが先頭を指す。
• 参照ポイント：
  • ヘッダポインタ：リスト全体の開始アドレスを指す変数。
  • ダミーヘッダノード：操作の統一性を高めるため先頭に配置される空ノード。
  • 先頭データノード：実際に最初のデータを格納するノード。

連結構造の最大の特徴は、物理配置の非連続性とアクセスの逐次性にある。先頭から順にポインタを辿る必要があるため、先頭と末尾への到達コストは要素数に比例する。

2. ノード構造の定義

以下の構造体定義では、整数型の値を保持するデータフィールドと、次ノードへの参照を保持するポインタフィールドを分離している。型エイリアスを用いてリスト全体の起点を明確にしている。

typedef int DataType;

typedef struct SinglyNode {
    DataType value;
    struct SinglyNode* next_link;
} SinglyNode;

typedef SinglyNode* ListHandle;

3. 基本操作の実装

3.1 初期化

ダミーヘッダを生成し、初期状態のリンクを切断する。ポインタ参照渡しを用いて呼び出し側のハンドルを更新する。

void InitializeEmptyList(ListHandle* out_handle) {
    *out_handle = (ListHandle)malloc(sizeof(SinglyNode));
    if (*out_handle != NULL) {
        (*out_handle)->next_link = NULL;
    }
}

3.2 全体の破棄

起点から末尾まで順にノードを解放し、メモリリークを防ぐ。

void ReleaseEntireList(ListHandle head) {
    SinglyNode* current = head;
    while (current != NULL) {
        SinglyNode* temp = current;
        current = current->next_link;
        free(temp);
    }
}

3.3 データのクリア

ダミーヘッダを維持したまま、実際のデータノードのみを解放する。

void PurgeDataNodes(ListHandle head) {
    if (!head) return;
    SinglyNode* ptr = head->next_link;
    while (ptr) {
        SinglyNode* next_safe = ptr->next_link;
        free(ptr);
        ptr = next_safe;
    }
    head->next_link = NULL;
}

3.4 要素数の取得

先頭から末尾まで走査し、通過したノード数を累積する。

size_t ComputeSize(ListHandle head) {
    size_t count = 0;
    for (SinglyNode* p = head->next_link; p; p = p->next_link) {
        count++;
    }
    return count;
}

3.5 位置指定による値の取得

1起点のインデックスを指定し、該当ノードの値を出力引数へ返す。範囲外の場合は失敗を通知する。

bool FetchValueAt(ListHandle head, int index, DataType* out_val) {
    SinglyNode* cur = head->next_link;
    int current_pos = 1;
    while (cur && current_pos < index) {
        cur = cur->next_link;
        current_pos++;
    }
    if (cur && current_pos == index) {
        *out_val = cur->value;
        return true;
    }
    return false;
}

3.6 値による位置の検索

指定された値と一致する最初のノードを探し、その相対位置を返す。存在しない場合は負値を返す。

int LocateValuePosition(ListHandle head, DataType target) {
    int pos = 0;
    for (SinglyNode* p = head->next_link; p; p = p->next_link) {
        pos++;
        if (p->value == target) return pos;
    }
    return -1;
}

3.7 ノードの挿入

指定位置の直前ノードを探し、新規ノードをリンクに組み込む。ポインタの差し替え順序に注意する。

void InsertNode(ListHandle head, int pos, DataType data) {
    SinglyNode* prev = head;
    int steps = 0;
    while (prev && steps < pos - 1) {
        prev = prev->next_link;
        steps++;
    }
    if (!prev) return;

    SinglyNode* new_node = (SinglyNode*)malloc(sizeof(SinglyNode));
    new_node->value = data;
    new_node->next_link = prev->next_link;
    prev->next_link = new_node;
}

3.8 ノードの削除

削除対象の直前ノードを取得し、リンクをバイパスした後に対象を解放する。

void RemoveNodeAt(ListHandle head, int pos) {
    SinglyNode* prev = head;
    int steps = 0;
    while (prev->next_link && steps < pos - 1) {
        prev = prev->next_link;
        steps++;
    }
    if (!prev->next_link) return;

    SinglyNode* target = prev->next_link;
    prev->next_link = target->next_link;
    free(target);
}

4. リストの構築パターン

4.1 先頭挿入法

配列から読み込んだ要素を毎回ヘッダ直後に配置する。結果として入力順序と逆のリストが生成される。

void BuildPrependStyle(ListHandle head, const int src[], int len) {
    for (int i = 0; i < len; i++) {
        SinglyNode* node = (SinglyNode*)malloc(sizeof(SinglyNode));
        node->value = src[i];
        node->next_link = head->next_link;
        head->next_link = node;
    }
}

4.2 末尾挿入法

終端ポインタを追跡しながら新ノードを繋いでいく。入力順序を維持したリストが構築できる。

void BuildAppendStyle(ListHandle head, const int src[], int len) {
    SinglyNode* tail_ptr = head;
    for (int i = 0; i < len; i++) {
        SinglyNode* node = (SinglyNode*)malloc(sizeof(SinglyNode));
        node->value = src[i];
        node->next_link = NULL;
        tail_ptr->next_link = node;
        tail_ptr = node;
    }
}