A data structure for n elements and O(1) operations
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.