Implementing Undo

In many applications, there is an “undo” feature that allows users to reverse their most recent actions. For example, in a text editor, you might want to undo the last change you made to a document. There is often a shortcut for this, such as Ctrl+Z on Windows or Command+Z on Mac.

To implement an undo feature, we need to keep track of the actions that the user has performed, in the order they were performed. We can use a data structure like ArrayList or LinkedList to store these actions. Each time the user performs an action, we add it to the end of the list. When the user undoes an action, we remove the most recently added action from the list and reverse its effects.

Let’s walk through a short session to see what order this produces. Say the user types “cat”, then makes the word bold, then deletes the “t”. The list of actions grows in that order, with the newest action at the end:

index:   0            1       2
action:  type "cat"   bold    delete "t"

Now the user presses Ctrl+Z three times. The first undo has to bring the “t” back, because deleting the “t” was the last thing that happened. That action is at index 2, the end of the list, so we take it and reverse it. The second undo reverses the bold, now at the end of the list. The third undo reverses the typing of “cat”:

undo 1  reverses  delete "t"    (index 2)
undo 2  reverses  bold          (index 1)
undo 3  reverses  type "cat"    (index 0)

Notice that the undo feature only ever needs the most recently added action. We never look up an action at any position other than the end of the list, and we never remove one out of order. So it makes sense to restrict the data structure to allow adding and removing only at the end of the list. This restriction also gives us a guarantee. If the structure does not let us get at any position other than the end, then no part of our program can accidentally disturb the order of the actions.

The undo feature is just one example of an application that would need this type of “limited access” data structure. A web browser’s back button is another one. It allows users to go back to previously visited pages. Many algorithms also need a similar structure, and you will see some of them in this chapter’s practice problems.

In this chapter, we will look at a data structure called a stack. A stack gives us this type of limited access, and we can use it to implement features like undo. The call stack is another example of a stack. A method returns to the call that invoked it most recently, which is the same order we just saw with undo.