title: Is there a data structure with efficient inserts/deletes, but with positional ordering?
body: <p>I'm looking for a data structure with efficient inserts, deletes and lookups, for which a binary tree would usually qualify, however my items are not ordered based on their value - rather I need them to be ordered based on their actual insert position (i.e. like an array). All operations will access, insert or delete items based on this position, as you would with an array.</p>
  
  <ul>
  <li>getItem(int position)</li>
  <li>addItem(int insertPosition, object item)</li>
  <li>removeItem(int position)</li>
  </ul>
  
  <p>So basically the problem is that inserting/deleting an item causes all items after it to have their index shifted by 1. Clearly storing the index will never yield better than O(n), so basic binary trees/hash tables are out.</p>
  
  <p>Is there a structure that's capable of implementing all these operations sub linear time? I keep thinking that a binary tree could be adapted somehow, and I'd support lookup by index by having each node store the number of nodes in it's left branch.</p>