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

Completed Posted 6 years ago Paid on delivery
Completed Paid on delivery

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.

.NET C Programming C# Programming C++ Programming Software Architecture

Project ID: #16418466

About the project

10 proposals Remote project Active 6 years ago

Awarded to:

hanumachari

I have 8+ yrs of experience in C/C++/Datastructures developing large complex telecom products. I can deliver your project as per your requirements using suitable data structures and algorithms, I assure you that I w More

₹750 INR in 1 day
(2 Reviews)
0.6

10 freelancers are bidding on average ₹1260 for this job

xzan88

Hi, I have read the description. I can do this in C/C++ in a few hours. Please contact me if you're interested in working with me.

₹1500 INR in 1 day
(107 Reviews)
6.3
stevegtdbz

Hello my friend, I have experience in C/C++ and data structures Please check my profile and let me know if you are interested.

₹1250 INR in 1 day
(27 Reviews)
4.5
aritron

I am experienced c/c++ programmer and can perform this activity in a day. Please get back. I can start immediately.

₹1450 INR in 1 day
(8 Reviews)
3.5
vaibhav1685

A proposal has not yet been provided

₹1250 INR in 1 day
(1 Review)
0.5
isc2013008

A proposal has not yet been provided

₹1750 INR in 2 days
(0 Reviews)
0.0