C言語プログラムで単一リンクリスト（片方向連結リスト）のノードの合計を求める方法

片方向リンクリストとは

片方向リンクリスト（単一リンクリスト）は、各要素（ノード）が「データの値」と「次のノードへのリンク（ポインタ）」という2つの部分で構成されるデータ構造です。リンクリスト内のすべての要素の合計を求めるには、先頭ノードから順に各ノードをたどりながら、その値を合計用の変数に加算していきます。

具体例

リンクリスト: 2 -> 27 -> 32 -> 1 -> 5
合計 = 2 + 27 + 32 + 1 + 5 = 67

合計を求める2つの方法

リンクリストのノードの合計を求めるには、大きく分けて次の2つの方法があります。

• 方法1：ループ（反復処理）を使ってリンクリストのすべての値を走査し、合計を求める
• 方法2：再帰関数を使って、リンクリストに要素がなくなるまで自分自身を呼び出しながら合計を求める

方法1：ループを使う方法

ループはリンクリストの末尾、つまりノードのポインタがNULLを指すまで実行され、その間に各ノードの値を順次加算していきます。処理がシンプルで追加のメモリをほとんど消費しないため、最も一般的な実装方法です。

サンプルコード（ループ版）

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void push(struct Node** nodeH, int nodeval) {
    struct Node* new_node = new Node;
    new_node->data = nodeval;
    new_node->next = (*nodeH);
    (*nodeH) = new_node;
}
int main() {
    struct Node* head = NULL;
    int sum = 0;
    push(&head, 95);
    push(&head, 60);
    push(&head, 87);
    push(&head, 6);
    push(&head, 12);
    struct Node* ptr = head;
    while (ptr != NULL) {
        sum += ptr->data;
        ptr = ptr->next;
    }
    cout << "Sum of nodes = " << sum;
    return 0;
}

実行結果

Sum of nodes = 260

方法2：再帰関数を使う方法

再帰関数は、リンクリストに要素が存在する限り自分自身を繰り返し呼び出します。各呼び出しでは、次のノードへのポインタと、合計値を格納する変数のアドレスを引数として渡します。コードが簡潔になる反面、再帰の深さ分だけスタックメモリを消費する点に注意が必要です。

サンプルコード（再帰版）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void nodesum(struct Node* head, int* sum) {
    if (!head)
        return;
    nodesum(head->next, sum);
    *sum = *sum + head->data;
}
int main() {
    struct Node* head = NULL;
    int sum = 0;
    push(&head, 95);
    push(&head, 60);
    push(&head, 87);
    push(&head, 6);
    push(&head, 12);
    nodesum(head, &sum);
    cout << "Sum of nodes = " << sum;
    return 0;
}

実行結果

Sum of nodes = 260

計算量の比較

どちらの方法も全ノードを一度ずつ訪問するため、時間計算量はO(n)で同一です。ただし、ループ版の空間計算量はO(1)であるのに対し、再帰版は呼び出しスタックをノード数分だけ使用するためO(n)となります。ノード数が非常に多いリンクリストを扱う場合は、スタックオーバーフローを避けるためにもループ版の採用が推奨されます。

補足

なお、本記事のコード例はC++（new演算子やiostreamを使用）で記述しています。純粋なC言語で実装する場合は、ノードの確保にmalloc()を、結果の出力にprintf()を使用してください。