C/C++ code - 04/03/2018 10:31 EST

linear (non-circular), singly linked list without dummy nodes. It contains integers in non-decreasing sorted order and supports the usual find, insert and delete operations, plus two new operations called undo and redo. A list is considered to be the most recent version after we apply an edit ( insert or delete) operation. The undo operation allows us to change the list back to a previous version, by reversing the last edit operation. We can call undo n times to reverse the last n edit operations. If there is no previous edit operation (because the list is new, or because all edit operations has been undone), undo does nothing. A redo operation cancels the previous undo operation and is used to update the list back to the next more recent version. We can call redo multiple times consecutively to cancel multiple undo operations. To support undo and redo operations in constant time, you need to keep copies of previous versions of the list. Then, undo and redo can just switch between different versions of the list. To reduce memory requirements, you should keep only a finite number of most recent versions. Attempting to undo beyond the oldest version kept will not have any effect on the list. You are to complete following methods using programming language of your choice using the scheme described previously: getHead() : Returns the head of the list. find(int v): Returns true if value v exists in the list, returns false otherwise. insert(int v): Inserts value v into the list, maintaining sorted order. delete(int v): Deletes the first occurrence of value v from the list. If v does not exist in the list, do nothing. undo(): Revert the list back to the previous version by canceling the last edit operation. If no previous version exists (either we have reverted to the oldest version available or the list is new), it has no effect on the list. redo(): Reapply the operation cancelled by the last undo operation. It has no effect on the most recent version of the list. As an example, consider a list L containing 2, 5, and 7, denoted as [2,5,7]. The following shows the sequence of operations executed and the list after each operation. 1. insert(6) // [2,5,6,7] 2. delete(5) // [2,6,7] 3. undo // [2,5,6,7], delete(5) cancelled. 4. undo // [2,5,7], insert(6) cancelled. 5. redo // [2,5,6,7], last undo cancelled, re-apply insert(6). 6. insert(4) // [2,4,5,6,7] 7. redo // [2,4,5,6,7], nothing to redo. 8. delete(3) // [2,4,5,6,7], 3 is not in the list, L remains unchanged. 9. undo // [2,4,5,6,7], delete(3) cancelled. 10. undo // [2,5,6,7], insert(4) cancelled.