One solution to the problem of running out of space for an array-based list implementation is to replace the array with a larger array whenever the original array overflows. A good rule that leads to an implementation that is both space and time efficient is to double the current size of the array when there is an overflow. Reimplement the array-based List class of Figure 4.2 to support this array-doubling rule.

Transcribed Image Text:

/** Array-based list implementation */ class AList implements List { private static final int defaultSize = 10; // Default size // Maximum size of list private int maxSize; private int listSize; private int curr; private E[] listArray; // Number of list items now // Position current element // Array holding list elements /** Constructors */ /** Create a list with the default capacity. */ AList() { this (defaultSize); } /** Create a new list object. @param size Max number of elements list can contain. */ @SuppressWarnings ("unchecked") // Generic array allocation AList (int size) { } public void clear() // Reinitialize the list { listSize = curr = 0; } // Simply reinitialize values maxSize = size; list Size = curr = 0; listArray (E[]) new Object [size]; // Create listArray /** Insert "it" at current position */ public void insert (E it) { assert listSize < maxSize : "List capacity exceeded"; for (int i=listSize; i>curr; i--) // Shift elements up listArray[i] = listArray [i-1]; // to make room listArray [curr] = it; list Size++; // Increment list size } public void append (E it) { // Append "it" assert listSize < maxSize : "List capacity exceeded"; listArray [listSize++] = it; } public void move ToStart() { curr = 0; } // Reset position