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

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