Program 8

Writing Classes with Linked Lists

Informatics Core II
INF-42

Introduction This programming assignment is designed to ensure that you know how to write classes that store collections of data using linked lists. You will be writing methods that manipulate the nodes that comprise a linked list; the class will declare instance variables to store a reference to the front of this list and keep track of the number of nodes that it stores. Of course, you will continue gaining experience with the standard control structures in Java (blocks, ifs, loops/breaks) as well as the more basic Java features (declarations and expression statements using arithmetic, state-change, relational and logical operators).

You will write just one class in this assignment. I will provide a driver program that you will use to test this class. As always, you can check the behavior of your programs against mine by downloading, unzipping, and then running the file Program #8 Executables, to help you understand the specification of the problem and observe the programmer/user interaction that you are to implement. Use the toString option liberally, to examine the contents of the arrays storing the information.

See Program #1 for details on how to run these executables on both PCs and in Eclipse (PCs and Macs). Remember, you can run these programs, but not examine their source (Java) code.

To start working on this assignment, download Program #8 Project Folder which contains a template for the class that you should write for this assignment, some other completely written classes, and the driver program that you should use to test these classes. When you finish, submit the Sequence.java file.

Note that the methods/classes in Sequence are all written or stubbed; so the driver program compiles but fails to work correctly until you write the required code.

Only one programmer of the pair should dropoff the programs. It doesn't matter which of the pair submits. Of course, the program should contain both student names (in the comment: the same one you cut, pasted, ane filled in at the top of each program in Program #1).

Sequence Collection Class You are to read and write the unwritten methods in the Sequence collection class. A sequence is just collection of values whose order is important; programmers using this class can insert, put, and remove values in specified indexes in the sequence (as well as empty all the values out of a sequence or reverse the order of its values). They can also examine the values stored at and indexes, find the index storing a value, and get other useful information (e.g., the size of the sequence). Finally, by using classes implementing the Decision interface, we can count how many values in the collection return true according to some Decision object's isOK method, or construct a new sequence containing only those values that return true according to some Decision object's isOK method.

The constructor for Sequence is written; the toString method is also written. First, examine the two instance variables declared for this class (for storing a reference to the first node in the sequence. Second, observe and understand how the constructor and written methods examine/update values in these variables.

The class uses objects from the LN (List Node) class to store all the values in a sequence. The size of the collection is the number of values stored in nodes in this collection; we cache this value, updating it when values are added and removed from this collection, so that we do not have to compute its value by traversing the linked list.

There is one private helper method you must write: referTo. This method takes an int parameter ith and returns a reference to the ith node in the list: 0 refers to the front (first) node. If ith < 0 or ith >= size it returns null (the ith node doesn't exist). Call this method as a helper in other methods. Hint: Often it is called to refer to the node "one before" the node you are interested in processing, with a special case check for processing the first node in the list (which doesn't have a node before it).

The public methods you must write are the accesors get, getSize, isEmpty, findIndex, countTrue, and filterTrue; and also the mutators makeEmpty, putAt, insert, insertAt, removeAt, remove, and reverse. The details of each of these methods is specified inside the Sequence.java file; reach them carefully. Each method is written in stubbed form (with a correct header but a generic body). If a method must check its parameters and throw an exception, execute this code first in the method (and supply a helful message in the exception: see my messages by testing my executable). The driver allows you to test each method individually, and also includes and automatic testing feature.

I suggest writing the insert method first (it basically adds a value to the end of the linked list) and testing it by calling toString. Then try writing and testing each of the "simple" accessors (all except countTrue and filterTrue, although you might find writing these simple methods as well). Try writing and testing each mutator in the order listed above. You can write remove by a simple combination of calling the findIndex and removeAt method. While this traverses the list twice, it is still an O(N) operation. If you haven't already written countTrue and filterTrue, write these methods. Finally, you can use the driver to perform an autotest on all these methods.

Note that these are the same operations you implemented using an array in Programming Assignment #5. Whether you used the array-based or list-based version of this class, your code should produce the same, correct results. The only difference should be in performance: the amount of time needed to perform the various operations.