title: Which data structure supports efficient deleting and random access?
body: <p>I am looking for a data structure in which I can efficiently remove items and also supports random access. </p>
  
  <p>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.</p>
  
  <p>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 <code>vector</code> in C++) has the random access property but deleting an element from such an structure has complexity of O(n).</p>
  
  <p>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.</p>
  
  <p>Thanks in advance! </p>