Section12.16Step 4.1: Building Skeletons (Add Methods)
Following the Design Recipe, after understanding the specification (Step 0), defining data (Step 1), setting the class structure (Step 2), and creating examples (Step 3), we now plan the implementation logic in Step 4: Skeleton / Method Template. We outline the logical steps for each method using comments, focusing on *what* needs to happen based on our understanding and examples, before writing detailed Java code in Step 5. This structured planning helps prevent errors and clarifies the required logic.
Subsubsection12.16.1.1Analyzing and Planning add(int index, T item)
This is the primary insertion method. Let’s revisit its contract from the ListADT.java Javadoc to guide our plan. (Remember, you can view this in VSCode by opening the file or hovering over the method name in ArrayList.java once you add the @Override.)
/**
* Inserts an element at the specified position. ...
* @param index position to insert (0 to size inclusive)
* @param item element to insert (cannot be null)
* @throws IndexOutOfBoundsException if index is invalid
* @throws IllegalArgumentException if item is null
*/
public void add(int index, T item); // From ListADT
This tells us we must first perform crucial checks before attempting the insertion:
Input Check 1 (Null Item): The Javadoc mandates throwing IllegalArgumentException if item is null. So, our first logical step is: // 1. If item is null, throw IllegalArgumentException.
Input Check 2 (Index Bounds): The Javadoc specifies the valid range for index is 0 up to and including size. An index outside this range is invalid. So, the next step is: // 2. If index < 0 or index > size, throw IndexOutOfBoundsException.
Now, assuming the inputs are valid, we think about the core task: inserting item into our internal buffer array. Two immediate challenges arise from using an array:
Problem: Capacity. What if the array is already full? That is, what if size already equals buffer.length? There’s no physical space to add another element, even if the index is valid (e.g., adding at the end when full).
Addressing the Problem: We realize we need a step to handle this *before* trying to insert. This leads to the third logical step: // 3. Ensure internal array has capacity for one more element. We haven’t designed *how* to ensure capacity yet, but we recognize the *need* for this logical step.
Problem: Overwriting and Order. If we are inserting at an index that’s less than the current size, that array slot (buffer[index]) already holds a valid element. We cannot just overwrite it, as that would lose data. Furthermore, the contract implies subsequent elements should shift to maintain order.
Addressing the Problem: To make space *without* losing data and *while* maintaining order and the "no gaps" rule (from Step 0), we must shift the existing elements currently occupying indices index through size - 1 one position to the right. This leads to the fourth step: // 4. If (index < size), shift elements currently in index..size-1 to index+1..size. Again, we plan the *what* (shifting needed), not the precise *how* (the loop/copy algorithm) in this skeleton step.
Initial State (size=3, capacity=5): buffer = [ A | B | C | ? | ? ]
Indices: 0 1 2 3 4
Need to insert "X" at index 1.
1. Shift elements from index 1..2 right:
- Move C (index 2) to index 3
- Move B (index 1) to index 2
Intermediate State: buffer = [ A | B | B | C | ? ]
0 1 2 3 4
2. Place "X" at index 1:
Final Array State: buffer = [ A | X | B | C | ? ]
0 1 2 3 4
3. Increment size to 4.
This detailed analysis, driven by the contract and the implications of using an array, leads us to the following skeleton plan for add(int index, T item):
@Override
public void add(int index, T item) {
// --- Skeleton Plan ---
// 1. Check for null item; throw IllegalArgumentException if invalid.
// 2. Check index bounds (0 <= index <= size); throw IndexOutOfBoundsException if invalid.
// 3. Ensure internal array has capacity for one more element (handle resizing if size == buffer.length).
// 4. Shift elements buffer[index...size-1] right to positions buffer[index+1...size] (Helper handles index == size case).
// 5. Place 'item' at buffer[index].
// 6. Increment 'size'.
}
Subsubsection12.16.1.2Identifying the Need for Helper Methods
Looking at the skeleton for add(index, item), steps 3 ("Ensure internal array has capacity...") and 4 ("...shift elements...") represent significant, potentially complex sub-tasks that might also be needed by other methods (like ensuring capacity before any add variant).
This suggests that during actual implementation (Step 5), encapsulating this logic into dedicated private helper methods would be good design. Why private? Because managing array capacity and the exact shifting mechanism are internal implementation details. They are not part of the public ListADT contract. Making them private prevents external code from interfering with the list’s internal state management.
For now, in Step 4, we simply note these logical sub-tasks within the main skeleton. We don’t need to design the helper method skeletons fully yet, just recognize the logical blocks:
@Override
public void addFirst(T item) {
// 1. Check for null item (throw IllegalArgumentException).
// 2. Ensure capacity (logical block `ensureCapacityForAdd`).
// 3. Shift *all* existing elements (0 to size-1) one position right (logical block `shiftRightFromIndex(0)`).
// 4. Place item at buffer[0].
// 5. Increment size.
}
Direct Logic as the Plan: This direct sequence of steps (check null, ensure capacity, shift all, place at 0, increment) forms our initial implementation plan for addFirst. It clearly lays out the specific actions required.
Comparison with add(index, item): Interestingly, if we compare these steps to the skeleton for add(index, item) when index is 0, we see they are identical! Both check null, ensure capacity, shift starting from index 0, place at index 0, and increment size. This observation suggests that *after* implementing and thoroughly testing both methods based on their direct logic, a potential future refinement for DRY (Don’t Repeat Yourself) could be to have addFirst(item) simply call add(0, item). However, for our initial implementation (Step 5), we will stick to the direct logic outlined above.
The Value of Direct Outlining: Thinking through the direct logic first is a valuable Step 4 exercise. It confirms our understanding of the specific behavior and reinforces the core logic involved (like shifting *all* elements).
@Override
public void addLast(T item) {
// --- Direct Logic Skeleton ---
// 1. Check for null item (throw IllegalArgumentException).
// 2. Ensure capacity (logical block `ensureCapacityForAdd`).
// 3. Place item at buffer[size] (No shifting required!).
// 4. Increment size.
}
Direct Logic as the Plan: This direct sequence (check null, ensure capacity, place at size, increment) is our implementation plan for addLast. It’s simpler because no shifting is required when adding at the very end.
Step 4 (Shifting): add(index, item) checks if (index < size). When index == size, this condition is false, so no shifting occurs. Same behavior as addLast.
The logic is identical in effect! This confirms that a potential future refinement could be to delegate to add(size, item). However, implementing addLast directly is often preferred as it’s slightly more efficient (it avoids the if (index < size) check needed in the general add method) and reflects its specific, common use case. We will proceed with the direct implementation.
Subsubsection12.16.1.5Skeleton for addAfter(T existing, T item)
This method combines searching and adding. Its skeleton relies on the logic we’ve planned for searching (which we’ll formalize when we skeletonize indexOf) and adding.
@Override
public boolean addAfter(T existing, T item) {
// --- Skeleton Steps ---
// 1. Check for null 'existing' or null 'item' (throw IllegalArgumentException, as per Javadoc).
// 2. Find the index of the 'existing' item.
// - Plan: Perform the logic equivalent to `indexOf(existing)`:
// - Iterate from index 0 to size-1.
// - Compare buffer[i] with 'existing' using .equals() (null-safe).
// - Store the first matching index found (`foundIndex`), or -1 if not found.
// 3. If 'existing' item was found (foundIndex >= 0):
// - Plan: Execute the direct logic for adding 'item' at 'foundIndex + 1':
// - Calculate insertionIndex = foundIndex + 1.
// - Check null 'item' (already done in step 1).
// - Check bounds for 'insertionIndex' (0 <= insertionIndex <= size).
// - Ensure capacity (call logical block `ensureCapacityForAdd`).
// - Shift right (call logical block `shiftRightFromIndex(insertionIndex)` - Helper handles no-shift case).
// - Place 'item' at buffer[insertionIndex].
// - Increment 'size'.
// - Return true (indicating success).
// 4. Else ('existing' item was not found, foundIndex == -1):
// - Return false.
}
This skeleton highlights how more complex operations are often built by combining the logic of simpler, core operations. During implementation, we would likely call our actual indexOf and add methods here.
If you\’d like to see the complete code with only the skeletons for the Add methods added (as planned in this section), you can view the dr-step-4.1-add-skeletons branch in the project repository using Git checkout.
By breaking down the requirements, analyzing different cases, and identifying common logical steps (potential helpers), we have created robust skeletons for the Add methods. This detailed plan in Step 4 provides a solid foundation for the actual coding in Step 5. Next, we will apply this same thinking process to create skeletons for the "Remove" operations.
