Program 2
Due Wed, Feb. 4 CSCI 271 Spring 2009
Purpose
Gain more experience working with templates and operator overloading.
Problem Statement
We want a data structure that is easy to add an element to any position. Also, we want the ability to go backwards as well as forwards. In order to insert we really need a pointer to the previous position for inserting, not the current position for inserting. For example, assume I have the list (10, 20, 30) and the current pointer is pointing to 20. If I want to add 15 (which is why the current pointer is at 20, since it had to go to 20 to determine that 15 was not in the list), then I need to change the cell with value 10's "next pointer" field. Therefore, I need a pointer to 10 also.
We could solve this problem with a pointer much like current, called prev. This pointer will always point to the element before current (it would have null when current points to head). However, one of the functions we talked about in the linked list class was a previous function that set the current to the previous element. This will cause difficulties, since when we back up current, we must back up previous also.
The simple solution is to have a previous pointer for each node. We will create a linked list where the nodes not only have the data field and the next pointer, but will also have a pointer to the previous. This will make it extremely trivial to insert at any location. We have the previous pointer for any node. (Remember, the previous of the first node will be null). This may cause a little more difficulty in creating the list, but with care and consideration, it will not be difficult.
Now we can easily implement an insertInOrder function. It will take the value to insert and place it into the linked list in its proper place. This insert in order function can use your existing find function to get current to the proper node (the value to be inserted will be inserted before this node). Your function should be able to handle an empty list also.
You are to create this TEMPLATED class.
Details
You are to call your class LinkedList and contain the following member functions. You may use additional ones if you wish.
| constructor | will set the head pointer to null and any other initializations you need |
| copy constructor | allows you to do LinkedList A(B) so that you create A as a copy of B. This is a little involved as it is NOT just copying the values of the head pointers. |
| bool empty() | true if there are no values in the list |
| int size() | returns the number of values in the list |
| void begin() | positions the current pointer at the beginning of the list |
| void clear() | removes all items from the list |
| void erase() | removes the current item from the list |
| void pushback(value) | insert value at the end |
| void pushfront(value) | insert value at the beginning |
| value popfront() | returns and removes the first value in the list |
| value popback() | returns and removes the last value in the list |
| void next() | go to the next item in the linked list |
| void previous() | go to the previous item in the linked list |
| void insertInOrder(value, compare function) | insert the value into the linked list in sorted order. |
| void remove(value) | find the node with the specified value and removes it. |
| void insert(value) | inserts value after the current node |
| list++ | move current to the next |
| list-- | move current to the previous |
| *list | return the value in the node pointed to by current |
Use the main program main.cxx in the directory /home/win.thackerw/271/p2 to test your class. Please start early so that if there are problems with my main, then they can be identified and corrected in time.
Email me your code as attachments (you may use a tar file if you wish or multiple attachments). Additionally, you are to hand in a printout of your code.
There will be a 20% penalty for each day late.