Geek Answers Handbook

What data structure supports efficient deletion and random access?

I am looking for a data structure in which I can efficiently delete items as well as support random access.

I also need efficient insertion, but since ordering the elements is not important, I thought I could allocate memory for the maximum number of elements that it can store, and then always put a new element at the end to redistribute or move other elements.

As far as I know, a linked list would be ideal for deletion, but access to its elements may take O (n) time. On the other hand, a simple array (for example, vector in C ++) has a random access property, but removing an element from such a structure has O (n) complexity.

Actually, the requirement of random access is something more powerful than what I really need. I only have to be able to select an element of the structure evenly randomly. Obviously, an effective access property implies the effectiveness of the operation I need, but I'm not sure if these two equivalents.

Thanks in advance!

+6
source share
2 answers

I believe that the solution you are hinting at in your question is actually what you need, with the exception of a small detail.

You suggested:

I thought that I could allocate memory for the maximum number of elements that it can store, and then always put a new element at the end so that no redistribution or movement of other elements is required.

If you can really set a reasonable maximum number of records, I would suggest you pre-allocate the array (for example, using std::array , if the maximum is known at compile time or std::vector otherwise) with this number of records, set the element counter ( to count the number of items currently saved) and follow these steps:

  • First you set the counter to 0
  • When you insert an element, you add it to the end and increase the counter
  • When you delete an item, you replace it with the last item and decrease the counter
  • For random access (in the sense in which you describe it, that is, literally choosing an element at random), you determine a random number between 0 and the counter and select this element

The only detail that I changed is the removal of the element, which I suggest you implement as switch positions with the last element.

Possible implementation:

 #include <vector> #include <utility> #include <iostream> template <typename Elem> class randomaccesstable { public: randomaccesstable(std::size_t initial_size) : data_(initial_size) , count_(0) { } randomaccesstable &push_back(const Elem &elem) { if (count_ < data_.size()) data_[count_++] = elem; else { data_.push_back(elem); ++count_; } return *this; } randomaccesstable &remove(const std::size_t index) { if (index < count_) { std::swap(data_[index],data_[count_-1]); --count_; } return *this; } const Elem &operator[](const std::size_t index) const { return data_[index]; } Elem &operator[](const std::size_t index) { return data_[index]; } std::size_t size() const { return count_; } private: std::vector<Elem> data_; std::size_t count_; }; int main() { randomaccesstable<int> table(10); table.push_back(3); table.push_back(12); table.push_back(2); for (std::size_t i = 0 ; i < table.size() ; ++i) std::cout << table[i] << ' '; std::cout << '\n'; table.remove(1); // this removes the entry for 12, swapping it for 2 for (std::size_t i = 0 ; i < table.size() ; ++i) std::cout << table[i] << ' '; std::cout << '\n'; return 0; }
+5
source

I would suggest using a hash table . There you can delete and search with constant complexity. In C ++ you can use std::unordered_map (C ++ 11) or boost::unordered_map (pre-C ++ 11), and in java - HashMap .

+1
source

More articles:


All Articles