title: Data Structure for Transaction Queue
body: <p>Is there a more appropriate/efficient data structure for a transaction queue than using a <code>List</code>. I've tried using <code>Queue</code>s and <code>Stack</code>s, but neither fits the bill correctly.</p>
  
  <p>I've outlined my problem in detail below with examples showing why I've ended up with a <code>List</code> for the time being. Any suggestions of alternative data structures (preferably, but not limited to, those with an implementation in the .Net BCL) are appreciated.</p>
  
  <h3>Problem</h3>
  
  <p>Maintain a transaction queue of <code>Insert()</code>/<code>Delete()</code> operations that will be later persisted to arbitrary backing storage when the user calls a <code>Commit()</code> method or discarded when they call the <code>Rollback()</code> method.</p>
  
  <p>Operations must be enacted on the in-memory state of the object affected since subsequent operations may rely on the state of the object created by previous operations.</p>
  
  <h3>Example 1</h3>
  
  <p>I have an object <code>obj</code> that starts as an empty collection. The user inserts an item <code>i</code> and then deletes it.</p>
  
  <p>They then call <code>Rollback()</code>. Given the following data structures for the queue, the following happens in the rollback:</p>
  
  <ul>
  <li>Queue - <code>obj.Delete(i)</code>, <code>obj.Insert(i)</code> → incorrect, since <code>obj</code> should remain empty after rollback.</li>
  <li>Stack - <code>obj.Insert(i)</code>, <code>obj.Delete(i)</code> → correct, since <code>obj</code> remains empty.</li>
  <li>List (Reverse Traversal) - <code>obj.Insert(i)</code>, <code>obj.Delete(i)</code> → correct, since <code>obj</code> remains empty.</li>
  </ul>
  
  <p>If they call <code>Commit()</code> instead, the following happens:</p>
  
  <ul>
  <li>Queue - <code>obj.Insert(i)</code>, <code>obj.Delete(i)</code> → correct, since <code>obj</code> remains empty.</li>
  <li>Stack - <code>obj.Delete(i)</code>, <code>obj.Insert(i)</code> → incorrect, since <code>obj</code> is not empty.</li>
  <li>List (Forward Traversal) - <code>obj.Insert(i)</code>, <code>obj.Delete(i)</code> → correct, since <code>obj</code> remains empty.</li>
  </ul>
  
  <p>So, for this example, Queue works for <code>Commit()</code>, but not <code>Rollback()</code> and a <code>Stack</code> shows the inverse behaviour, <strong>but</strong> both are incorrect. The only <code>List</code> shows correct behaviour, though note that for the commit, we traverse the list in a forward direction while for a rollback, we traverse the list in a reverse direction.</p>
  
  <h3>Example 2</h3>
  
  <p>Now, consider having again an object <code>obj</code> that this time starts with the single item <code>i</code> contained in itself.</p>
  
  <p>This time, the sequence of operations is a Delete of <code>i</code> followed by an Insert of <code>i</code>.</p>
  
  <p>If they call <code>Rollback()</code>, the following happens:</p>
  
  <ul>
  <li>Queue - <code>obj.Insert(i)</code>, <code>obj.Delete(i)</code> → incorrect, since <code>obj</code> ends up as empty.</li>
  <li>Stack - <code>obj.Delete(i)</code>, <code>obj.Insert(i)</code> → correct, since <code>obj</code> contains the single item <code>i</code> still.</li>
  <li>List (Reverse Traversal) - <code>obj.Delete(i)</code>, <code>obj.Insert(i)</code> → correct, since <code>obj</code> contains the single item <code>i</code> still.</li>
  </ul>
  
  <p>If they instead called <code>Commit()</code>, the following happens:</p>
  
  <ul>
  <li>Queue - <code>obj.Delete(i)</code>, <code>obj.Insert(i)</code> → correct, since <code>obj</code> contains the single item <code>i</code> still.</li>
  <li>Stack - <code>obj.Insert(i)</code>, <code>obj.Delete(i)</code> → incorrect, since <code>obj</code> ends up as empty.</li>
  <li>List (Forward Traversal) - <code>obj.Delete(i)</code>, <code>obj.Insert(i)</code> → correct, since <code>obj</code> contains the single item <code>i</code> still.</li>
  </ul>
  
  <p>As with the previous example only using <code>List</code> is correct in both cases, but we have to traverse it in different directions depending on whether we are committing or rolling back.</p>
  
  <h2>Bottom Line</h2>
  
  <p>While using a <code>List</code> is not inefficient in itself, I just wondered whether there was a more appropriate data structure that is a better fit for my problem?</p>