Section12.20Step 5.2: Implementing Resizing and addLast
We continue with Design Recipe Step 5: Implementation. Having implemented the constructor and core accessors (size, isEmpty, get, set) and verified them with tests, we now tackle a fundamental aspect of our ArrayList<T>: making it dynamic. This requires handling the case where the internal buffer array is full when we try to add a new element. We’ll implement the resizing logic using basic array manipulation and loops, and then implement the relatively simple addLast method.
Subsection12.20.1Implementing the Resizing Logic (Helper Method with Loop)
In Step 4 (Skeletons), our analysis of add operations revealed the need for logic to Ensure Capacity. Before adding an element, we must check if the internal array is full (size == buffer.length). If it is, we need to replace the internal array with a larger one and copy the existing elements over.
Identifying the Need for a Helper: As planned, we’ll encapsulate this resizing logic in a private helper method called growIfNeeded to keep our main add methods cleaner.
Copy Elements: We now need to copy all the current elements (from index 0 to size - 1) from the old buffer array into the newbuffer array, preserving their order.
Designing the Copy Loop: How do we copy size elements from buffer to newbuffer? This is a classic task for a for loop (See Chapter 4). Let’s think about the loop structure:
// Inside the ArrayList<T> class...
/**
* Ensures that the internal array has space to add at least one more element.
* If the array is full, it creates a new, larger array (typically double
* the size) and copies the existing elements into it using a loop.
*/
@SuppressWarnings("unchecked") // For the cast when assigning back to buffer
private void growIfNeeded() {
// Check if the array is full
if (this.size == this.buffer.length) {
// Determine the new capacity
int oldCapacity = this.buffer.length;
int newCapacity = (oldCapacity == 0) ? DEFAULT_CAPACITY : oldCapacity * 2;
// Create the new, larger array (as Object[] due to erasure)
Object[] newbuffer = new Object[newCapacity];
// --- Copy elements using a standard for loop ---
// We need to copy 'size' elements, from index 0 to size-1
for (int i = 0; i < this.size; i++) {
newbuffer[i] = this.buffer[i]; // Copy element at index i
}
// --- End of copy loop ---
// Update the buffer reference to point to the new array
// This requires the cast, hence the @SuppressWarnings on the method
this.buffer = (T[]) newbuffer;
// Optional: Log or print a message when resizing happens (for debugging)
// System.out.println("DEBUG: Resized array from " + oldCapacity + " to " + newCapacity);
}
// If not full, do nothing.
}
Note12.20.1.Loop vs. Library Methods.
Implementing the copy with a for loop helps solidify your understanding of array iteration. In professional code, developers often use built-in methods like System.arraycopy or Arrays.copyOf for this task, as they are typically highly optimized and concise. We may revisit this in a later refinement step as a "knowledge-based" improvement – knowing the right tool exists in the library. For now, our loop is perfectly functional.
With our resizing logic in place via growIfNeeded(), implementing addLast according to its Step 4 skeleton is now quite direct. It must check for null, ensure capacity, place the item at index size, and increment the size.
// Inside the ArrayList<T> class...
@Override
public void addLast(T item) {
// --- Implementation based on Step 4 Direct Logic Skeleton ---
// 1. Check for null item (as per Javadoc contract)
if (item == null) {
throw new IllegalArgumentException("Item cannot be null.");
}
// 2. Ensure internal array has capacity for one more element
growIfNeeded(); // Call our private helper method
// 3. Place item at buffer[size] (the first unused slot)
this.buffer[this.size] = item;
// 4. Increment size
this.size++;
}
This directly follows our plan: check input, ensure capacity, place element, update size.
Many other tests will still fail because they rely on methods like add(index), remove(index), get (on non-empty lists), etc., which use logic (like shifting) that we haven’t implemented yet. Focus on ensuring the tests related to addLast and basic growth are now passing before moving on. Debug any failures in addLast or growIfNeeded based on the test output.
We’ve successfully implemented dynamic resizing (using a loop for now) and the ability to add to the end of the list. The next critical step is implementing insertion and deletion at arbitrary indices, which requires coding the element shifting logic we planned in Step 4.
