A data structure for n elements and O(1) operations

Read

Discuss

Propose a data structure for the following:

The data structure would hold elements from 0 to n-1. There is no order on the elements (no ascending/descending order requirement)

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)

We strongly recommend to minimize the browser and try this yourself first.

A boolean array works here. Array will have value ‘true’ at ith index if i is present, and ‘false’ if absent.

Initialization:

We create an array of size n and initialize all elements as absent.

C++

void initialize(int n)
{
    bool A[n];
    for (int i = 0; i < n; i++)
        A[i] = false;
}

C

void initialize(int n)
{
  bool A[n];
  for (int i = 0; i<n; i++)
    A[i] = {0}; // or A[n] = {false};
}

Java

void initialize(int n)
{
  boolean A[n];
  for (int i = 0; i<n; i++)
    A[i] = false;
}
 
// This code is contributed by aadityaburujwale.

Python3

def initialize(n):
    A = [False] * n
 
# This code is contributed by akashish__

C#

void initialize(int n)
{
    bool[] A = new bool[n];
    for (int i = 0; i < n; i++)
        A[i] = false;
}
 
// This code is contributed by akashish__

Javascript

function initialize(n) {
  let A = new Array(n);
  for (let i = 0; i < n; i++) {
    A[i] = false;
  }
}
 
// This code is contributed by akashish__

Insertion of an element:

C

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

C++

void insert(int i)
{
   /* set the value at index i to true */
   A[i] = true;
}

Java

void insert(int i)
{
   /* set the value at index i to true */
   A[i] = true;
}
 
// This code is contributed by aadityaburujwale.

Python3

def insert(i):
    """Set the value at index i to True."""
    A[i] = True
# This code is contributed by akashish__

C#

void insert(int i)
{
   /* set the value at index i to true */
   A[i] = true;
}
 
// This code is contributed by akashish__

Javascript

void insert(unsigned i)
{
   /* set the value at index i to true */
   A[i] = true;
}
// This code is contributed by akashish__

Deletion of an element:

C++

void delete(int i)
{
    /* make the value at index i to false */
    A[i] = false;
}

C

void delete(unsigned i)
{
  /* make the value at index i to 0 */
  A[i] = 0;  // Or A[i] = false;
}

Java

void delete(int i)
{
  /* make the value at index i to false */
  A[i] =  false;
}
 
// This code is contributed by aadityaburujwale.

Python3

#Python equivalent of the code
def delete(i):
  """ make the value at index i to false """
  A[i] = False

C#

void delete(int i)
{
    /* make the value at index i to false */
    A[i] = false;
}
 
// This code is contributed by Akshay Tripathi(akshaytripathi19410)

Javascript

function delete(i) {
    // make the value at index i false
    A[i] = false;
}

Finding an element:

C++

// Returns true if 'i' is present, else false
bool Find(int i)
{
    return A[i];
}

C

// Returns true if 'i' is present, else false
bool find(unsigned i)
{
    return A[i];
}

Java

// Returns true if 'i' is present, else false
boolean find(int i)
{
    return A[i];
}
 
// This code is contributed by aadityaburujwale.

C#

// Returns true if 'i' is present, else false
bool Find(int i)
{
    return A[i];
}

Javascript

// Returns true if 'i' is present, else false
// JavaScript
function find(i) {
    return A[i] ? true : false;
}
// This code is contributed by akashish__

Python3

# code
def Find(i):
  return A[i]

As an exercise, change the data structure so that it holds values from 1 to n instead of 0 to n-1.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 25 Mar, 2023