Section12.17Step 4.2: Building Skeletons (Remove Methods)
Continuing with Design Recipe Step 4, having planned the logic for adding elements, we now focus on outlining the skeletons for the methods responsible for removing elements from our ArrayList<T>. We’ll again start with the core indexed removal method and analyze the requirements derived from the ListADT specification and our Step 0 understanding.
/**
* Removes and returns the element at the specified position.
* ... shifts subsequent elements to the left ...
* @param index position of element to remove (0 to size-1 inclusive)
* @return the removed element
* @throws IndexOutOfBoundsException if index is invalid
*/
public T remove(int index); // From ListADT
Prepare Return Value: The method must return the element being removed. Since we’re about to potentially shift elements over its position, we need to save it *before* shifting: // 2. Store the element currently at buffer[index] (to be returned later).
Problem: Gap Creation. Removing the element conceptually leaves a "gap" at index. According to our "no gaps" rule (from Step 0) required for array list correctness, we cannot leave this slot empty or null *within* the active part of the list.
Addressing the Problem: We must shift all elements that came *after* the removed element one position to the left to close the gap. This identifies the need for a core piece of logic: // 3. Shift elements buffer[index+1...size-1] left to positions buffer[index...size-2].
Initial State (size=4, capacity=5): buffer = [ A | B | C | D | ? ]
Indices: 0 1 2 3 4
Need to remove element at index 1 ("B").
1. Store element "B" (return value).
2. Shift elements from index 2..3 left:
- Move C (index 2) to index 1
- Move D (index 3) to index 2
Intermediate State: buffer = [ A | C | D | D | ? ]
0 1 2 3 4
3. Null out the old last element slot (index 3):
Final Array State: buffer = [ A | C | D |null| ? ]
0 1 2 3 4
4. Decrement size to 3.
Problem: Dangling Reference. After shifting, the last logical slot (buffer[size-1]) now holds a duplicate reference to the element that was originally there (since we shifted left over it). While the list is logically correct because we’ll decrement size, this lingering reference might prevent the garbage collector from reclaiming the object if it’s no longer referenced elsewhere.
Considering Good Practice (Memory Management): Java automatically manages memory. When an object is no longer reachable by any active part of the program, the Java Virtual Machine’s garbage collector can reclaim the memory it uses. However, even though our list’s size field tells us not to use the element at the old size-1 index anymore, the array slot buffer[size-1] *still holds a reference* to that object. If this is the *only* reference left, the object cannot be garbage collected. Setting this slot to null removes this last reference, allowing the garbage collector to potentially free up memory sooner. This is especially helpful if the list contains large objects. So, a good practice step is: // 4. Set buffer[size - 1] to null (to help garbage collection).
Subsubsection12.17.1.2Identifying the Need for Shift-Left Logic
Similar to the "Ensure Capacity" and "Shift Right" logic identified during the add planning, Step 3 ("Shift elements buffer[index+1...size-1] left...") represents a distinct, potentially reusable sub-task. This "Shift Left" operation is the counterpart to "Shift Right".
Again, we anticipate this might become a private helper method during implementation (Step 5) for clarity and potential reuse. Let’s plan its conceptual logic:
// --- Private Helper Logic Plan: shiftLeft(int index) ---
// (This logic is needed to close the gap after removing at 'index')
// We need to copy elements from index+1, index+2, ..., size-1
// over to positions index, index+1, ..., size-2 respectively.
// Loop Analysis:
// - Initialization: Start loop counter `i` at `index`. This is the first destination slot.
// - Condition: Continue as long as `i` is less than `size - 1`. Why? The last element we
// need to *copy from* is at `size - 1`. This element needs to be copied into
// position `size - 2`. So, the last destination index `i` we need to write to is `size - 2`.
// Therefore, the loop should run while `i <= size - 2`, or equivalently `i < size - 1`.
// - Update: Increment `i` (`i++`) to move to the next destination slot.
// 1. Iterate from `i = index` up to `size - 2` (inclusive).
// 2. In each iteration, copy the element from the position to the right (`i + 1`)
// into the current position (`i`).
// `buffer[i] = buffer[i + 1];`
We can now use this conceptual block in our main skeleton.
@Override
public T remove(int index) {
// --- Skeleton Plan ---
// 1. Check index bounds (0 <= index < size); throw IndexOutOfBoundsException if invalid.
// 2. Store buffer[index] in a temporary variable (e.g., 'removedItem').
// 3. If removing element before the last one (index < size - 1), perform "Shift Left" helper logic, starting at 'index'.
// 4. Decrement 'size'.
// 5. Set buffer[size] (the now-unused last slot) to null.
// 6. Return 'removedItem'.
}
Note12.17.1.Refined Logic Order.
Notice a slight reordering in the final skeleton compared to the initial analysis. We decrement size *before* nulling out the slot at the *new* size. This is often simpler to implement correctly.
Subsubsection12.17.1.4Skeletons for removeFirst() and removeLast()
These methods remove from the ends and have a specific requirement to handle empty lists by throwing NoSuchElementException (as per the Javadoc). Let’s outline their direct logic first.
@Override
public T removeFirst() {
// 1. Check if list is empty (size == 0).
// 2. If empty, throw NoSuchElementException.
// 3. If not empty, perform the logic for remove(0):
// - Store buffer[0].
// - Shift elements 1..size-1 left to 0..size-2 (using shiftLeft(0) logic).
// - Decrement size.
// - Null out buffer[size] (the new last slot).
// - Return the stored element.
}
@Override
public T removeLast() {
// 1. Check if list is empty (size == 0).
// 2. If empty, throw NoSuchElementException.
// 3. If not empty:
// - Store buffer[size - 1].
// - Decrement size.
// - Set buffer[size] (the now-unused slot) to null.
// (No shifting required!)
// - Return the stored element.
}
Direct Logic as the Plan: The direct logic skeletons above, including the specific empty-list check (throwing NoSuchElementException) and the appropriate helper calls or direct actions (like skipping the shift for removeLast), form our primary plan for implementation in Step 5.
For removeFirst(): After handling the distinct empty-list exception (NoSuchElementException required here vs. IndexOutOfBoundsException from remove(0) if size is 0), the remaining direct steps (store element 0, shift left from 0, decrement, null out, return) *exactly match* the core logic of remove(0).
For removeLast(): After the empty check, the remaining direct steps (store element size-1, decrement size, null out new slot size, return stored element) are effectively the same as the logic within remove(index) when index == size - 1 (where the shifting step is skipped).
Potential Refinement: The comparison reveals that, *after* implementing and testing the direct logic, delegation to remove(index) is a feasible future refinement (likely desirable for DRY), provided the distinct empty-list exception (NoSuchElementException) is handled correctly in removeFirst/removeLast *before* delegating. For Step 5, we will implement the direct logic first.
@Override
public boolean remove(T item) {
// --- Skeleton Steps ---
// 1. Find the index of the first occurrence of 'item'.
// - Plan: Perform logic equivalent to `indexOf(item)`:
// - Iterate from 0 to size-1.
// - Compare buffer[i] with 'item' using .equals() (null-safe).
// - Store the first matching index, or -1 if none.
// - Let 'foundIndex' be the result.
// 2. Check if the item was found.
// - If foundIndex >= 0:
// - Plan: Perform the direct logic for removing the element at 'foundIndex':
// - Check bounds for 'foundIndex' (0 <= foundIndex < size) - Implicitly true if found.
// - Store buffer[foundIndex] (optional if method returns void/boolean).
// - If (foundIndex < size - 1), shift left (call logical block `shiftLeft(foundIndex)`).
// - Decrement 'size'.
// - Set buffer[size] to null (Help GC).
// - Return true.
// - Else (foundIndex == -1):
// - Return false.
}
@Override
public void clear() {
// --- Skeleton Steps ---
// 1. Optional (for GC): Iterate from 0 to size-1 and set buffer[i] to null.
// (Helps garbage collector reclaim objects sooner, especially if list held large objects).
// 2. Reset the size.
// - Set size = 0;
// (Note: We might also consider resizing the internal array back to default capacity,
// but the basic contract only requires making the list logically empty).
}
The state of the code after adding the skeletons for the Remove methods (as planned in this section) can be found on the dr-step-4.2-remove-skeletons branch in the repository.
We have now outlined the logical steps for the "Remove" methods, again identifying necessary checks, the core logic (like shifting left), and considering potential reuse or delegation. The next step is to create skeletons for the remaining "Other" operations (accessing, querying).
