n個の要素を格納し、すべての操作がO(1)で実行できるデータ構造の実装方法

本記事では、n個の要素を保持し、すべての操作を定数時間 O(1) で実行できるデータ構造について解説します。挿入・削除・検索といった基本操作が、いずれも一定の時間で完了する点が大きな特徴です。

このデータ構造は、0からn-1までのn個の要素を保持します。要素は任意の順序で格納されていても構いません。そして、挿入（Insert）、削除（Delete）、検索（Search）のすべての操作が O(1) の時間計算量で実行できます。

実装のアイデア

この問題を解く鍵となるのは、ブール型（bool）の配列です。配列の各インデックス i に対して、その位置に要素が存在するかどうかをフラグとして記録します。要素が存在すれば 1（true）、存在しなければ 0（false）を格納します。

この仕組みにより、特定の要素の有無を確認したり、追加・削除を行ったりする際に、配列の該当インデックスへ直接アクセスするだけで済むため、どの操作も定数時間で処理できます。

アルゴリズム

初期化：init(n)

begin
    ブール配列の全要素を 0（false）で埋める
end

挿入：insert(i)

begin
    インデックス i の要素を 1（true）に設定する
end

削除：delete(i)

begin
    インデックス i の要素を 0（false）に設定する
end

検索：search(i)

begin
    インデックス i の値を返す
end

C++による実装例

// 初期化
void init(int n) {
    bool dataStructure[n];
    for (int i = 0; i < n; i++)
        dataStructure[i] = 0;
}
// 挿入
void insert(unsigned i) {
    dataStructure[i] = 1;
}
// 削除
void delete(unsigned i) {
    dataStructure[i] = 0;
}
// 検索
bool search(unsigned i) {
    return dataStructure[i];
}

まとめ

このように、ブール配列を用いたシンプルな実現方法により、挿入・削除・検索のすべてを O(1) の時間計算量で行うことが可能です。ただし、この手法は「扱う要素が 0〜n-1 の範囲の整数に限定される」「メモリ使用量が n に比例して増える」といった制約がある点には注意が必要です。範囲が既知で小さい場合には非常に効率的な選択肢となります。