n個の要素とO（1）操作のデータ構造？

ここでは、n個の要素を持つ1つのデータ構造と、O（1）操作を示します。そのため、操作の実行には一定の時間がかかります。

データ構造はn個の要素（0からn-1まで）を保持します。データは任意の順序にすることができます。挿入、削除、検索にはO（1）の時間がかかります。

この問題を解決するために、1つのブール配列を使用します。これは、アイテムが位置iに存在するかどうかを示します。アイテムが存在する場合は1を保持し、存在しない場合は0を保持します。

アルゴリズム

initialization（n）

begin
   fill all elements of the Boolean array as 0
end

insert（i）

begin
   set element at index i as 1(true)
end

delete（i）

begin
set element at index i as 0(false)
end

search（i）

begin
   return item at position i
end

例

//initialization
void init(int n) {
   bool dataStructure[n];
   for (int i = 0; i<n; i++)
      dataStructure[i] = 0;
}
//Insertion
void insert(unsigned i) {
   dataStructure[i] = 1;
}
//Deletion
void delete(unsigned i) {
   dataStructure[i] = 0;
}
//Search
bool search(unsigned i) {
   return dataStructure[i];
}