Lab 4 - Array Based List Structure

In this lab you will add additional functionality to the ExpandableArray which we wrote in class. You will add functionality to allow removal of elements, and will explore the difference between operating on implementation details of the data structure and using the API it provides.

As in previous labs, set up a project folder for this lab, being sure to use Gradle. Copy the ExpandableArray code from class into an appropriately named java file in the proper location. Be sure you can compile and run the code.

Part 1: Removal Methods

Implement the following methods in the ExpandableArray.

removeAt

This public method takes an integer index as an argument and returns a boolean. It will remove the element at the specified index, returning true if this is successful or false if the index is outside of the range of the list. Remember that our list should not contain holes, so you will need to update the locations of other elements.

remove

This public method takes an integer and removes the first occurrence of that integer from the list. It does not return anything. Be sure you are not duplicating functionality – use existing methods where possible!

In the main method of the class, test your code by performing the following operations:

Add 1 to the list.
Add 2 to the list.
Insert 3 at position 0.
Insert 2 at position 1.
Remove 2.
Remove 2.

Along the way, print out the contents of the list to inspect them. Add additional tests to ensure your methods are working as intended. Explain to the lab TA the rationale for your tests.

Part 2: External vs. Internal Manipulation

You will implement methods for reversing an ExpandableArray from two perspectives, internally and externally.

Internal

Implement a method called reverse inside your ExpandableArray. It will take no arguments and return no result. It should reverse the order of the items in the ExpandableArray. Create some tests to show that your reverse works.

External

Begin by adding the following methods to your ExpandableArray.

    public int size() {
        return count;
    }

    public int get(int idx) throws IndexOutOfBoundsException {
        if (idx > count || idx < 0) throw new IndexOutOfBoundsException();
        return arr[idx];
    }

    public boolean set(int i, int idx) {
        if (idx > count || idx < 0) return false;
        arr[idx] = i;
        return true;
    }

public int size() {

return count;

}

public int get(int idx) throws IndexOutOfBoundsException {

if (idx > count || idx < 0) throw new IndexOutOfBoundsException();

return arr[idx];

}

public boolean set(int i, int idx) {

if (idx > count || idx < 0) return false;

arr[idx] = i;

return true;

}

Create a new public class called EAUser and move the main method from ExpandableArray to the new class. Now, pretend that reverse() does not exist inside ExpandableArray, but you still want to be able to reverse the elements in the data structure. Your only choice is to use the publicly available methods in ExpandableArray.

Write a method in EAUser called externalReverse which takes an ExpandableArray as an argument. This method will perform the reverse operation externally, using methods callable on the passed ExpandableArray. Add tests to the main method to ensure this works. Be sure to test both odd and even length lists. Hint: Think about how to swap two elements at different ends of the ExpandableArray!

When you have completed the lab, show it to your lab instructor.

Hi There!

Lab 4 – Array Based List Structure