Undo/Redo using Memento: Stack, Queue or just LinkedList?

What is the best having when implementing Memento pattern (for Undo/Redo)

in witch collection to Keep Mementos?

Basically, I need this(c = change, u = undo, r = redo):

                  0
                  *c
            -1    0
                  *c
      -2    -1    0
                  *c
-3    -2    -1    0
                 开发者_StackOverflow <u
      -2    -1    0    1
                  *c
-3    -2    -1    0

Variants:

• LinkedList - possible in principle, maybe not optimized.
• Queue - not adapted for this task, IMO.
• Stack - not adapted for undo AND redo;
• Double Stack - maybe optimal, but can't control the undo maximum size.

Finally, I used LinkedList

Public Sub Add(ByVal item As T)
  If _list.Count > 0 Then
    If Me.IsFull Then
      ' we forgot (delete) the oldest state '
      _list.RemoveFirst()
    End If
    ' remove all the following the current items objects '
    Dim lastNode As LinkedListNode(Of T) = _list.Last
    While Not Object.ReferenceEquals(_currentNode, lastNode)
      _list.RemoveLast()
      lastNode = _list.Last
    End While
  End If

  ' add the new item and point current to it '
  _currentNode = _list.AddLast(item)
End Sub

A double ended queue is used preferably to support undo redo operations efficiently. As the user types words, nodes are inserted into the queue and head pointer points to the current location. When an undo operation is triggered, just move the head to the previous node and on redo operation move the head pointer to next location in the list. In case of edit operation, remove all the nodes to the right of head and insert at the end of head. This way we can perform undo redo in O(1) time complexity.

When you undo you are going to want to revert to the most recently overwritten data. So the memento you will want to use will be the last one added to the collection. As stacks are last in first out (LIFO) they should be ideal for your intentions.

Note: you might want to look into the command pattern as it is very useful for implementing undo functionality.

Edit: did not notice that you wanted redo. Popping stuff off your stack will get rid of it so that will not be of much use for your purposes. Linked list should work.

Do you want the user to be able to select more than one item for undo or redo?

If that is the case, then you would want to use a generic List or ObservableCollection (if WPF/Silverlight) so that the items could be displayed in the UI. You could use two lists: one for undo and one for redo.

Use a doubly-linked list. When users are using undo/redo they may index the state several times (e.g. do 4 undos, then realize they went too far and do a redo). A single stack or a queue won't support that.

Two stacks will support undo and redo, but I think using them is kind of a waste. All redo mementos will end up being deleted as soon as the user performs an edit (that creates a new memento). So, most of the time an application is running there will be no 'redo' mementos.

Assuming you have garbage collection since you tagged it .net: When a user makes an edit all you'll have to do with the doubly-linked list is set the head reference of the linked list to the current memento. If you use a stack then you'll have to either create a new stack or pop everything off it in order for the gc to free the redo mementos.