In this lab you are going to create two different implementations of a set data structure, ArraySet and LinkedSet, and compare their performance.
In mathematics a set is a collection of distinct objects. That is, no two objects can have the same value. In order to ensure this condition it must be possible to compare the value of an object that is being added. In other words, the set should be limited to contain only objects that implement Comparable.
The file Set.java contains an interface that defines all of the method for the set classes. Look at the file and read through the methods to make sure that you understand all of them. Notice that the class is very similar to the ArrayList class. The major difference is that there are no operations on elements of the set at specific indices. This means that there is no get(index i) method. Access to elements of the set is instead performed using an iterator. Page 143 of your book explains how to use iterators and page 586 has an example of creating an Iterator.
The file ArraySet.java contains the skeleton on a class that implements the Set interface. Complete the class to implement a that stores elements in an array. You can use the example of ArrayBag on page 582 of in your book to help you. Think about how the ArraySet class is different from the ArrayBag class. For example, your ArraySet class uses generics like ArrayBag, but it limits the type to be of classes that implement Comparable. The array instance variable of the class should also be a Comparable object. Also the elements of the set should be contiguous in the array so that no memory is wasted. Therefore, when an element is removed from the ArraySet the element in the array that contains the element must be filled. The class should also be able to grow so that the array instance variable never runs out of space.
Remember to code in small pieces! Every time you write a method you should test it (do not forget to test boundary conditions). Creating a separate class with a main method to do this testing would be helpful. Proceed only when you are sure that your class is functioning properly.
A class that implements a linked collection does not contain an array to store its data. Instead it contains a pointer to the first element in the set. Each element in the set then in turn has a pointer to the element after it in the set.
Create a class LinkedSet that implements Set using links. To do this you will need to create a class LinkedSetNode that has two instance variables, an object of type Comparable for the data of the particular node, and a LinkedSetNode for the next element. When an object is added to the the LinkedSet it is added to the beginning of the set by creating a new LinkedSetNode. The node data is set to the object being added, and the next node is set to the first node of the of the LinkedSet. The first element of the LinkedSet is then set to the node that was just added. Again code in small pieces and test methods before proceeding.
Create a program that computes the steady state run-times of performing various operations on large a ArraySet and LinkedSet. Feel free to use your steady state code from lab 7 or from the sorting time code on the course web site. Have your program print out a table comparing the steady state run-times of the sets when adding a adding an element, and when removing an element.
Hand In: Tar your lab directory and e-mail it to your instructor with cpsc170 lab9 in the subject.