Computer Science 230 Assignment 3 – Revised

Objectives:
to create a "linked list" data structure
Assignment – Part 1: In Greek mythology the Hydra is a nine-headed monster. When one of its heads is chopped off two more grow in its place. We will create a new data structure called the Hydra List. It is a "many-headed list" that sometimes has heads cut off, and sometimes grows many new heads. Write a Java Class, HydraList. In the class there is a reference to the Letter list, a singly-linked, sorted, non-circular list (whether it has a dummy node is up to you). The only data in the node is the initial letter of the key field. There are a next link and a data link. The data link is a reference to another list, the Data list, a singly-linked, sorted, non-circular list. The node of the Letter list counts as the dummy node of the Data list. (Be careful! The Letter list node is a different class from the Data node.) The Hydra List supports the four standard operations, insert, fetch, delete and update. There is also a method, print(), that prints all of the contents of the Hydra List in ascending key order. The Hydra List does not have to be generic. When a new item is inserted into the Hydra List, the Letter list is scanned for the first letter of the new key. If the letter is not in the list it is added, and the new item is inserted into the new Data list. If the letter is already in the Letter list the item is simply inserted into the Data list. When an item in the data list is fetched, return the complete item, or null if the item is not found. For simplicity we will limit the updates that can be done (see below). When an item is deleted, the Data list must remain sorted. But if the Data list becomes empty, then the corresponding Letter list node is also deleted, and the Letter list must remain sorted. Assignment – Part 2 – Application: Bubba's Auto Parts wants you to write a program to keep track of their inventory. Providentially you have just created the HydraList, and decide to keep the parts inventory in it. Write a class, AutoPart, that has the fields, partNumber, makeAndModel, description, price, and numberInStock. The partNumber is the key field. It is slightly misnamed, because it is really a String, as are makeAndModel and description. price is a float, and numberInStock is an int. Write a constructor that initializes all fields from the parameters. Write setters for price and numberInStock. Write getters if you need them. Write a toString(). Write a class, PartsStore, that stores AutoPart objects in a HydraList. (Don't write a separate driver; PartsStore is the driver.) For simplicity we will allow updates to the price and numberInStock fields only. Be sure that PartsStore exercises HydraList thoroughly. I reserve the right to replace your PartsStore class with my own test class. Assignment – Part 3 – Assessment: Write a report giving the Big-O of each of the operations, insert, fetch, delete, and update, for the HydraList. Explain briefly how you arrived at the Big-O that you are asserting. Call the file Report.<x, where <x is one of the formats, .txt, .rtf, .doc, .docx, or .pdf. Submission: Every file that you submit must begin with a comment giving the author's name. If you modify someone else's file, include comments giving both the original author's name and your name, and the modifications that you did. Submit the files, HydraList.java, AutoPart.java, and PartsStore.java, on WebCT by the date and time specified above. No submissions will be accepted other than by WebCT. Submit only .java files, not .class files. Do not use a Java package. Do not put the files into a folder or, zip the files or use any other archive. Submit the files, Report.<x on WebCT by the date and time specified above. No submissions will be accepted other than by WebCT.