A data structure with n elements and with O(1) operations?

Here we will see a data structure with n elements and O(1) operations. Therefore, the operation will take constant time to execute.

The data structure will hold n elements (from 0 to n-1). Data can be in any order. Insertion, deletion and search will take O(1) time.

To solve this problem we will use a boolean array. This will indicate whether the item exists at location i. 1 if the item exists, 0 otherwise.

Algorithm

Initialization(n)

begin
   fill all elements of the Boolean array as 0
end

Insertion(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

Example

//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];
}

The above is the detailed content of A data structure with n elements and with O(1) operations?. For more information, please follow other related articles on the PHP Chinese website!