CSc 150

Project 5 -- It's in the Bag, Part II
Due: Wednesday, May 12, 2010

Objectives

Reinforce how the behavior of an object is completely separate from its implementation (i.e. information hiding)
Practice with the linked list data structure

You're not quite done with your Bag class yet. If you look closely at the public interface (the prototypes of all of the public methods) of the Bag class that you made for Project 4, you'll notice that none of them reveal that arrays are being used for the underlying implementation. That's the point. Despite the fundamental differences between arrays and Bags (arrays can't expand and contract while bags can), a programmer wishing to build upon the Bag class doesn't need to know about arrays in order to use the class you made. That means that as long as you keep the same public interface for Bag, you can alter/upgrade the underlying implementation and not affect in any way anybody else's code that happens to use your Bag class. You'll prove that in this project as you switch from an array-based Bag to a linked-list based one.

Your Mission

Redo Project 4 in its entirety, but this time, use a linked list to hold the data members of a bag instead of an array. You must keep the exact same public interface that was given in Project 4. You will need to write two new classes: a ListNode class to define the structure of a single data node, and a LinkedList class to define the linked list structure along with the methods for manipulating the linked list. Notice that I'm not telling you what methods should be included in your LinkedList class. You should include methods that each deals with a single task involving manipulating a linked list (insertion, deletion, etc.) and write them in as general a way as possible, just as was shown in Chapter 3 of your text. Remember, only the instance variables in your ListNode class are allowed to be public. You are not allowed to use Java's LinkedList class or any of Java's built-in container classes like Vector or ArrayList in your program.

If you lost points for insufficient testing in Project 4, here's your chance to correct those deficiencies. Remember, each test should make it clear what is being tested, what is expected, what the actual results were, and if the test passed or failed. I've given you the results of my own testing of your array-based Bag, and those results should prove valuable in constructing better tests for your code this time around.

Remember to be modular. The LinkedList class I showed in lecture contains a method for generically inserting a node into the list. This makes the class reusable by any class needing to insert nodes into a linked list. So when your Bag class needs to add a new element to a bag, it should do so by invoking a method in the LinkedList class instead of having the add() method access the linked list directly. At the same time, however, remember that your LinkedList methods need to represent general behavior that would be usable by anyone who needs a container of data. If a method in LinkedList is too specific to this project, then it's not reusable. For example, if there's a 1-1 correspondence between the methods in Bag and the methods in LinkedList (so there's a union method, a copy method, etc. in LinkedList) you're doing something wrong. union is something bags can do, not linked lists. That is, union defines Bag behavior. While you could define a union method in LinkedList, doing so only makes sense for this project, unlike, say, a search method, which is something you'd like to do with any container.

As mentioned previously, many of the methods are easier to write if you use the more "basic" methods within them. For example, as shown in class I created equals with the help of contains, remove, and a few others. Doing so keeps you from writing the same code over and over again. As you do this project, take note where you use those "basic" methods inside other methods. You should find that those methods that mainly call other methods to get their job done should require very little modification on your part. That's the idea behind reusability. If a given method's behavior doesn't change, then code that uses it will still work, regardless of how that method accomplishes its task.

A word about Size and Capacity

It's important to remember that a computer program is just a model for some system in the real world. In this case, your Bag class is a model for a container and all containers have a size and capacity. The distinction is easy to see when the bag is array-based, but the line becomes blurred with a linked-list-based bag. If the capacity is 10 but the size is 3, does that mean you have 7 "empty" nodes? Or should all nodes be full all the time? If there are no "empty" nodes, what does "capacity" mean? These are important design decisions that you need to consider early on before writing any code. I'll talk more about this point in class.

Extra Credit alert: Your Bag could become even more reusable by implementing a Java interface like the Containable interface I showed in class. Extra credit will be given for implementing it in this project. You'll have to alter your test methods from last project to accommodate the interface.

As always, practice good programming skills:

Use comments that reveal the purpose of your code. Use Javadoc format for all comments.
Test each method individually instead of trying to get the code to work all at once
Use good debugging skills: tracing, echo printing, and checkpointing
Be modular by using private auxiliary methods to do subtasks.

Remember to turn in both a paper and an electronic copy of your project.

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Gentle Reminder

Programming assignments, like homework assignments, are individual projects. I encourage you to talk to others about the general nature of the project and ideas about how to pursue it. However, the technical work, the writing, and the inspiration behind these must be substantially your own. If any person besides you contributes in any way to the project, you must credit their work on your homework. Similarly, if you include information that you have gleaned from other published sources, you must cite them as references. Looking at, and/or copying, other people's programs or written work is inappropriate, and will be considered cheating.