An undo stack and a redo stack

This is the most common way to implement undo and redo. It’s used in almost everything that supports undo.

Whenever you make a change, the previous state is saved to the undo stack. When you undo something, the most recent change is popped off of the undo stack and pushed onto the redo stack. Finally, if you undo some changes and then starts modifying the document, the redo stack is cleared. The means that any previous changes are gone forever after undoing and then modifying the document.

Lite has documentation on its implementation of this system.

An undo tree

This is a system that Vim uses. It’s a “non-destructive” undo system where changes can never be lost by modifying the document after undoing some changes.

It works the same as the undo and redo stack up to the point that you modify the document after undoing something. At that point, instead of clearing the redo stack, it is moved aside and a new redo stack is created. If you want to go back to the previous redo stack, you can view all of the saved redo stacks and move do another one (in Vim, this is :undolist and :undo <change number>).

You can read Vim’s documentation for more information about undo trees.

An undo linked list

GrafX2 uses a simpler non-destructive undo system. Instead of a tree, it uses a linked list. When you undo some changes, a pointer into the list of changes moves back to an earlier time. If you undo some changes and then modify the image, the change is inserted into the list at that point in time. If you change your mind and want to redo some of your old changes again, you just redo. This moves the pointer forward in the list.

GrafX2 does not document this feature because it works just like regular undo/redo systems. The only time that you might notice that something is different is when you redo past where you expect the newest item in your redo stack would be. At that point, you will find yourself in an older version of the document. This could be a pleasant surprise, because maybe you want these old changes back. However, it brings up a consequence of this system: the changes in the list are not necessarily in chronological order. After several undo/modify/redo cycles, the order of the edits in the list may not be obvious.

If you want to learn more about how this is implemented, you can refer to GrafX2’s source code, which documents the system with a beautiful mixture of diagrams, French and English comments, and C code.

An append-only undo list

Emacs uses another non-destructive undo system. The implementation is simple, but it may be a little harder for users to understand at first because there is no redo command.

There is a single undo list, like the linked list system. However, this list is never modified. Emacs only adds to the end of it. If you want to undo something, you use the undo command. This moves a pointer back through the undo list. You can undo several times to move the pointer back through the list. When you find the change you want, you can start editing the document again. At this point, the pointer is moved back to the end of the list and the state that you wanted to revert to is saved in the undo list. So now the undo list contains some typing, then a undo to a previous state, then more typing. If you want to revert to before the undo, there is no redo command. Instead, you use undo again until the pointer moves to before the time when you undid the changes you wanted to keep.

This system is more complicated than the others when you want to redo something. However, it is conceptually simple in the sense that the undo list is just a timeline of changes in the document. Undo is not treated specially. It is just another type of change to your document.

You can read more about this system in Emacs’s manual.