►Lab 3
1 Lab Objectives
2 The Sorted List Data Structure
3 What to Turn in

Lab 3

1 Lab Objectives

  1. Explore another data structure with an invariant

  2. Practice implementing lists or AVL trees in Java

  3. Think about how Java captures the relationship between data structures with invariants and their core shape implementations.

The core problems of this lab involve implementing the sorted list data structure. This exercises recent class concepts that you need to know, but may feel simple to those of you with extensive Java experience. If you have lots of Java experience, skim the list problems to make sure you see how to do them (especially #5). From there, you can either do either problem #6, or try to implement tree rotations and AVL trees as discussed in class.

2 The Sorted List Data Structure

Sorted lists are lists with the following invariant:

The first item in the list is smaller than all other elements in the list, and the rest of the list is a sorted list.

(assume no duplicate elements for now)

  1. Create an interface and implementation classes for sorted lists, using a separate class for the empty list as we did in lecture.

  2. Add implementations of addElt and size (our standard operations on sets) to your sorted list class.

  3. In practice, we often need to convert data from one data structure to another. For lists in particular, we may want to convert a general list (non-sorted) to a sorted one. Create an interface and classes for general lists. Then write a sort method on lists that produces a sorted list.

    Don’t forget to include tests in your Examples class.

  4. Where does your code capture the expectation that the result of sort be a sorted list?

  5. If we had wanted to allow duplicate elements in lists, where would your existing setup need to change? Consider the invariant, interfaces, method bodies, etc. You don’t need to make the changes. Just write a sentence or two indicating where that change would affect your work so far.

  6. If you get this far (not expected for most students), think about the relationships between the implementations for sorted lists and regular lists. Would it make sense to somehow share code between these data structures? For which implementations? How might you try to do this in Java? This is a slightly challenging design exercise. Save a copy of your work so far, then work on this problem on a fresh copy of your files.

3 What to Turn in

Submit all .java files that you produced for this assignment to the Lab1 area via Turnin.