Какая структура данных поддерживает эффективное удаление и произвольный доступ?

Я считаю, что решение, на которое вы намекаете в своем вопросе, на самом деле то, что вам нужно, за исключением небольшой детали.

Вы предложили:

Я думал, что могу предварительно выделить память для максимального количества элементов, которые она может хранить, а затем всегда помещать новый элемент в конец, чтобы не было необходимости в перераспределении или перемещении других элементов.

Если вы действительно можете установить разумное максимальное количество записей, то я бы предложил вам предварительно выделить массив (например, используя std::array, если максимум известен во время компиляции, или std::vector в противном случае) с этим количеством записей, установить количество элементов (чтобы подсчитать количество элементов, хранящихся в данный момент), и выполните следующие действия:

1. Изначально вы устанавливаете счетчик на 0
2. Когда вы вставляете элемент, вы добавляете его в конец и увеличиваете количество
3. Когда вы удаляете элемент, вы заменяете его последним элементом и уменьшаете счетчик
4. Для произвольного доступа (в том смысле, в каком вы его описали, т. е. буквально случайного выбора элемента) вы определяете случайное число между 0 и подсчетом и выбираете этот элемент

Единственная деталь, которую я изменил, — это удаление элемента, которое я предлагаю вам реализовать как переключить позиции с последним элементом.

Возможная реализация:

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

Я бы предложил использовать хеш-таблицу. Там вы можете как удалять, так и искать элемент с постоянной сложностью. В C++ вы можете использовать std::unordered_map(C++11) или boost::unordered_map(pre-C++11), а в java - HashMap.