C言語でのリンクリストの実装方法を徹底解説：基本から応用まで

リンクリストはデータ構造の基本の一つであり、効率的なデータ管理に欠かせません。本記事では、C言語におけるリンクリストの基本概念から応用例までをわかりやすく解説します。これを学ぶことで、データ構造の理解が深まり、より効率的なプログラムの作成が可能になります。

リンクリストとは

リンクリストはデータ構造の一種で、各要素（ノード）が次の要素への参照（リンク）を持つことで構成されます。配列と異なり、リンクリストは動的にメモリを確保するため、要素の追加や削除が効率的に行えます。これにより、データの管理や操作が柔軟に行える点がリンクリストの大きな利点です。以下のセクションでは、リンクリストの基本的な概念とその構造について詳しく見ていきます。

シングルリンクリストの基本構造

シングルリンクリストは、各ノードが次のノードへの参照を一つだけ持つ構造です。基本的な要素は以下の通りです：

ノードの構造

ノードはデータ部分と次のノードを指すポインタ部分の二つから成ります。C言語では、構造体を用いてノードを定義します。

ヘッドポインタ

リンクリストの最初のノードを指すポインタで、リスト全体を操作するための入り口となります。

基本構造の例

以下にシングルリンクリストの基本構造を示します：

struct Node {
    int data; // データ部分
    struct Node* next; // 次のノードへのポインタ
};

このようにして定義されたノードを用いて、リンクリストの操作を行います。次のセクションでは、具体的なノードの定義とリンクリストの作成方法を説明します。

ノードの定義とリンクリストの作成

シングルリンクリストを実装するためには、まずノードの定義とリンクリストの初期化を行います。以下に、具体的な手順とコード例を示します。

ノードの定義

C言語では、構造体を用いてノードを定義します。各ノードはデータ部分と次のノードへのポインタ部分を持ちます。

struct Node {
    int data; // データ部分
    struct Node* next; // 次のノードへのポインタ
};

リンクリストの初期化

リンクリストの初期化とは、ヘッドポインタをNULLに設定することを意味します。これにより、空のリンクリストが作成されます。

struct Node* head = NULL; // 初期状態ではヘッドポインタはNULL

ノードの追加

新しいノードをリンクリストに追加するためには、以下の手順を踏みます：

新しいノードを作成し、メモリを割り当てる。
新しいノードのデータ部分に値を設定する。
新しいノードの次のノードへのポインタを現在のヘッドに設定する。
ヘッドポインタを新しいノードに変更する。

// 新しいノードの作成と初期化
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 10;
newNode->next = head;
head = newNode;

このコードにより、新しいノードがリンクリストの先頭に追加されます。次のセクションでは、リンクリストへのデータ追加方法について詳しく説明します。

リンクリストへのデータ追加

リンクリストに新しいデータを追加する方法には、主に3つのケースがあります：リストの先頭に追加、リストの末尾に追加、特定の位置に追加。以下に各ケースについて具体的な方法とコード例を示します。

リストの先頭にデータを追加

新しいデータをリストの先頭に追加するには、前述の方法を用います。

void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

リストの末尾にデータを追加

新しいデータをリストの末尾に追加するには、リストを最後まで走査し、最後のノードの次のポインタを新しいノードに設定します。

void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    newNode->data = newData;
    newNode->next = NULL;

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

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = newNode;
}

特定の位置にデータを追加

リストの特定の位置に新しいデータを追加するには、その位置までリストを走査し、新しいノードを挿入します。

