データ構造の基礎：一般化リスト（Generalized List）とは？定義とC++実装を解説

一般化リスト（Generalized List）とは

このセクションでは、データ構造の一つである「一般化リスト（Generalized List）」について詳しく解説します。一般化リストは、通常の線形リストを拡張したもので、入れ子構造を持つ柔軟なデータ表現が可能です。

一般化リストの定義

一般化リスト L は、n 個（n ≥ 0）の要素からなる有限の列として定義されます。各要素 e_i は、次のいずれかです。

• アトム（atom）：それ以上分解できない単一の要素
• 部分リスト（サブリスト）：別の一般化リストそのもの

つまり、アトムではない要素 e_i は、すべて L の部分リストとみなされます。

具体例

例として、次の一般化リストを見てみましょう。

L = ((A, B, C), ((D, E), F), G)

このリスト L は、3つの要素で構成されています。

• 部分リスト (A, B, C)
• 部分リスト ((D, E), F) —— これはさらに、部分リスト (D, E) とアトム F の2要素を持ちます
• アトム G

このように、一般化リストではリストの中にリストを何重にも入れ子にできるため、木構造に近い複雑な階層データも自然に表現できます。

C++ による一般化リストの構造定義

C++ では、一般化リストのノードを次のように定義できます。

class GeneralizedListNode {
    private:
        GeneralizedListNode *next;
        bool tag;
        union {
            char data;
            GeneralizedListNode *down;
        };
};

ノード構造の仕組み

この実装における各メンバの役割は以下の通りです。

• tag：タグフラグ。true の場合、そのノードは部分リストを表し、false の場合はアトムを表します。
• down ポインタ：tag が true のとき、部分リストの先頭ノードを指します。
• next ポインタ：同じ階層における次の要素へのポインタです。
• union（data / down）：アトムの場合は文字 data を格納し、部分リストの場合は down ポインタを使用します。共用体によりメモリを節約できます。

これらのポインタとタグを組み合わせることで、アトムと部分リストが混在する一般化リスト全体を一貫した方法で操作することが可能になります。