title: Efficient data structure for fast random access, search, insertion and deletion
body: <p>I'm looking for a data structure (or structures) that would allow me keep me an ordered list of integers, no duplicates, with indexes and values in the same range.</p>
  
  <p>I need four main operations to be efficient, in rough order of importance:</p>
  
  <ol>
  <li>taking the value from a given index</li>
  <li>finding the index of a given value</li>
  <li>inserting a value at a given index</li>
  <li>deleting a value at a given index</li>
  </ol>
  
  <p>Using an array I have 1 at O(1), but 2 is O(N) and insertion and deletions are expensive (O(N) as well, I believe). </p>
  
  <p>A Linked List has O(1) insertion and deletion (once you have the node), but 1 and 2 are O(N) thus negating the gains.</p>
  
  <p>I tried keeping two arrays a[index]=value and b[value]=index, which turn 1 and 2 into O(1) but turn 3 and 4 into even more costly operations.</p>
  
  <p>Is there a data structure better suited for this?</p>