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.
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?
Submit AList.java
through Canvas.