title: Sparse array with O(1) indexing and O(1) prev and next
body: <p>I want to implement data structure with operations both pertinent to arrays - i.e. indexing, and linked list - quick access to prev/next item. Resembles sparse array, but the memory is not a concern - the concern is time complexity. </p>
  
  <p>Requirements:</p>
  
  <ul>
  <li>key is integer with a limited range <code>1..N</code> - you can afford to allocate an array for it (i.e. memory is not a concern)</li>
  </ul>
  
  <p>Operations:</p>
  
  <ul>
  <li><code>insert(key, data)</code> - O(1)</li>
  <li><code>find(key)</code> - O(1) - returns the "node" with data</li>
  <li><code>delete(node)</code> - O(1)</li>
  <li><code>next(node)</code> - O(1) - find next occupied node, in the ordering given by key</li>
  <li><code>prev(node)</code> - O(1)</li>
  </ul>
  
  <p>I was thinking of implementation in an array with pointers to the next/prev occupied item, but I have problems in the <code>insert</code> operation - how do I find the prev and next items, i.e. the place in the double linked list where to put the new item - I don't know how to make this <code>O(1)</code>.</p>
  
  <p>If this is not possible please provide a proof.</p>