void insertAfter(struct Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("前のノードがNULLです。挿入できません。\n");
        return;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

これらの方法により、リンクリストに対して柔軟にデータを追加することができます。次のセクションでは、リンクリストからのデータ削除方法について説明します。

リンクリストからのデータ削除

リンクリストからデータを削除する方法には、主に3つのケースがあります：リストの先頭から削除、特定のデータを持つノードの削除、リストの末尾から削除。以下に各ケースについて具体的な方法とコード例を示します。

リストの先頭からデータを削除

リストの先頭のデータを削除するには、ヘッドポインタを次のノードに設定し、現在の先頭ノードを解放します。

void deleteFromBeginning(struct Node** head) {
    if (*head == NULL) return; // リストが空の場合は何もしない

    struct Node* tempNode = *head;
    *head = (*head)->next;
    free(tempNode);
}

特定のデータを持つノードの削除

特定のデータを持つノードを削除するには、そのノードの前のノードを見つけ、その次のポインタを削除するノードの次のポインタに設定します。

void deleteNode(struct Node** head, int key) {
    struct Node* tempNode = *head;
    struct Node* prevNode = NULL;

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

    while (tempNode != NULL && tempNode->data != key) {
        prevNode = tempNode;
        tempNode = tempNode->next;
    }

    if (tempNode == NULL) return; // キーが見つからない場合

    prevNode->next = tempNode->next;
    free(tempNode);
}

リストの末尾からデータを削除

リストの末尾のデータを削除するには、リストを最後まで走査し、最後のノードの前のノードの次のポインタをNULLに設定します。

void deleteFromEnd(struct Node** head) {
    if (*head == NULL) return; // リストが空の場合は何もしない

    struct Node* tempNode = *head;
    struct Node* prevNode = NULL;

    if (tempNode->next == NULL) {
        *head = NULL;
        free(tempNode);
        return;
    }

    while (tempNode->next != NULL) {
        prevNode = tempNode;
        tempNode = tempNode->next;
    }

    prevNode->next = NULL;
    free(tempNode);
}

これらの方法により、リンクリストから効率的にデータを削除することができます。次のセクションでは、リンクリストの探索と表示方法について説明します。

リンクリストの探索と表示

リンクリスト内のデータを探索し、表示する方法を解説します。これにより、リンクリストの内容を確認したり、特定のデータを見つけたりすることができます。

リンクリストの探索

リンクリスト内の特定のデータを探索するためには、リストを順次走査し、目的のデータを持つノードを見つける必要があります。

bool search(struct Node* head, int key) {
    struct Node* current = head; // 現在のノードをヘッドから始める

    while (current != NULL) {
        if (current->data == key)
            return true;
        current = current->next;
    }
    return false;
}

このコードは、リンクリストを先頭から順に走査し、指定されたデータを持つノードが見つかればtrueを返し、見つからなければfalseを返します。

リンクリストの表示

リンクリストの内容を表示するには、リストを順次走査し、各ノードのデータを出力します。

void printList(struct Node* head) {
    struct Node* current = head;

    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

このコードは、リンクリストを先頭から順に走査し、各ノードのデータを表示します。最後に”NULL”を表示することで、リストの終端を示します。

リンクリストの例

以下に、リンクリストを作成し、データを追加、表示する一連の操作の例を示します。

int main() {
    struct Node* head = NULL;

    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    printf("リンクリストの内容: ");
    printList(head);

    int key = 2;
    if (search(head, key))
        printf("%d はリンクリスト内に存在します。\n", key);
    else
        printf("%d はリンクリスト内に存在しません。\n", key);

    return 0;
}

この例では、リンクリストにデータを追加し、リストの内容を表示し、特定のデータの探索結果を出力しています。次のセクションでは、ダブルリンクリストの基本構造について説明します。

ダブルリンクリストの基本構造

ダブルリンクリストは、各ノードが次のノードへの参照（ポインタ）だけでなく、前のノードへの参照も持つデータ構造です。これにより、前方向と後方向の両方でリストを走査することが可能になります。以下に、ダブルリンクリストの基本構造とシングルリンクリストとの違いを説明します。

ダブルリンクリストの構造

ダブルリンクリストのノードは、データ部分と二つのポインタ部分（次のノードへのポインタと前のノードへのポインタ）を持ちます。

struct DNode {
    int data; // データ部分
    struct DNode* next; // 次のノードへのポインタ
    struct DNode* prev; // 前のノードへのポインタ
};

シングルリンクリストとの違い

シングルリンクリストは次のノードへのポインタしか持たないのに対し、ダブルリンクリストは前のノードへのポインタも持つため、以下のような利点があります：

双方向の走査が可能：前方向だけでなく後方向にもリストを走査できるため、特定の操作が効率的に行えます。
ノードの削除が容易：特定のノードを削除する際に、前のノードのポインタを更新するのが容易になります。

ダブルリンクリストの初期化

ダブルリンクリストの初期化は、シングルリンクリストと同様にヘッドポインタをNULLに設定することで行います。

struct DNode* head = NULL; // 初期状態ではヘッドポインタはNULL

ダブルリンクリストへのデータ追加

ダブルリンクリストに新しいデータを追加する場合、前のノードのポインタも設定する必要があります。以下にリストの先頭にデータを追加する例を示します。

void insertAtBeginning(struct DNode** head, int newData) {
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = newData;
    newNode->next = *head;
    newNode->prev = NULL;

    if (*head != NULL)
        (*head)->prev = newNode;

    *head = newNode;
}

これにより、新しいノードがリストの先頭に追加され、適切に前のノードへのポインタも設定されます。次のセクションでは、ダブルリンクリストを用いた応用例として、スタックとキューの実装方法について説明します。

応用例：リンクリストを用いたスタックとキューの実装

リンクリストは柔軟なデータ構造であり、スタックやキューといった他のデータ構造を実装するのに適しています。以下に、リンクリストを用いたスタックとキューの実装方法を具体的なコード例とともに解説します。

スタックの実装

スタックは、後入れ先出し（LIFO）構造のデータ構造です。リンクリストを用いてスタックを実装する場合、通常はリストの先頭をスタックのトップとします。

スタックのプッシュ操作

新しいデータをスタックにプッシュするには、リストの先頭にノードを追加します。

void push(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

スタックのポップ操作

スタックからデータをポップするには、リストの先頭ノードを削除します。

int pop(struct Node** head) {
    if (*head == NULL) {
        printf("スタックが空です。\n");
        return -1;
    }
    struct Node* tempNode = *head;
    *head = (*head)->next;
    int poppedData = tempNode->data;
    free(tempNode);
    return poppedData;
}

キューの実装

キューは、先入れ先出し（FIFO）構造のデータ構造です。リンクリストを用いてキューを実装する場合、リストの先頭をデキュー操作のフロントとし、リストの末尾をエンキュー操作のリアとします。

キューのエンキュー操作

新しいデータをキューにエンキューするには、リストの末尾にノードを追加します。

void enqueue(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    newNode->data = newData;
    newNode->next = NULL;

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

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = newNode;
}

キューのデキュー操作

キューからデータをデキューするには、リストの先頭ノードを削除します。

int dequeue(struct Node** head) {
    if (*head == NULL) {
        printf("キューが空です。\n");
        return -1;
    }
    struct Node* tempNode = *head;
    *head = (*head)->next;
    int dequeuedData = tempNode->data;
    free(tempNode);
    return dequeuedData;
}

これらのコードにより、リンクリストを用いたスタックとキューの基本的な操作が実装できます。次のセクションでは、リンクリストに関する理解を深めるための演習問題を提供します。

演習問題

リンクリストに関する理解を深めるために、以下の演習問題に挑戦してください。これらの問題を通じて、リンクリストの操作や応用について実践的なスキルを身につけることができます。

演習問題1：リストの逆転

シングルリンクリストを逆転させる関数を実装してください。リストの先頭から最後までの順序を逆にする方法を考えてみましょう。

void reverse(struct Node** head) {
    struct Node* prev = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    *head = prev;
}

演習問題2：ループの検出

リンクリストにループが存在するかどうかを検出する関数を実装してください。リスト内のノードが再度訪れるかどうかを確認します。

bool detectLoop(struct Node* head) {
    struct Node* slowPtr = head;
    struct Node* fastPtr = head;

    while (slowPtr != NULL && fastPtr != NULL && fastPtr->next != NULL) {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;

        if (slowPtr == fastPtr) {
            return true;
        }
    }

    return false;
}

演習問題3：ノードの削除（特定の条件）

与えられた値より大きいデータを持つすべてのノードを削除する関数を実装してください。

void deleteNodesGreaterThan(struct Node** head, int value) {
    struct Node* current = *head;
    struct Node* prev = NULL;

    while (current != NULL) {
        if (current->data > value) {
            if (prev == NULL) {
                *head = current->next;
            } else {
                prev->next = current->next;
            }
            struct Node* temp = current;
            current = current->next;
            free(temp);
        } else {
            prev = current;
            current = current->next;
        }
    }
}

これらの演習問題を通じて、リンクリストの操作に関する理解を深めてください。次のセクションでは、本記事のまとめを行います。

まとめ

本記事では、C言語でのリンクリストの実装方法について、基本から応用までを詳しく解説しました。リンクリストは柔軟で効率的なデータ構造であり、データの追加や削除、探索が容易に行えるため、多くのプログラムで利用されています。基本的なシングルリンクリストの構造から、より高度なダブルリンクリストの応用、スタックやキューの実装方法まで幅広く紹介しました。これらの知識を活用して、リンクリストを効果的に使いこなし、プログラムの性能を向上させましょう。