## CS 112 Project 5: List Operations

### Objectives:

1. Build more List operations.
2. Practice using pointers.
3. Practice using the debugger (if necessary).

### Introduction

This week's project is a team project to add more functionality to the List class we built in this week's lab. To illustrate, suppose that list1, list2, and list3 are List objects containing the following values:

`   list1 == {11, 22, 33}`
`   list2 == {11, 22, 33}`
`   list3 == {}        // the empty list`
1. Equality. An expression like:
`   list1 == list2`
should return true; an expression like:
`   list1 == list3`
should return false.
2. Inequality. An expression like:
`   list1 != list2`
should return false; an expression like:
`   list1 != list3`
should return true.
3. Stream Input. The expression:
4. `  list3.readFrom(cin);`
should read an arbitrary number of values from cin, appending each value to list3. This method should read the character that follows each value, and halt when that character is the newline ('\n') character. In other words, this method should assume that all values to be read into the list are on the same line.
5. Stream Output. The expression:
`  list1.writeTo(cout, '\t');`
should write the values of list1 to cout, with items separated by tabs. Your method should allow the user to pass whatever separator they wish to use.

6. File Input. The expression:
`  list3.readFrom(fileName);`
should fill list3 with values stored in fileName. This method should assume that fileName contains only values; it should continue reading and appending values to the List until end-of-file is reached.
7. File Output. The expression:
`   list1.writeTo(fileName, '\n');`
should write all of the values in list1 to the file named by fileName, with each item on a separate line of the file. Your method should let the user pass whatever separator they wish to use.
8. Prepend. The expression:
`   list2.prepend(-1);`
should change list2 as follows:
`   list2 == {-1, 11, 22, 33}`
The operation aList.prepend(it) thus inserts it at the beginning of aList.
9. Searching. The statement:
`   int index = list1.getIndexOf(22);`
should set index to 1, because if our List were an array, 1 is the index at which 22 would reside. More generally, the operation aList.findIndexOf(it); should start at the beginning of the list, and return the index of the first occurrence of it. If it is not present in aList, this operation should return -1.
10. Insertion. If list2 is as we just left it, the expression:
`list2.insert(0, 1);`
should insert the value 0 into list2 at index 1:
`list2 == {-1, 0, 11, 22, 33}`
More generally, the operation aList.insert(it, index) should insert item it into aList at index index. If index is negative or zero, insertion should occur at the front of the list; if index is greater than or equal to the size of the list, insertion should occur at the end of the list.
11. Deletion. If list2 is as we just left it, the expression
`Item it = list2.remove(0);`
should remove the node at index 0 and return its Item (-1 in this case):
`list2 == {0, 11, 22, 33}`
More generally, the operation aList.remove(index) should remove the item at index index in aList, reclaiming its Node's dynamic storage, and returning the Item at that index. If index is negative or zero, the first Node in the list should be removed and its Item returned; if index is greater than or equal to the size of the list, the last Node in the list should be removed and its Item returned.

As indicated on the grade sheet, different members of your team are responsible for different operations. See me for the teams for this project. The person responsible for a given operation is also responsible for building a test-method for that operation. (Alternatively, you may if you wish write the test-cases for your team-mate's operations (and vice versa); just indicate in your test-classes who did what.) A part of your grade will be based on the thoroughness of your tests; you may want to use model your tests after those provided for you in previous projects.

I strongly encourage you to "design" your operations by drawing a diagram of what you want to have happen, showing the data structure before your operation is performed and then showing how it has changed after your operation has been performed. Once you have a diagram of what you want to happen, you are more likely to write code that actually does the right thing. (Lists and pointers are not something you can get right by trial and error.) Be careful to watch out for "special cases" (like empty vs. non-empty Lists).

If you get to the point where you cannot figure out what is wrong, use the debugger! The debugger is your friend when it comes to finding bugs in Lists and pointers.

Template. When you have "finished" your List class, convert it to a List<Item> template and modify the tests in ListTester to test your new template.

### Submit

• A hard copy of this grade sheet, attached to a hard copy of a script file that lists the files in your project, shows that it compiles/links correctly, and shows it correctly running and providing the required functionality.