Data Structure for Transaction Queue

Is there a more appropriate/efficient data structure for a transaction queue than using a List. I've tried using Queues and Stacks, but neither fits the bill correctly.

I've outlined my problem in detail below with examples showing why I've ended up with a List 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.

Problem

Maintain a transaction queue of Insert()/Delete() operations that will be later persisted to arbitrary backing storage when the user calls a Commit() method or discarded when they call the Rollback() method.

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.

Example 1

I have an object obj that starts as an empty collection. The user inserts an item i and then deletes it.

They then call Rollback(). Given the following data structures for the queue, the following happens in the rollback:

• Qu开发者_如何转开发eue - obj.Delete(i), obj.Insert(i) → incorrect, since obj should remain empty after rollback.
• Stack - obj.Insert(i), obj.Delete(i) → correct, since obj remains empty.
• List (Reverse Traversal) - obj.Insert(i), obj.Delete(i) → correct, since obj remains empty.

If they call Commit() instead, the following happens:

• Queue - obj.Insert(i), obj.Delete(i) → correct, since obj remains empty.
• Stack - obj.Delete(i), obj.Insert(i) → incorrect, since obj is not empty.
• List (Forward Traversal) - obj.Insert(i), obj.Delete(i) → correct, since obj remains empty.

So, for this example, Queue works for Commit(), but not Rollback() and a Stack shows the inverse behaviour, but both are incorrect. The only List 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.

Example 2

Now, consider having again an object obj that this time starts with the single item i contained in itself.

This time, the sequence of operations is a Delete of i followed by an Insert of i.

If they call Rollback(), the following happens:

• Queue - obj.Insert(i), obj.Delete(i) → incorrect, since obj ends up as empty.
• Stack - obj.Delete(i), obj.Insert(i) → correct, since obj contains the single item i still.
• List (Reverse Traversal) - obj.Delete(i), obj.Insert(i) → correct, since obj contains the single item i still.

If they instead called Commit(), the following happens:

• Queue - obj.Delete(i), obj.Insert(i) → correct, since obj contains the single item i still.
• Stack - obj.Insert(i), obj.Delete(i) → incorrect, since obj ends up as empty.
• List (Forward Traversal) - obj.Delete(i), obj.Insert(i) → correct, since obj contains the single item i still.

As with the previous example only using List is correct in both cases, but we have to traverse it in different directions depending on whether we are committing or rolling back.

Bottom Line

While using a List is not inefficient in itself, I just wondered whether there was a more appropriate data structure that is a better fit for my problem?

Technically you could use a LinkedList<T>. It's like a Queue + Stack: you can add and remove from head and from tail, and in both cases it's O(1) (but it's normally slower than a List, for reasons connected to memory locality and the need to allocate memory for each adding of an element).

(Please, don't kill me because I said a LinkedList<T> is like Queue + Stack… I know the difference… I meant only that it can be used in both ways at the same time.)

I'll add that, if you consider Rollback an "exception" (something rare), then you can use a Queue and, when you have a Rollback, Reverse the output of the Queue using LINQ. Being an "exception", it can be slower (and you don't even need LINQ… You can do a ToArray() and traverse the array in reverse order).