C言語で連結リストの指定インデックスのノードを出力・検索する方法

連結リスト(リンクリスト)において、指定されたインデックス位置にあるノードのデータを出力する方法を解説します。配列と異なり、連結リストには一般的にインデックスという概念が存在しないため、リスト全体を先頭から順に走査し、目的の位置に到達した時点でデータを出力する必要があります。

例えば、リストが 29、34、43、56、88 というノードを保持しており、指定するインデックスが 1、2、4 である場合、出力はこれらのインデックスに対応するノード、すなわち 34、43、88 となります。

例

連結リスト: 29->34->43->56->88
入力: 1 2 4
出力: 34 43 88

上記の連結リストの図では、黄色で強調表示されているノードが出力対象、つまり特定のインデックス上に存在するノードを表しています。

ここで採用するアプローチは、1つのポインタと、1で初期化したカウンタ変数を使用するものです。ノードを走査するたびにカウンタを増加させ、その値をキー(目的のインデックス)と照合します。キーとカウンタの値が一致した時点で、ノード構造体を指すポインタがそのノードのデータを出力し、さらに次のノードへと移動していきます。これにより、特定のインデックスに対応するノードを取得できます。

以下のコードは、このアルゴリズムをC言語で実装した例です。

アルゴリズム

START
    Step 1 -> 構造体型のノード変数を作成
        int data を宣言
        ノード型ポインタ *next を宣言
    Step 2 -> struct node* intoList(int data) を作成
        malloc で newnode を生成
        newnode->data = data を設定
        newnode->next = NULL を設定
        newnode を返す
    Step 3 -> 関数 void displayList(struct node *catchead) を宣言
        struct node *temp を作成
        IF catchead == NULL
            「リストは空です」を出力
            return
        End
        temp = catchead を設定
        Loop While (temp != NULL)
            temp->data を出力
            temp = temp->next を設定
        End
    Step 4 -> 関数 int search(int key, struct node *head) を宣言
        int index を宣言
        struct node *newnode を作成
        index = 0、newnode = head を設定
        Loop While (newnode != NULL かつ newnode->data != key)
            index++ を実行
            newnode = newnode->next を設定
        End
        return (newnode != NULL) ? index : -1
    Step 5 -> main() 内で
        struct node* head = intoList(9) でノードを作成
        displayList(head) を呼び出す
        index = search(24, head) を設定
        IF index >= 0
            index を出力
        ELSE
            「リスト内に見つかりません」を出力
        EndIF
STOP

実装コード

#include <stdio.h>
#include <stdlib.h>
//ノードの構造体
struct node {
    int data;
    struct node *next;
};
struct node* intoList(int data) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}
//リストを表示する関数
void displayList(struct node *catchead) {
    struct node *temp;
    if (catchead == NULL) {
        printf("List is empty.\n");
        return;
    }
    printf("elements of list are : ");
    temp = catchead;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
//要素を検索する関数
int search(int key,struct node *head) {
    int index;
    struct node *newnode;
    index = 0;
    newnode = head;
    while (newnode != NULL && newnode->data != key) {
        index++;
        newnode = newnode->next;
    }
    return (newnode != NULL) ? index : -1;
}
int main() {
    int index;
    struct node* head = intoList(9); //リストに要素を挿入
    head->next = intoList(76);
    head->next->next = intoList(13);
    head->next->next->next = intoList(24);
    head->next->next->next->next = intoList(55);
    head->next->next->next->next->next = intoList(109);
    displayList(head);
    index = search(24,head);
    if (index >= 0)
        printf("%d found at position %d\n", 24, index);
    else
        printf("%d not found in the list.\n", 24);
    index=search(55,head);
    if (index >= 0)
        printf("%d found at position %d\n", 55, index);
    else
    printf("%d not found in the list.\n", 55);
}

出力結果

上記のプログラムを実行すると、次のような出力が得られます。

elements of list are : 9 76 13 24 55 109
24 found at position 3
55 found at position 4

この実装では、search 関数がリストを先頭から走査し、キーと一致するデータを持つノードの位置(インデックス)を返します。該当するノードが存在しない場合は -1 を返すため、呼び出し側では戻り値を判定して適切なメッセージを表示しています。連結リストはランダムアクセスができないため、このような線形探索の計算量は O(n) となります。