Starter Code

• List.java - OpenDSA list interface.
• AList.java - OpenDSA array-based list implementation.
• AListTest.java - Unit tests.

Dynamic Arrays (95%)

Dynamic arrays use the following algorithm to ensure sufficient capacity when new elements are added:

if the current array is full:
    * Allocate a new array that is twice as large as the current array.
    * Copy all entries from the current array to the new array.
    * Replace the current array with the newly allocated array.

Your goal for this lab is to update the OpenDSA AList class so that it performs these steps every time append or insert is called. Since the same steps are required for both methods, it would be appropriate to create a private helper method.

Dynamically Shrinking Arrays (5%)

The resizing operation above provides an efficient mechanism for ensuring that the AList always has adequate capacity. However without a corresponding mechanism for shrinking the array the AList might end up tying up a huge amount of unneeded memory. Imagine adding 1,000,000 items, then immediately removing them.

One solution for this problem is to monitor the percentage of the array that is currently being used, and to resize the array if the value falls below some threshold.

Modify the remove method so that it shrinks the array by a factor of 2 whenever the number of used entries falls below 25%.

BONUS QUESTION #1: Why 25% and not 50%?

BONUS QUESTION #2: The designers of the Java ArrayList class chose not to implement this shrinking operation. What do you think motivated their decision?

Submitting

Submit AList.java through Autolab.