連続しないメモリ領域にデータを格納するため、順序付きリスト（配列）の挿入・削除における線形コストを回避する方法として、連結リストが用いられる。 連結リストは、メモリ上で連続しない複数の構造体から構成され、各構造体はデータ要素と次の要素へのポインタ（next）を持つ。末尾の要素のnextはNULLとなる。 単方向連結リストは、各ノードが1つのポインタのみを持つリストである。

特徴：

• ノードのメモリ上の位置は任意であり、論理的に隣接するデータが物理的にも隣接するとは限らない。
• アクセスは先頭ポインタ（head）を介してのみ行われ、各ノードのnextポインタを順にたどる。

1. 単方向連結リストの定義

以下では、先頭ノード（ダミーノード）を持つ単方向連結リストを扱う。

1.1 ヘッダファイルと構造体

#include <stdio.h>
#include <stdlib.h>

typedef struct SNode {
    int data;
    struct SNode* next;
} SNode, *SinglyLinkedList;

1.2 初期化

初期化関数では、先頭ポインタのポインタを受け取り、ダミーノードを生成する。 SinglyLinkedList* L とすることで、関数内部で実際の先頭ポインタを変更できる。

void initializeList(SinglyLinkedList* L) {
    *L = (SinglyLinkedList)malloc(sizeof(SNode));
    if (*L == NULL) {
        return;
    }
    (*L)->next = NULL;
}

2. リストの生成

2.1 末尾挿入による生成

void createListTail(SinglyLinkedList L) {
    int val, count = 2;
    SinglyLinkedList newNode, tail = L;
    printf("最初のデータを入力（'.'で終了）: ");
    while (scanf("%d", &val)) {
        newNode = (SinglyLinkedList)malloc(sizeof(SNode));
        newNode->data = val;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        printf("第%dデータを入力（'.'で終了）: ", count++);
    }
    printf("入力完了\n");
    // 入力バッファをクリア
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF);
}

2.2 先頭挿入による生成

void createListHead(SinglyLinkedList L) {
    int val, count = 2;
    SinglyLinkedList newNode;
    printf("最初のデータを入力（'.'で終了）: ");
    while (scanf("%d", &val)) {
        newNode = (SinglyLinkedList)malloc(sizeof(SNode));
        newNode->data = val;
        newNode->next = L->next;
        L->next = newNode;
        printf("第%dデータを入力（'.'で終了）: ", count++);
    }
    printf("入力完了\n");
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF);
}

3. 基本操作

3.1 長さ取得

