Section12.21Step 5.3: Implementing Indexed Add and Remove
Continuing with Design Recipe Step 5: Implementation, we’ve established the core structure, resizing logic (growIfNeeded), and the ability to add elements to the end (addLast). Now, we tackle the more complex operations that work at arbitrary positions within the list: add(int index, T item) and remove(int index). Both require careful handling of the internal buffer array to maintain the "no gaps" contiguous storage rule, which necessitates shifting elements.
Subsection12.21.1Implementing the Shift-Right Logic (Helper Method)
First, let’s implement the helper logic we planned in Step 4 for shifting elements to the right, which is needed for add(int index, T item) when inserting before the current end (index < size).
Recall the Logic Plan: To avoid overwriting elements before they are moved, we must loop backwards, starting from the last element to be moved (size - 1) down to the insertion point (index), copying each element one position to its right (buffer[i + 1] = buffer[i]).
// Inside the ArrayList<T> class...
/**
* Shifts elements to the right to make space for insertion at a given index.
* Elements from buffer[index] through buffer[size-1] are moved
* to positions buffer[index+1] through buffer[size].
* Assumes capacity is already sufficient and index is valid for insertion.
* @param index The index at which an element will be inserted (0 <= index < size).
*/
private void shiftRight(int index) {
// Loop backwards from the last current element down to the insertion index
// Example: size=3, index=1. Need to move elements at 1, 2.
// i = 2: buffer[3] = buffer[2] (Move C)
// i = 1: buffer[2] = buffer[1] (Move B)
for (int i = this.size - 1; i >= index; i--) {
this.buffer[i + 1] = this.buffer[i];
}
// The slot at buffer[index] now contains a copy but is ready to be overwritten.
}
This private helper encapsulates the right-shifting logic.
// Inside the ArrayList<T> class...
@Override
public void add(int index, T item) {
// --- Implementation based on Step 4 Skeleton ---
// 1. Check for null item
if (item == null) {
throw new IllegalArgumentException("Item cannot be null.");
}
// 2. Check index bounds for insertion (0 <= index <= size)
if (index < 0 || index > this.size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size);
}
// 3. Ensure capacity for one more element
growIfNeeded(); // Use helper implemented previously
// 4. Make space by shifting elements right (helper handles index == size case)
shiftRight(index); // Use our shiftRight helper
// 5. Place the new item at the specified index
this.buffer[index] = item;
// 6. Increment the list size
this.size++;
}
This code directly follows our plan, handling validation, capacity, shifting (only when needed), insertion, and size update.
Based on our Step 4 direct logic skeleton, implementing addFirst requires checking the item, ensuring capacity, shifting *all* existing elements right (if any), placing the new item at index 0, and incrementing the size.
// Inside the ArrayList<T> class...
@Override
public void addFirst(T item) {
// --- Implementation based on Step 4 Skeleton ---
// 1. Check for null item
if (item == null) {
throw new IllegalArgumentException("Item cannot be null.");
}
// 2. Ensure capacity
growIfNeeded(); // Call helper
// 3. Shift *all* existing elements right
if (this.size > 0) { // Need to check if size > 0 before shifting index 0..size-1
shiftRight(0); // Call helper
}
// 4. Place item at buffer[0]
this.buffer[0] = item;
// 5. Increment size
this.size++;
}
This implementation follows the specific sequence needed for adding at the beginning: check, grow, shift, place, increment.
(Note: The addLast method was implemented directly in the previous section. While it could also delegate via add(size, item), having the direct implementation is also fine, especially as it avoids the unnecessary if (index < size) check present in the general add method.)
Subsection12.21.4Implementing the Shift-Left Logic (Helper Method)
Now let’s turn to removal. The core remove(int index) operation requires shifting elements to the left to fill the gap created by the removal, maintaining the "no gaps" rule.
Designing the Shift-Left Loop: We need to move elements starting from the one *after* the removed element (index + 1) up to the end of the list (size - 1), copying each one position to its left (buffer[i - 1] = buffer[i] or equivalently buffer[i] = buffer[i + 1] in a forward loop).
Approach: Unlike shifting right, we can loop forwards here without overwriting necessary data prematurely. We want to copy the element at index + 1 to position index, then copy index + 2 to index + 1, and so on.
Condition: Continue as long as i is less than the *last* valid index before the original end: i < size - 1. (Because when i is size - 2, we copy from size - 1 to size - 2, which is the last copy needed).
// Inside the ArrayList<T> class...
/**
* Shifts elements to the left to fill the gap after removal at a given index.
* Elements from buffer[index+1] through buffer[size-1] are moved
* to positions buffer[index] through buffer[size-2].
* @param index The index from which an element was just removed (0 <= index < size).
*/
private void shiftLeft(int index) {
// Loop from the removal index up to the second-to-last element
// Example: size=4, index=1 (removed B). Need to move C, D.
// i = 1: buffer[1] = buffer[2] (Move C left)
// i = 2: buffer[2] = buffer[3] (Move D left)
// Loop condition i < size - 1 (i < 3) stops it correctly.
for (int i = index; i < this.size - 1; i++) {
this.buffer[i] = this.buffer[i + 1];
}
// The slot at the old end (size - 1) now contains a duplicate
// but will be handled by the calling remove method.
}
// Inside the ArrayList<T> class...
@Override
public T remove(int index) {
// --- Implementation based on Step 4 Skeleton ---
// 1. Check index bounds (0 <= index < size)
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size);
}
// 2. Store buffer[index] to return later
T removedItem = this.buffer[index];
// 3. If removing element before the last one (index < size - 1), shift left
if (index < this.size - 1) {
shiftLeft(index); // Use our new helper
}
// If removing the last element (index == size - 1), no shifting is needed.
// 4. Decrement size *before* nulling out the slot
this.size--; // List is now logically shorter
// 5. Set the now-unused last slot to null (helps Garbage Collector)
this.buffer[this.size] = null;
// 6. Return the stored 'removedItem'
return removedItem;
}
This implementation validates the index, saves the item to return, calls the shiftLeft helper only when necessary (optimizing removal of the last element), updates the size, cleans up the unused array slot, and returns the removed item.
You’ve now implemented the core indexed operations add(index, item) and remove(index), along with their shifting helpers and potentially addFirst. This is significant progress! Run the full test suite in VSCode again.
✅ RemoveTests > testRemove_ByIndex_CausesShifting, testRemove_ByIndex_AtBoundaries: These should now pass, verifying your remove(index) and shiftLeft logic.
✅ AccessModifyTests: Tests like testGet_ValidIndex and testSet_ValidIndex should definitely pass now, as both the setup (addLast or maybe add(index)) and the tested methods (get, set) are implemented.
❌ Still Failing: Tests for removeFirst, removeLast, remove(T item), addAfter, first, last, contains, indexOf, and clear are still expected to fail as those methods haven’t been fully implemented yet (or rely on unimplemented methods like indexOf). Also, exception tests for NoSuchElementException will fail.
Focus on debugging any failures in the indexed add/remove logic or the tests that should now be passing based on these implementations. Ensure edge cases (index 0, index size-1, index size) are handled correctly.
The state of the code after completing this section (implementing indexed add/remove and shift helpers) can be found on the dr-step-5.3-indexed-impl branch in the repository.
Implementing the indexed add and remove methods, along with their associated shifting logic, forms the most complex part of the array list. With these in place and tested, implementing the remaining methods will often be simpler, frequently leveraging the logic we’ve already built.
