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);
    should write the values of list1 to cout, with items separated by tabs.

  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);
    should write all of the values in m to the file named by fileName, with each item on a separate line of the file.
  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.

I strongly encourage you to "design" your operations by drawing a diagram of what you want to have happen. 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 best 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


CS > 112 > Projects > 05


This page maintained by Joel Adams.