Dynamic Arrays Lab

Introduction

Dynamic arrays allow for expansion when their capacity limit is reached. In this lab, you will modify the openDSA list to provides these capabilities.

Files

Download the following files:

• List.java
• AList.java
• AListTest.java

Part 1 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.

Part 2 Shrinking Arrays Too (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?

Lab Submission

Submit AList.java to Gradescope: