Arrays: Create a data structure for n elements and constant operations

The complexity of the operations should be as follows:

* Insertion of an element – O(1)
* Deletion of an element – O(1)
* Finding an element – O(1)

According to question, we need to insert, delete and find the element in constant time.
This can be solved using simple arrays or by using vectors. The only advantage by using vectors in C++, that it is dynamic and can be optimized more.

In this solution we solve it by using constant array. Hence we need to know the value of “n” beforehand.

Basic Idea:

The basic idea is to initialize all the values in the array from “0” to “n” to “false” or “0”.
Then when we insert an element we mark that index as “true” or “1”.
When finding that element, we check the index of the number, if it is “true” or “false”, hence we get if the element is present or not.
When deleting the element, we check the index of the number, if it is “true” make it “false”, thus deleting the number.

Hence doing all the operations in O(1) time.

Below code snippets explains how to do it.

1. Initialization of the array.

The idea is to initialize all the elements to 0.

void initialize(int n)
{
	// initialize all the values to 0
	for (int i = 0; i<=n; i++)
	{
		arr[i] = 0; 
	}
}

2. Inserting an element:

Set the value at that index to true or “1”.

void insert(unsigned i)
{
	// set the value at that index to true
	arr[i] = 1; 
}

3. Finding an element:

Return the present value at that index. “0” means that element is not found, else “1” means the element is present.

int search(unsigned i)
{
	//check if the value at that index is true or false and return that
	return arr[i];
}

4. Delete the element.

Set the value at that index to “0”.

void remove(unsigned i)
{
	//directly assign the value at that index to 0
	arr[i] = 0;
}

Full program:

#include<iostream>
using namespace std;

//global array
int arr[50];


void initialize(int n)
{
	// initialize all the values to 0
	for (int i = 0; i<=n; i++)
	{
		arr[i] = 0; 
	}
}

void insert(unsigned i)
{
	// set the value at that index to true
	arr[i] = 1; 
}

int search(unsigned i)
{
	//check if the value at that index is true or false and return that
	return arr[i];
}

void remove(unsigned i)
{
	//directly assign the value at that index to 0
	arr[i] = 0;
}


int main()
{
	initialize(50);

	//insert element at the index 5
	insert(5);

	//check if 5 is present or not
	cout<<"The element 5 is = " << search(5)<<endl;

	//check if 6 is present or not
	cout<<"The element 6 is = " << search(6)<<endl;
	
	//delete element 5
	remove(5);
	cout<<"Element 5 has been deleted "<<endl;

	//check if 5 is present or not. The value should be 0 now.
	cout<<"The element 5 is = " << search(5)<<endl;

	return 0;

}

Output:

The element 5 is = 1
The element 6 is = 0
Element 5 has been deleted
The element 5 is = 0