n উপাদান এবং O(1) অপারেশনের জন্য একটি ডেটা কাঠামো?

এখানে আমরা n উপাদান সহ একটি ডেটা-স্ট্রাকচার এবং O(1) অপারেশন দেখতে পাব। সুতরাং অপারেশনগুলি সম্পাদন করতে নিয়মিত সময় লাগবে৷

ডাটা স্ট্রাকচার n উপাদান ধারণ করবে (0 থেকে n-1 পর্যন্ত)। ডেটা যেকোনো ক্রমে হতে পারে। সন্নিবেশ, মুছে ফেলা এবং অনুসন্ধান করতে O(1) পরিমাণ সময় লাগবে।

এই সমস্যা সমাধানের জন্য, আমরা একটি বুলিয়ান অ্যারে ব্যবহার করব। এটি নির্দেশ করবে যে আইটেমটি অবস্থানে আছে বা নেই। যদি আইটেমটি উপস্থিত থাকে তবে এটি 1 ধরে রাখবে, অন্যথায় 0।

অ্যালগরিদম

শুরুকরণ(n)

begin
   fill all elements of the Boolean array as 0
end

ঢোকান(i)

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

মুছুন(i)

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

অনুসন্ধান(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];
}