title: Iterable O(1) insert and random delete collection
body: <p>I am looking to implement my own collection class.  The characteristics I want are:</p>
  
  <ol>
  <li>Iterable - order is not important</li>
  <li>Insertion - either at end or at iterator location, it does not matter</li>
  <li>Random Deletion - this is the tricky one.  I want to be able to have a reference to a piece of data which is guaranteed to be within the list, and remove it from the list in O(1) time.  </li>
  </ol>
  
  <p>I plan on the container only holding custom classes, so I was thinking a doubly linked list that required the components to implement a simple interface (or abstract class).  </p>
  
  <p>Here is where I am getting stuck.  I am wondering whether it would be better practice to simply have the items in the list hold a reference to their node, or to build the node right into them.  I feel like both would be fairly simple, but I am worried about coupling these nodes into a bunch of classes.</p>
  
  <p>I am wondering if anyone has an idea as to how to minimize the coupling, or possibly know of another data structure that has the characteristics I want.</p>