C 言語による双方向リンクリストの実装

はじめに

このプロジェクトでは、C言語で双方向リンクリストデータ構造を実装する方法を学びます。双方向リンクリストは、各ノードがその直前と直後のノードへのポインタを含むリンクリストの一種で、前向きと後ろ向きの両方向への効率的な走査が可能です。

👀 プレビュー

$ gcc test_list.c list.c -o test
$./test
welcome
to
labex
online

🎯 タスク

このプロジェクトでは、以下を学びます。

• 双方向リンクリストを初期化する方法
• 双方向リンクリストを走査し、各ノードに対してコールバック関数を実行する方法
• 双方向リンクリストの特定のノードの後ろに新しいノードを挿入する方法
• 双方向リンクリストの特定のノードの前に新しいノードを挿入する方法
• 双方向リンクリストからノードを削除する方法

🏆 成果

このプロジェクトを完了すると、以下のことができるようになります。

• 双方向リンクリストの基本構造と操作を理解する
• 双方向リンクリストを管理するために必要なコア関数を実装する
• C言語におけるポインタと動的メモリ割り当てを扱う能力を示す
• 提供された双方向リンクリストの実装を修正し、改善するために知識を適用する

Skills Graph

セグメンテーション フォールトの修正

このステップでは、free_list 関数がノードを解放した後に current ポインタを更新しないため、セグメンテーション フォールトが発生します。この不具合を直さなければなりません。

1. list.c ファイル内の free_list() 関数を探します。
2. 以下が更新された free_list() 関数です。

void free_list(struct List* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;

    while (current) {
        next = current->next;
        free(current);
        current = next; // 更新済み
    }
    free(list);
}

特定のノードの後ろにノードを挿入する

このステップでは、双方向リンクリストの特定のノードの後ろに新しいノードを挿入する方法を学びます。

1. list.c ファイル内の insert_after() 関数を探します。
2. この関数は、struct List*、struct Node*（新しいノードを挿入する後のノード）、および新しいノードの data を引数にとります。
3. この関数は、新しい struct Node を作成し、その data フィールドを提供された data で初期化する必要があります。
4. 次に、新しいノードの next と prev ポインタと、新しいノードを正しく挿入するための prev ノードを更新する必要があります。
5. 最後に、新しいノードがリストの末尾に挿入されている場合、tail ポインタを更新する必要があります。

以下が更新された insert_after() 関数です。

void insert_after(struct List* list, struct Node* prev, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (prev) { // 更新済み
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // 更新済み
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // 更新済み
        list->head = newnode;
    }
}

6. insert_after (list, NULL, data); を探して、以下のコードに変更します。

insert_after (list, list->tail, data);

特定のノードの前にノードを挿入する

このステップでは、双方向リンクリストの特定のノードの前に新しいノードを挿入する方法を学びます。

1. list.c ファイル内の insert_before() 関数を探します。
2. この関数は、struct List*、struct Node*（新しいノードを挿入する前のノード）、および新しいノードの data を引数にとります。
3. この関数は、新しい struct Node を作成し、その data フィールドを提供された data で初期化する必要があります。
4. 次に、新しいノードの next と prev ポインタと、新しいノードを正しく挿入するための next ノードを更新する必要があります。
5. 最後に、新しいノードがリストの先頭に挿入されている場合、head ポインタを更新する必要があります。

以下が更新された insert_before() 関数です。

void insert_before(struct List* list, struct Node* next, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (next) { // 更新済み
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // 更新済み
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // 更新済み
        list->tail = newnode;
    }
}

6. insert_before (list, NULL, data); を探して、以下のコードに変更します。

insert_before (list, list->head, data);

双方向リンクリストからノードを削除する

このステップでは、双方向リンクリストからノードを削除する方法を学びます。

1. list.c ファイル内の delete_from() 関数を探します。
2. この関数は、struct List* と struct Node*（削除するノード）を引数にとります。
3. この関数は、隣接するノードの next と prev ポインタを更新して、指定されたノードをリストから削除する必要があります。
4. 削除されたノードがリストの head または tail であった場合、この関数はまた head と tail ポインタも更新する必要があります。
5. 最後に、この関数は削除されたノードが占有するメモリを解放する必要があります。

以下が更新された delete_from() 関数です。

void delete_from(struct List* list, struct Node* node) {
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next; // 更新済み

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // 更新済み

    free(node);
}

これで、list.c ファイル内の双方向リンクリストの実装が正常に動作するはずです。双方向リンクリストの機能をテストするには、提供された test_list.c ファイルを使用できます。テスト結果は以下の通りです。

$ gcc test_list.c list.c -o test
$./test
welcome
to
labex
online

まとめ

おめでとうございます！このプロジェクトを完了しました。実力を向上させるために、LabExでさらに多くの実験を行って練習してください。