Implementing ArrayList Algorithms
Introduced| English |
|---|
| shift/ʃɪft/ |
| delete/dɪˈliːt/ |
| insert/ˈɪnsɜːt/ |
Adjacent removals reveal a skipped element
- Starting with
[0, 0, 5], remove index 0 and then increment i. The second zero has shifted into index 0, so that forward loop skips it and leaves[0, 5]. - For the forward while-loop taught here, stay at the same index after removal and advance only when keeping an element. It then removes both zeros and finishes with
[5].
Keep the current forward index after removal
- After
remove(i), every later element shifts one place left. If an element now occupies i, it has not yet been checked; inspect it on the next iteration. - The loop below accepts a non-null list of non-null Integers and removes every zero in place. It uses current size each iteration and performs no get call on an empty list.
import java.util.ArrayList;
public class RemoveZeros {
public static void removeZeros(ArrayList<Integer> list) {
int i = 0;
while (i < list.size()) {
if (list.get(i) == 0) {
list.remove(i);
} else {
i++;
}
}
}
}
Explain why this loop terminates
- Each iteration either removes one element and reduces size, or keeps one and increases i. Thus
size() - i, the number of positions still to check, decreases by one each iteration. - Starting with
[0, 0, 5], the states are[0, 5]at i=0,[5]at i=0, then[5]at i=1. The final condition is false, so no out-of-bounds access occurs.
A backward loop follows a different rule
- A reverse loop starts at the final existing index:
for (int i = list.size() - 1; i >= 0; i--). Remove matching elements withremove(i); the next i is always one lower. - Deleting at i shifts only later indices, which have already been checked. Earlier unchecked elements retain their indices, so decrementing after a removal is correct here; “never advance after removal” is not a universal rule.
Choose an index update that matches the direction of traversal. In the forward while-loop, stay after removal; in the backward for-loop, continue decrementing. Direct structural changes during an enhanced loop are a separate unsafe pattern, even when no fail-fast exception appears.
In the forward while-loop shown here, advance i only when you...
After remove(i), the next element shifts into i — don't skip it.
The naive forward loop on [0, 0, 5] that removes at i=0 and then increments i skips the next zero.
The remaining zero shifts into index 0, but the next test is at index 1. A backward loop uses a different correct index rule.
An alternative to in-place removal that avoids shifting is to...
Adding keepers to a fresh list sidesteps shifting.
ArrayList algorithms reuse array patterns via...
Swap array [] and length for get(i) and size().
The resizable nature of an ArrayList lets you insert and delete elements, unlike a fixed array.
add and remove change the list's size.
A backward removal loop starting at size()-1 must stay at the same index after every deletion.
False: earlier unchecked elements retain their indices, so the backward loop decrements normally.
Build a new list when the original must remain
- To preserve the original list, create a fresh result and append every nonzero element while reading the original. This keeps the original sequence and its size unchanged; it uses additional list storage.
- For lists of mutable objects, copying retained references does not clone those objects. A new list structure may still share its element objects with the original; distinguish list identity from element identity.
Forward removal keeps the index after a deletion
Two adjacent zeros are checked at index 0 before 5 is kept.
Check the cases that expose the algorithm
- Test an empty list, all zeros, no zeros, adjacent zeros and a zero at the last index. For in-place removal, other references to the same list observe its change; a fresh result leaves that original structure intact.
- An ArrayList can insert 插入 or delete 删除 elements; those operations can shift 移位 later indices. A search may return a found index or -1 when absent; a maximum requires an explicit empty-list policy. Reusing array patterns through get/size helps, but each algorithm still needs its own bounds and contract.
Removing shifts indices. Explain which elements remain unchecked and choose the next index accordingly. Forward stay-or-increment and backward decrement are both valid patterns; a fresh list of keepers preserves the original structure but may share objects.
Order the states for the corrected removal loop on [0, 0, 5].
Each removal rechecks the shifted value; keeping 5 finally advances the index.
How many get calls does the shown forward removeZeros method make on an empty list?
The initial condition 0 < 0 is false, so no get call occurs.