एन तत्वों और ओ (1) संचालन के लिए डेटा संरचना?

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

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

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

एल्गोरिदम

आरंभीकरण(एन)

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];
}