【C言語】第8章第5回：リンクリストの基本と応用

2025年1月15日 a-mun

リンクリストは、メモリを動的に管理しながらデータを格納するデータ構造です。本記事では、リンクリストの基本と実装方法を学びます。

Table of Contents

0. 記事の概要

この記事を読むメリット

柔軟なデータ管理：リンクリストを使用して、効率的にデータを操作できます。
応用力の向上：リンクリストを応用した高度なデータ構造の基礎を学べます。
動的メモリ管理の理解：動的メモリ確保と解放を通じてメモリ管理のスキルが向上します。

この記事で学べること

リンクリストの構造と基本操作
動的メモリ管理の基本
応用例：リンクリストを使ったデータの管理

活用のイメージ

リンクリストは、データベースの実装やタスクスケジューリング、プログラム内の動的データ管理に広く応用されています。

1. リンクリストの基本

1.1 リンクリストとは？

リンクリストは、データの要素（ノード）がポインタによって連結されているデータ構造です。

例：「A → B → C」というデータをリンクリストで表現します。各ノードは次のノードのアドレスを保持します。

1.2 リンクリストの基本操作

挿入（Insert）：リストの先頭または末尾にデータを追加
削除（Delete）：特定のノードを削除
探索（Search）：特定のデータを検索

2. リンクリストの実装

2.1 ノードの定義

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

// ノードの定義
typedef struct Node {
    int data;
    struct Node* next;
} Node;

2.2 ノードの挿入

// 先頭に挿入
void insertAtHead(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

// 末尾に挿入
void insertAtTail(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

2.3 ノードの削除

// 特定の値を持つノードを削除
void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Key not found\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

2.4 リンクリストの表示

// リンクリストを表示
void displayList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtTail(&head, 30);

    printf("Linked List: ");
    displayList(head);

    deleteNode(&head, 20);
    printf("After Deletion: ");
    displayList(head);

    return 0;
}

動作解説

挿入操作：新しいノードを作成し、リストに追加します。
削除操作：特定のデータを持つノードを見つけて削除します。
表示操作：リスト内の全データを順番に出力します。

3. 練習問題

以下の課題に挑戦して、リンクリストの理解を深めましょう。

リンクリストを逆順に表示する関数を実装してください。
リンクリストの長さを計算する関数を作成してください。
リンクリストをソートする関数を実装してください。

4. 練習問題の解答と解説

問1の解答

// リンクリストを逆順に表示
void displayReverse(Node* head) {
    if (head == NULL) {
        return;
    }
    displayReverse(head->next);
    printf("%d -> ", head->data);
}

int main() {
    Node* head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtTail(&head, 30);

    printf("Linked List in Reverse: ");
    displayReverse(head);
    printf("NULL\n");

    return 0;
}

このプログラムでは、再帰を使用してリンクリストを逆順に表示します。

5. まとめ

本記事では、リンクリストの基本的な構造と操作方法を学びました。次回は、リンクリストを応用した高度なデータ構造について学びます。