Lab 3: Array vs. linked implementations Solution

In this lab, you explore the implementa on of the ADT bag using arrays and linked chains. You will override the equals method so that it will determine if two bags are equal based on their contents.

The primary goal of this lab is to prac ce solving the problems that arise when developing implementa ons of data structures (alternately array- and linked-based). A secondary goal is to exercise good code reuse prac ces, as exis ng Bag methods may be useful in implemen ng the one you will be wri ng in the lab.

As we have seen in lecture, a bag is an unordered collec on of items that may contain duplicates. Before comple ng this exercise you should review the methods available to you in the Bag ADT, as well as the implementa on techniques we used to construct the array-and linked-based implementa ons of this ADT.

Your TA will give a lesson reviewing the two main implementa ons of Bag, and discussing the method that you will write in this exercise.


Exercise




A  er the TA’s lesson, complete the following steps:

    1. Download the provided code from the course website. The following Java files are provided in package cs445.lab3 .
BagInterface.java is a Java interface represen ng the ADT Bag ArrayBag.java is a dynamic capacity array-based implementa on of ADT Bag. It has a nonfunc onal stub for the equals method that you must write in this lab.

LinkedBag.java is a linked implementa on of ADT Bag. It also has a non-func onal stub for the equals method.

EqualsTest.java is an example test client of the Bag equals method.


    2. Devise an algorithm for comparing two bags to determine if they contain the same contents. Here are some steps you may want to follow:
 Consider two “equal” bags. What items and frequencies need to be compared to determine that they are equal? What exis ng bag methods can you reuse to accomplish this?

 Determine an example of two bags that cannot be equal, yet no item comparisons are needed to make that determina on.

  Write an algorithm for each of ArrayBag and LinkedBag that returns true if

two bags contain the same entries. Remember to consider the example from the previous step.
    3. Implement your algorithm(s) as method boolean equals(Object other) in each class. Since this is overriding a method from the generic Object class, you cannot change the method signature, which means you cannot accept a parameter of type ArrayBag . This means you must first check if other instanceof ArrayBag . If not, return false . If so, cast the reference to type ArrayBag to complete the rest of the algorithm.

    4. Test your equals method by running EqualsTest . To change which class is tested, change the object type of the instances created for tes ng (i.e., from ArrayBag to

LinkedBag ).



Conclusion




In this lab, you wrote implementa on code for the array- and linked-based implementa ons of the ADT Bag. Throughout the term, you should take the me to prac ce implemen ng useful methods for the data structures that we present. You may either choose to implement addi onal methods, as in this lab, or simply re-implement exis ng methods without looking at the given code. The techniques demonstrated are best learned through repeated prac ce