Program 1
Due Wed. Jan. 21 CSCI 271 Spring 2009
Purpose
Gain more experience working with linked lists and pointers.
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 insert 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.
The data field in the linked list will contain an integer (for now, we will use templates in the near future).
Details
You are to call your class LinkedList and contain the member functions (you may include others, but these need to be used as is):
| 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(int) | insert value at the end |
| void pushfront(int) | insert value at the beginning |
| int popfront() | returns and removes the first value in the list |
| int 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(int) | insert the value into the linked list in sorted order. |
| void remove(int) | find the node with the specified value and removes it. |
| value data() | return the value at the current position |
| void insert(int) | inserts value after the current node |
| void sort() | sorts the values in the list (must allow for any number of values) EXTRA CREDIT |
| void merge(LinkedList) | merges the values from the sorted list indicated by LinkedList into this sorted list EXTRA CREDIT |
Use the main program main.cxx in the directory /home/win.thackerw/271/p1 to test your class. You can use mainec.cxx to test the extra credit part.
You are to email me your program file(s) as well as turn in a printout in the class.
Design, implement and test a small subset of these operations first. I would suggest the constructor, pushback, data, begin and next. Then write a small main to test these methods. If they don't work then none of the others will work. This way if there are design problems you can make the changes in design without having to change many of the methods.
20% off per day late. Late starts at 9:05 on due date.