Which data structure supports efficient deleting and random access?

Question

I am looking for a data structure in which I can efficiently remove items and also supports random access.

I also need efficient insertion but as the ordering of elements is not important, I thought I can preallocate memory for maximum number of elements it may have to store and then always put the new element at the end so that no reallocation or move of other elements is necessary.

To the best of my knowledge, a linked list would be perfect for deleting but accessing its elements can take O(n) time. On the other side, a simple array (e.g vector in C++) has the random access property but deleting an element from such an structure has complexity of O(n).

Actually, the random access requirement is something stronger than what I really need. I only have to be able to pick an element of the structure uniformly at random. Clearly efficient access property implies efficiency of the operation I need but I am not sure if those two are equivalent.

Thanks in advance!

Answer 1

I believe the solution you hint at in your question is actually what you need, except for a small detail.

You suggested:

I thought I can preallocate memory for maximum number of elements it may have to store and then always put the new element at the end so that no reallocation or move of other elements is necessary.

If indeed you can establish a reasonable maximum number of entries, then I would suggest you pre-allocate an array (e.g. using std::array if the maximum is known at compile time, or a std::vector otherwise) with that number of entries, establish an element count (to count the number of elements currently stored), and proceed as follows:

1. Initially you set the count to 0
2. When you insert an element, you add it to the end and increment the count
3. When you delete an element, you swap it with the last element and decrement the count
4. For random access (in the sense you described it, i.e. literally picking an element randomly) you determine a random number between 0 and count, and pick that element

The only detail I changed is element deletion, 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;
}

Answer 2

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