O(1) সময়ে ইন্সারশন, ডিলিশন ও সার্চ সাপোর্ট করে এমন ডেটা স্ট্রাকচার

এখানে আমরা একটি ডেটা স্ট্রাকচার দেখব যেখানে n সংখ্যক উপাদান থাকবে এবং সব অপারেশন O(1) সময়ে সম্পন্ন হবে — অর্থাৎ ধ্রুব সময়ে এক্সিকিউট হবে।

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

এই সমস্যা সমাধানের জন্য আমরা একটি বুলিয়ান অ্যারে ব্যবহার করব। এটি নির্দেশ করবে যে পজিশন i-তে আইটেমটি আছে কিনা। উপস্থিত থাকলে ১ (true), অন্যথায় ০ (false) রাখবে।

অ্যালগরিদম

ইনিশিয়ালাইজেশন (n)

শুরু
    বুলিয়ান অ্যারের সব এলিমেন্ট ০ দিয়ে ফিল করুন
শেষ

ইনসার্ট (i)

শুরু
    i ইন্ডেক্সের এলিমেন্টকে ১ (true) সেট করুন
শেষ

ডিলিট (i)

শুরু
    i ইন্ডেক্সের এলিমেন্টকে ০ (false) সেট করুন
শেষ

সার্চ (i)

শুরু
    i পজিশনের আইটেমটি রিটার্ন করুন
শেষ

উদাহরণ কোড

// ইনিশিয়ালাইজেশন
void init(int n) {
    bool dataStructure[n];
    for (int i = 0; i < n; i++)
        dataStructure[i] = 0;
}

// ইনসারশন
void insert(unsigned i) {
    dataStructure[i] = 1;
}

// ডিলিশন
void delete(unsigned i) {
    dataStructure[i] = 0;
}

// সার্চ
bool search(unsigned i) {
    return dataStructure[i];
}