title: Data structure that has constant time for insertion, contains, remove and getting elements by index
body: <p>I have a large data set of <code>Person</code> objects which are queued up in a list. I want the data structure to be able to do the following operations efficiently.</p>
  <ol>
  <li>Add a <code>Person</code> at the end of the queue.</li>
  <li>Remove the first <code>Person</code>.</li>
  <li>Find whether a particular <code>Person</code> exists, if so, remove it and put it at the end of the queue.</li>
  <li>Get a particular <code>Person</code> by its position.</li>
  </ol>
  <p>Is it possible to have O(1) time for all of these operations?
  So far I have come up with two ways, but they are not optimal.</p>
  <ol>
  <li><p><code>ArrayList&lt;Person&gt;</code> + <code>HashMap&lt;Person, Integer&gt;</code></p>
  <p>The <code>HashMap</code> stores the index of the <code>Person</code> objects. This gives O(n) time for operation 2 and 3 (removing element in the <code>ArrayList</code>)</p>
  </li>
  <li><p><code>ArrayDeque&lt;Person&gt;</code> / <code>LinkedList&lt;Person&gt;</code></p>
  <p>They give O(1) for first 2 operations, but O(n) for the last two.</p>
  </li>
  </ol>
  <p>Space complexity must not be larger than O(n) in my case. Operation 4 is less intensive, so I could tolerate a slightly inefficient way to do this.</p>
  <p>Any suggestions would be appreciated. Thanks in advance!</p>