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

Question

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
                  <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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

Hi Try UndoEngine from www.undomadeeasy.com. It does it all the list management automatically for you. You just have to think about your own application - not all tricky bits. Rgrds Carl