C++で双方向リンクリストのサイズ（要素数）を求めるプログラム

本記事では、双方向リンクリスト（Doubly Linked List）が与えられたときに、そのサイズ（要素数）を求めるC++プログラムの作成方法を詳しく解説します。

双方向リンクリストとは、片方向リンクリストと比べて、各ノードが前後両方向のリンクを持つため、前方にも後方にも自由に移動できる特殊なリンクリストです。まず、双方向リンクリストを理解するうえで重要な用語を確認しておきましょう。

• リンク（Link）：リンクリストの各リンクには、「要素」と呼ばれるデータが格納されます。
• ネクスト（Next）：各リンクには、次のリンクを指す参照「Next」が含まれます。
• プレヴ（Prev）：各リンクには、前のリンクを指す参照「Prev」が含まれます。
• リンクリスト本体：先頭のリンク「First」と末尾のリンク「Last」への接続情報を保持しています。

双方向リンクリストの構造

問題の説明

上記のような双方向リンクリストが与えられ、そのサイズ（ノード数）を求めるのが今回の課題です。具体的な例で確認してみましょう。

入力

A <-> B <-> C

出力

3

解決アプローチ

双方向リンクリストのサイズを求めるには、先頭ノード（head）から順にリストを走査し、通過したノードの個数を変数 length でカウントしていくのが基本的な考え方です。

アルゴリズム

1. 初期化：length = 0、temp = head とする。
2. ステップ1：temp != NULL である間、以下を繰り返す。
   　ステップ1.1：length を1増やす（length++）。
   　ステップ1.2：temp = temp->next として、ポインタを次のノードへ進める。
3. ステップ2：length の値を出力する。

C++での実装例

#include <iostream>
using namespace std;

struct doublyLL {
    char val;
    struct doublyLL *next;
    struct doublyLL *prev;
};

void insertNode(struct doublyLL** head_ref, char value){
    struct doublyLL* new_node = new doublyLL;
    new_node->val = value;
    new_node->next = (*head_ref);
    new_node->prev = NULL;
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
    (*head_ref) = new_node;
}

int calcDLLSize(struct doublyLL *temp) {
    int length = 0;
    while (temp != NULL){
        temp = temp->next;
        length++;
    }
    return length;
}

int main(){
    struct doublyLL* head = NULL;
    insertNode(&head, 'A');
    insertNode(&head, 'H');
    insertNode(&head, 'E');
    insertNode(&head, 'K');
    insertNode(&head, 'M');
    insertNode(&head, 'S');
    cout << "The size of Doubly Linked List is " << calcDLLSize(head);
    return 0;
}

実行結果

The size of Doubly Linked List is 6

コードの解説

calcDLLSize 関数では、引数として受け取った先頭ノードから next ポインタをたどりながら length をインクリメントしていき、NULL に到達した時点でカウントした値を返します。一方、insertNode 関数はリストの先頭に新しいノードを挿入する関数で、既存の先頭ノードが存在する場合はその prev ポインタを新ノードに向けて更新しています。

このアルゴリズムの時間計算量は O(n)（n はノード数）、追加で必要なメモリは O(1) です。リスト全体を一度だけ走査すればよいため、非常に効率的な方法といえます。