What's the best data structure for (undo-redo)?

Question

What is the Best Data Structure for Undo/Redo , (ctrl+z , ctrl+y) ? Before few days our teacher said that the stack is the best for undo , but i am thinking about double-linked list ..

is there any another data structure do our purpose in a better quality ? or one of those two lead our purpose & which one of them ? PS : if there is better data structure then explain it using (oop) -java preferred- & thanks for help

Answer 1

put all the actions in a stack for multi level undo. and in case of redo make another stack.this stack will keep all the commands you have undone.so when you perform an undo command you pop undo stack and push the action into redo stack.You do same thing into redo .when you pop a redo action put it into undo stack

Answer 2

Undo/Redo are stack based (first in, last out) operation from principle, so you need some kind of stack based architecture to store actions.

With that being said, the way how you stack behaviour can differ based on other requirements of your application. Usual way is to have stack backed by array - you keep current index of last element and you add (remove) new stuff elements to at that index and increase (decrease) ot accordingly

But you can also implement this first-in-last-out behaviour in a different way, for example double linked list - you will keep reference to the last element of the list and either add new to the end (and update this reference) or remove last element (and also update the reference to the new last). Giving yourself stack-like behaviour

EDIT:

For redo you keep separate stack, where you push commands whenever you undo them, so you can use it later (pop from redo stack, do it, push to undo stack) It is important to clear redo stack when you push new (e.g. not from redo stack) command to undo stack