n तत्वों के लिए O(1) ऑपरेशन वाला डेटा स्ट्रक्चर

यहां हम एक ऐसे डेटा स्ट्रक्चर को देखेंगे जिसमें n तत्व हों और सभी ऑपरेशन O(1) समय में हों। यानी ऑपरेशन को निष्पादित करने में लगने वाला समय स्थिर होगा।

यह डेटा स्ट्रक्चर n तत्वों (0 से n-1 तक) को धारण करेगा। डेटा किसी भी क्रम में हो सकता है। सम्मिलन, विलोपन और खोज O(1) समय लेंगे।

इस समस्या को हल करने के लिए हम एक बूलियन सरणी का उपयोग करेंगे। यह इंगित करेगा कि स्थिति i पर आइटम मौजूद है या नहीं। यदि आइटम मौजूद है, तो यह 1 रखेगा, अन्यथा 0।

एल्गोरिदम

प्रारंभिकरण (n)

begin
    बूलियन सरणी के सभी तत्वों को 0 से भरें
end

सम्मिलन (i)

begin
    इंडेक्स i पर तत्व को 1 (सत्य) पर सेट करें
end

विलोपन (i)

begin
    इंडेक्स i पर तत्व को 0 (असत्य) पर सेट करें
end

खोज (i)

begin
    स्थिति i पर आइटम लौटाएं
end

उदाहरण

// प्रारंभिकरण
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];
}