int getListLength(SinglyLinkedList L) {
    int len = 0;
    SinglyLinkedList p = L->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

3.2 空チェック

int isEmpty(SinglyLinkedList L) {
    return (L->next == NULL);
}

3.3 インデックスによる要素取得

void getElementByIndex(SinglyLinkedList L) {
    int idx, pos = 0;
    SinglyLinkedList p = L;
    printf("取得したい要素の番号を入力: ");
    scanf("%d", &idx);
    while (p != NULL && pos < idx) {
        p = p->next;
        pos++;
    }
    if (p == NULL || idx == 0) {
        printf("第%d要素は存在しません\n", idx);
    } else {
        printf("第%d要素の値: %d\n", idx, p->data);
    }
}

3.4 値による検索

void locateElementByValue(SinglyLinkedList L) {
    int target, pos = 1;
    SinglyLinkedList p = L->next;
    printf("検索する値を入力: ");
    scanf("%d", &target);
    while (p != NULL && p->data != target) {
        p = p->next;
        pos++;
    }
    if (p) {
        printf("値 %d は第%d要素に見つかりました（アドレス: %p）\n", target, pos, (void*)p);
    } else {
        printf("値 %d は見つかりませんでした\n", target);
    }
}

3.5 挿入

void insertElement(SinglyLinkedList L) {
    SinglyLinkedList p = L, newNode;
    int idx, pos = 0, val;
    printf("挿入位置（1始まり）: ");
    scanf("%d", &idx);
    printf("挿入する値: ");
    scanf("%d", &val);
    while (p != NULL && pos < idx - 1) {
        p = p->next;
        pos++;
    }
    if (p == NULL || pos > idx - 1) {
        printf("挿入位置が不正です\n");
        return;
    }
    newNode = (SinglyLinkedList)malloc(sizeof(SNode));
    newNode->data = val;
    newNode->next = p->next;
    p->next = newNode;
    printf("挿入成功\n");
}

3.6 削除

void deleteElement(SinglyLinkedList L) {
    SinglyLinkedList p = L, q;
    int idx, pos = 0;
    printf("削除する要素の位置: ");
    scanf("%d", &idx);
    while (p != NULL && pos < idx - 1) {
        p = p->next;
        pos++;
    }
    if (p == NULL || pos > idx - 1 || (p->next == NULL && idx == 1)) {
        printf("削除位置が不正です\n");
        return;
    }
    q = p->next;
    p->next = q->next;
    printf("削除された値: %d\n", q->data);
    free(q);
}

3.7 表示

void printList(SinglyLinkedList L) {
    SinglyLinkedList p = L->next;
    if (p == NULL) {
        printf("リストは空です\n");
        return;
    }
    printf("リスト: ");
    while (p != NULL) {
        printf("%d", p->data);
        if (p->next != NULL) printf(" -> ");
        p = p->next;
    }
    printf("\n");
}

3.8 クリア（全要素削除）

void clearList(SinglyLinkedList L) {
    SinglyLinkedList p = L->next, q;
    while (p != NULL) {
        q = p;
        p = p->next;
        free(q);
    }
    L->next = NULL;
    printf("リストをクリアしました\n");
}

3.9 破棄（ヘッダノードも解放）

void destroyList(SinglyLinkedList* L) {
    SinglyLinkedList p = *L, q;
    while (p != NULL) {
        q = p;
        p = p->next;
        free(q);
    }
    *L = NULL;
    printf("リストを破棄しました\n");
}

4. メニューとメイン関数

void showMenu() {
    printf("================================================\n");
    printf(" 1: 末尾挿入でリスト生成\n");
    printf(" 2: 先頭挿入でリスト生成\n");
    printf(" 3: 長さ取得\n");
    printf(" 4: 空チェック\n");
    printf(" 5: インデックスで要素取得\n");
    printf(" 6: 値で検索\n");
    printf(" 7: 挿入\n");
    printf(" 8: 表示\n");
    printf(" 9: 削除\n");
    printf("10: クリア\n");
    printf("11: 破棄\n");
    printf("12: 終了\n");
    printf("================================================\n");
}

int main() {
    showMenu();
    SinglyLinkedList list = NULL;
    initializeList(&list);
    int choice, ch;
    printf("操作番号を入力: ");
    while (scanf("%d", &choice)) {
        if (choice == 12) {
            printf("プログラムを終了します\n");
            destroyList(&list);
            break;
        }
        switch (choice) {
            case 1: createListTail(list); break;
            case 2: createListHead(list); break;
            case 3: printf("長さ: %d\n", getListLength(list)); break;
            case 4: printf(isEmpty(list) ? "空です\n" : "空ではありません\n"); break;
            case 5: getElementByIndex(list); break;
            case 6: locateElementByValue(list); break;
            case 7: insertElement(list); break;
            case 8: printList(list); break;
            case 9: deleteElement(list); break;
            case 10: clearList(list); break;
            case 11: destroyList(&list); 
                     printf("リストを破棄後、再初期化します\n");
                     initializeList(&list);
                     break;
            default: printf("不正な入力です\n");
        }
        // 入力バッファクリア（scanf後に残る改行など）
        while ((ch = getchar()) != '\n' && ch != EOF);
        printf("操作番号を入力: ");
    }
    return 0;
}