1 Problems
2 What to Turn In
3 Grading

Assignment 3: Parameterized Data Structures

Due: Tuesday, Nov 16 at 11:59pm via Turnin

With the exam coming early this week as well, this is a gentle assignment just to make sure you’re keeping pace with the material.

1 Problems

In lecture, we saw how to use either Object or generics to abstract over classes that were similar except for their types. This same idea applies to whole data structures as well: although we have talked about lists, sets, trees, heaps, etc as containing numbers, in reality we often want to use these over arbitrary data. This assignment makes sure that you can implement multi-class data structures with parameterized datatypes as well.

  1. Use Object to create a general-purpose class hierarchy for lists. Start from the 2-class/1-interface list shape covered in class. Call these OLists (O for Object – different names for problems 1 and 2 will make testing a lot easier).

  2. Create a generic class hierarchy for lists, in which the type of the contents are provided through a type parameter. Call these GLists (G for Generic).

  3. For each of OList and GList, require that all instances implement a hasElt method that consumes an element and checks whether that element is in the list. Hint: interfaces can be type-parameters in generics.

  4. Create a list of MenuItems (from class notes on data abstraction) using each of OList and GList. You’ll have to provide the hasElt method under each version. Provide an Examples class with tests of your hasElt implementation on both kinds of MenuItem lists.

  5. Written question: Assume you wanted to create a list containing a mix of numbers and strings. Would you rather use OList or GList? Explain your reasoning in a sentence or two. You do not need to write any code.

  6. Written question: Assume you wanted to create a list containing a mix of boas and dillos (as defined in our early lectures). Would you rather use OList or GList? Explain your reasoning in a sentence or two. You do not need to write any code.

2 What to Turn In

Submit .java files containing the final versions of all classes, interfaces, and examples developed for this assignment. Do not submit the .class files. You may submit either a separate file for each class/interface (standard for Java) or a single file containing all classes and interfaces. Submit a single questions.txt file with your answers to the two written questions.

3 Grading

Grading will follow the standard rubric for all assignments.