HW 1 - A Trip Planner


SETUP

Note that in this assignment, you will have to use the eclipse IDE. To start:


Making and Using A Trip List

A linked list is a useful data structure for managing sequential data where you may have to periodically add data at the start or at the end or remove data from the start or end, and where random access of individual pieces of data is not common. In fact, linked lists are typically used in such a way that all the data gets processed at once, in order, from start to finish, which we'll do using an iterator. In this assignment, you are going to define methods for manipulating a singly linked list that can store data of any Object type. You will then see one potential use of a linked list, for managing stops on a trip.

Examine the following 4 files:

Go through the code of these classes and read the documentation. TripPlanner has a main method. Try running it. It will display a GUI (Graphical User Interface) and will provide controls to test your linked list methods. In addition, I have provided a test class called HW1TestProgram. This class tests some (not all) of your methods in a few simple ways, and you can and should add further tests to this class to test your methods.

A singly linked list - The SinglyLinkedList class manages a linked list of Objects, meaning it can store any type of data. The TripPlanner class uses it to manage TripCity objects, while the HW1TestProgram program demonstates using it to manage Strings. The linked list you'll be manipulating has both a head node and a tail node, and you must make sure to properly maintain these instance variables at all times. In addition, the class has a size instance variable which you must make sure to maintain. In this assignment, you are going to write methods in this class for manipulating nodes in various ways. Remember to carefully handle all special cases.

Your 10 methods inside SinglyLinkedList


What's an Iterator? Iterators are a common tool for traversing through all the data in order in a linked list in both the Java and C++ programming languages. In addition to defining methods for linked list manipulation, in this assignment you will define a custom iterator, ListIterator which is an inner class of SinglyLinkedList, and which implements Java's Iterator interface. This interface has 3 methods, hasNext, next, and remove, though we really only care about hasNext and next. Anytime one wishes to go through all the elements in a linked list, one can get a custom iterator object (i.e. call the listIterator method) and as long as there are more items to fetch (hasNext is true), we can fetch the current item and move on to the next one.

Note that an iterator is just a disposable object used to go through a linked list once. Each time one wishes to go through all the elements in the list, one will have to construct a brand new iterator object. So how should these methods work? Well, my TripPlanner class, for example, uses your iterator to go through all the list data in order to draw the trip onto the map. In the HW1TestProgram we use an iterator to print out a textual representation of each piece of data in the list. We can do so by writing:

Iterator it = linkedList.listIterator();
while(it.hasNext())
{
  Object obj = it.next();
  System.out.println(obj);
}


Your 2 methods inside ListIterator, which is an inner class defined inside SinglyLinkedList


SAMPLE OUTPUT

As I mentioned, you can and should add further tests to the HW1TestProgram program. This does some basic tests, but does not do so thoroughly. As it exists, running the program should produce the following output:

Current List:
A->C->D->C->null

Current List:
C->D->C->null

Current List:
A->B->A->C->A->B->null

Current List:
A->B->B->A->null


As for the TripPlanner program, if your linked list methods are defined properly, it should allow one to create a trip, adding, inserting, and removing nodes. This trip would then be drawn over the map. One such trip might involve the folloing stops:

0: Austin
1: Boston
2: Dallas
3: Denver
4: El Paso
5: Houston
6: Indianapolis
7: Jacksonville
8: Los Angeles
9: New Orleans
10: New York City
11: Phoenix
12: San Francisco
13: Seattle
14: Washington D. C.

For such a trip, the program would draw the following:



Handin Instructions


Grading

All assignment will be graded purely based on program performance. Submissions that do not compile will receive 0 points. Submissions that never produce correct results will receive 0 points. The TAs will test your submissions using various input, and grades will be awarded depending on how often your code produces the correct results.



SUNYSB CSWeb page created and maintained
by Richard McKenna