Implementing the List ADT

Part 0: A tour of the List class

In this lab, you'll get a chance to take something that works well on its own and make it even better! You'll interact with two files: LabList.h and lab07_driver.cpp. You should copy these files to your local directory for usage.

Your goal for Part 0 is to get familiar with the List class as it appears now. Pay attention to lines 67-70, as these represent the new functions that you'll implement (and properly comment). You should also note that, outside of changes you'll make to Iterator's private member section and Iterator's constructor and next() implementations, all the changes you'll make are in the last part of the file (below line ~170).

To reassure yourself that the program works as implemented, go ahead and compile/link LabList.h and lab07_driver.cpp. You should see something like this:

The program doesn't do what it's supposed to do, but that's where you come in! You should not make any structural changes to lab07_driver.cpp but feel free to comment out any blocks of code (Parts 2-4, for example) inmain if you don't want them to display while you work individual parts. Note that you'll likely need earlier blocks of code to run later blocks, so if you're working on Part 3 make sure Parts 1 and 2 aren't commented out! You can comment out blocks of code by using /* and */ as necessary. For example:

/*
  // Here is some example code that
  // will be commented out:
  int x = 2006;
  string daBest = "two thousand six";
*/

Make sure you comment your code implementations. This will only help you in the long run. The skills you learn from implementing each part should help with future parts, so making sure you understand what's going on at each step will help tremendously!

Part 1 (20 points): Implement a length function

Implement a function called length which will return the number of nodes. This can be done quite simply by using the nested class Iterator to cycle over the items in the list. Note that this is a const function so you may not change the list contents of the function caller. The requirements are as follows:

• You should handle the case of an empty list should the user pass one to length (in other words, only attempt to do work on a list if it actually has elements!)
• Any "count" variable must be local to the length function and should not be a member variable of List. (I'll submit that there are other ways to implement length, but I don't want you modifying my add2frontor add2rear functions!)

If you've implemented it correctly, you should see "Part 1 - Length: 5" print out when you run lab07_driver.cpp.

Part 2 (20 points): Implement a list-copying function

Implement a function called copyList which will copy the List which called copyList into an empty list passed by reference. Note that this is also a const function so you may not change the list contents of the function caller, but changes can (and must) be made to the list which was passed in. Again, for this part (and every part for that matter) the Iterator class makes your task much simpler. The requirements are as follows:

• You should handle the case of an empty list should the user pass one to copyList (in other words, only attempt to do work on a list if it actually has elements!)
• You should perform a deep copy of the list by actually adding them to the new list. If you simply point the new list to items in the original list, the new list will be changed if the old list is changed in any way!

If you've implemented it correctly, you should see "Part 2 - Copy: this is just a test" print out when you run lab07_driver.cpp.

Part 3 (30 points): Implement an "insert before iterator" function

Implement a function called insertBefore that will take a value to add to the list and an Iterator pointing to the node in front of which the value should be added. Whereas the other functions were relatively straightforward, inserting a new node is relatively tough. This is because you need to know what the Iterator's previous node was so that you can set that node's next pointer appropriately. That means that you'll have to augment the class Iterator by giving it another data member:

Node *pred;

For an iterator to the first node in the list, of course, pred will simply be set to NULL. After next() is called, it'll be set to point to the Node immediately before the current node (in other words, the node curr was just pointing to). The requirements are as follows:

• You should add pred to Iterator and modify the constructor and next function appropriately.
• Once you've done the above you should implement the insertBefore member function to handle three cases of modifying the List as it was passed in:
  1. The list is empty so we're adding the first node.
  2. The iterator is pointing to the current first node so we're adding to the front of the list and creating a new first node.
  3. The iterator is pointing to some other node so adding a new node to any remaining part of the list will be the same.
• The iterator should remain pointing to whatever it was before the list addition, but pred should be updated if necessary.

Convince yourself that in the first case pred should still point to NULL, in the second case pred should point to the first node, and in the third case pred should point to the node we just inserted. To make clear how it should work, if the current configuration of list L and iterator I is this:

and you do a L.insertBefore("true",I), afterwards list L and iterator I ought to look like this:

If you've implemented it correctly, you should see "Part 3 - Insert: this is really just a test" print out when you run lab07_driver.cpp.

Part 4 (30 points): Implement a remove function

Implement a function called remove that will take an Iterator pointing to the node to be removed. With your added Iterator functionality from Part 3, this should be conceptually clear. However, you'll need to handle four cases of modifying the List, similar to Part 3:

1. The list is empty (so you should do no work!)
2. The iterator is pointing to the head node.
3. The iterator is pointing to the tail node.
4. The iterator is pointing to some other node that's neither the head nor the tail.

You should think about how (or if) you should modify List and Iterator pointers in each of the above cases. You'll also need to make a call to delete on the node in question (as not to have any memory leaks), so I recommend making a temporary node pointer that will remember which node you want to remove while you make the necessary modifications. As always, though, there are multiple ways to solve this problem so do what makes sense to you (and make sure you call delete)!

If you've implemented it correctly, you should see "Part 4 - Remove: this is really a test" print out when you run lab07_driver.cpp.

Solved Example

If you successfully complete all parts of the Lab your output should look like this:

Deliverables

Due: 2359, Monday 22 Oct 2018

Submit your modified and commented LabList.h source code via the the submisison website: submit.cs.usna.edu.
Note: Be sure to indicate in the comment block at the top on your submission the highest part you completed if you did not complete the entire lab.

Ensure your file is named exactly as specified. Do NOT submit any additional files, including the lab07_driver.cpp file.

~/bin/submit -c=SI221 -p=Lab07 LabList.h