Note 12.23.1. Test After Refining!
Always re-run your full test suite after applying any refinement. The goal is to improve the code *without breaking its correctness*. Tests are your safety net!
Section 12.23 Step 5.5: Refining the Implementation
Congratulations! If you’ve reached this point and all the provided unit tests for your
ArrayList<T> are passing (✅), you have successfully completed the core implementation task. This is a significant achievement.
However, the Design Recipe includes one final, important part in Step 5: Refinement. Now that our code is correct (according to the tests), we can review it with a critical eye and look for ways to improve its quality. Refinement isn’t about changing what the code *does*, but *how* it does it, focusing on aspects like efficiency, readability, maintainability (DRY), robustness, and leveraging existing tools effectively.
Let’s explore several potential refinements for our
ArrayList implementation.
Subsection 12.23.1 Refinement 1: Improving Efficiency with System.arraycopy()
The Opportunity (Efficiency/Knowledge): Our helper methods
growIfNeeded, shiftRight, and shiftLeft currently use for loops to copy array elements. While logically correct, copying potentially large blocks of memory element-by-element in a Java loop can be much slower than using optimized, low-level system routines.
Teaching the Tool:
System.arraycopy() Java provides a static method specifically for fast bulk copying of array elements: System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length). It’s designed to be highly efficient. Let’s break down its parameters:
-
Object src: The source array you are copying from. -
int srcPos: The starting index in the source array from where copying begins. -
Object dest: The destination array you are copying to. -
int destPos: The starting index in the destination array where copied elements will be placed. -
int length: The number of elements to copy.
Crucially,
System.arraycopy correctly handles copying elements within the *same* array (as needed for shifting), even if the source and destination ranges overlap.
Subsubsection 12.23.1.1 Applying to growIfNeeded
Before (Loop):
// Inside growIfNeeded, if resizing needed...
Object[] newbuffer = new Object[newCapacity];
for (int i = 0; i < this.size; i++) { // Copying 'size' elements
newbuffer[i] = this.buffer[i];
}
this.buffer = (T[]) newbuffer;
After (
System.arraycopy):
// Inside growIfNeeded, if resizing needed...
Object[] newbuffer = new Object[newCapacity];
// Copy 'size' elements from 'this.buffer' starting at index 0
// to 'newbuffer' starting at index 0.
System.arraycopy(this.buffer, 0, newbuffer, 0, this.size); // Replaces the loop
this.buffer = (T[]) newbuffer;
Benefit: More concise and significantly faster for large lists.
Subsubsection 12.23.1.2 Applying to shiftRight
Before (Loop):
private void shiftRight(int index) {
for (int i = this.size - 1; i >= index; i--) {
this.buffer[i + 1] = this.buffer[i];
}
}
After (
System.arraycopy):
private void shiftRight(int index) {
// Need to move elements from index..size-1 to index+1..size
int numToMove = this.size - index; // Number of elements from index onwards
if (numToMove > 0) {
// Copy 'numToMove' elements:
// from: 'buffer' starting at 'index'
// to: 'buffer' starting at 'index + 1'
System.arraycopy(this.buffer, index, this.buffer, index + 1, numToMove);
}
}
Benefit: Replaces the backward loop with a single, efficient copy operation.
Subsubsection 12.23.1.3 Applying to shiftLeft
Before (Loop):
private void shiftLeft(int index) {
for (int i = index; i < this.size - 1; i++) {
this.buffer[i] = this.buffer[i + 1];
}
}
After (
System.arraycopy):
private void shiftLeft(int index) {
// Need to move elements from index+1..size-1 to index..size-2
int numToMove = this.size - 1 - index; // Num elements after the removed one
if (numToMove > 0) {
// Copy 'numToMove' elements:
// from: 'buffer' starting at 'index + 1' (element after removed one)
// to: 'buffer' starting at 'index' (the gap)
System.arraycopy(this.buffer, index + 1, this.buffer, index, numToMove);
}
}
Benefit: Replaces the forward loop with a single, efficient copy operation.
Subsection 12.23.2 Refinement 2: Simplifying clear with Arrays.fill()
The Opportunity (Knowledge/Conciseness): Our `clear` method uses a loop to null out references to help the garbage collector. This is good, but slightly verbose.
Teaching the Tool:
Arrays.fill() The java.util.Arrays class provides many static utility methods for working with arrays. One is Arrays.fill(Object[] a, int fromIndexInclusive, int toIndexExclusive, Object val). It efficiently assigns the specified value (val) to each element of the array within the specified range. Note that the toIndex is exclusive (the element at `toIndex` itself is *not* included).
Before (Loop):
@Override
public void clear() {
for (int i = 0; i < this.size; i++) { // Null out indices 0 to size-1
this.buffer[i] = null;
}
this.size = 0;
}
After (
Arrays.fill):
@Override
public void clear() {
// Fill the range currently holding elements (0 up to size) with null.
// The 'toIndex' parameter is exclusive, so 'this.size' is correct here.
java.util.Arrays.fill(this.buffer, 0, this.size, null);
// Reset size *after* nulling out the old range
this.size = 0;
}
Benefit: This version is slightly more concise and clearly expresses the intent of nulling out a range. Both versions are functionally acceptable.
Subsection 12.23.3 Refinement 3: Enhancing Consistency with Delegation
The Opportunity (DRY/Consistency): In Step 5, we implemented methods like
addFirst, removeFirst, and removeLast using their direct logic sequences (calling private helpers). This provided good practice but resulted in some repetition of checking logic and helper call patterns already present in add(index) and remove(index).
Refinement (Delegation): Now that our core indexed methods are implemented and assumed tested, we can refactor the convenience methods to delegate to them. This centralizes the core logic, improving maintainability and adherence to DRY.
Example:
removeFirst Before (Direct Logic with Helpers):
@Override
public T removeFirst() {
if (isEmpty()) { throw new NoSuchElementException("List is empty."); }
T removedItem = this.buffer[0];
if (0 < this.size - 1) { shiftLeft(0); } // Check if shifting needed
this.size--;
this.buffer[this.size] = null;
return removedItem;
}
Example:
removeFirst After (Delegation):
@Override
public T removeFirst() {
if (isEmpty()) { // Still need specific empty check for NoSuchElementException
throw new NoSuchElementException("List is empty.");
}
// Delegate core logic (index check, get item, shift, size--, null out)
return remove(0); // remove(0) handles the rest
}
Similarly,
removeLast can be refined to check for empty and then call remove(size - 1), and addFirst can be refined to just call add(0, item).
Note 12.23.2. Trade-offs of Delegation.
Delegation generally leads to cleaner, more maintainable code (fix a bug in `remove(index)`, and `removeFirst`/`Last` automatically benefit). The main prerequisites are that the core method (`add(index)` or `remove(index)`) must be correct and thoroughly tested, and you must ensure the specific preconditions of the convenience method (like the empty check for `removeFirst` throwing `NoSuchElementException` instead of `IndexOutOfBoundsException`) are handled before delegating if they differ from the core method’s contract.
Subsection 12.23.4 Refinement 4: Improving Null Checks with Objects.equals()
The Opportunity (Knowledge/Robustness/Clarity): Our `indexOf` method correctly handles nulls, but the logic is slightly verbose.
Before (Manual Null Check in `indexOf` loop):
// Inside the loop...
T currentElement = this.buffer[i];
if (item == null) {
if (currentElement == null) { return i; }
} else {
if (item.equals(currentElement)) { return i; }
}
Teaching the Tool:
Objects.equals() The utility class java.util.Objects (available since Java 7) provides a static method Objects.equals(Object a, Object b) designed specifically for null-safe equality checks. It returns true if both arguments are null, false if exactly one is null, and calls a.equals(b) if both are non-null.
After (
Objects.equals):
// Inside the loop...
if (java.util.Objects.equals(item, this.buffer[i])) {
return i;
}
Benefit: Using
Objects.equals is the standard, idiomatic way to check for equality when either operand might be null in modern Java. It’s more concise and less prone to logic errors than manual null checks. This is a knowledge-based refinement that improves code clarity and robustness.
Subsection 12.23.5 Refinement Summary
This refinement step demonstrated several ways to improve our initial, correct implementation by leveraging standard library features and design principles:
-
Using
System.arraycopysignificantly improves the efficiency of internal data copying. -
Using
Arrays.filloffers a concise alternative for nulling out elements inclear. -
Using delegation for convenience methods enhances DRY and maintainability after core methods are stable.
-
Using
Objects.equalsmakes null-safe comparisons cleaner and more robust.
Applying such refinements after establishing correctness through testing leads to higher-quality, professional code. Remember to re-run your tests after any refinement!
Note 12.23.3. Code Snapshot.
The final, refined version of the code incorporating the improvements discussed in this section can be found on the
dr-step-5.5-final-refined branch.
With implementation and refinement complete, we have successfully built and improved our own generic
ArrayList<T>, gaining valuable insight into data structures, generics, and the Design Recipe. The final section will conclude the chapter.
You have attempted of activities on this page.
