Undo function to the Linked List class

Question

Hey I'm a beginner in C++ and I want to Add an Undo function to the linkedList class in C++ , The function reverses the last operation done on the list such as (append , insertAt , deleteAt , clear ) , Any ideas about what is the best way to go about undoing these commands ?

Answer 1

I can think of two simple ways to accomplish the magic of "undo": by holding changes in a queue until you have really have to push them, or by pushing a reverse operation to each change you make into an undo queue.

The first would look like this:

User Action  | Action Queue      | actual list
---------------------------------------
  nothing    |  empty            |  {}
  push 5     |  {push 5}         |  {}
  push 2     |  {push 2, push 5} |  {}
  print list |  {}               |  {5, 2}

Only when the user does an action where you need to percolate the changes (like a print or a get) do you actually make the changes. Then an undo would just be a pop off of the action queue.

The other option would be to store a reverse queue:

User Action  | Reverse Queue       | actual list
---------------------------------------
  nothing    |  empty              |  {}
  push 5     |  {pop}              |  {5}
  push 2     |  {pop, pop}         |  {5, 2}
  pop        |  {push 2, pop, pop} |  {5}
  undo       |  {pop, pop}         |  {5, 2}

Here anything the user does is percolated immediately and you push a reverse of the action onto the Reverse Queue. Then an undo is to pop off the Reverse queue and take the action.

While the first is far easier to implement, it means you lose the ability to undo after "the changes are pushed."