Implementing ArrayList Algorithms
| English | Chinese | Pinyin |
|---|---|---|
| insert | 插入 | chā rù |
| delete | 删除 | shān chú |
| shift | 移位 | yí wèi |
Same patterns, new powers
- ArrayList algorithms reuse the same patterns as arrays — with list methods.
- Count / sum / max: traverse with
get(i)and accumulate. - Search: return the index where found, or
-1. - The resizable nature adds two new powers: insert 插入 and delete 删除.
Removing matching elements
- To delete every element matching a condition, you must handle the shift 移位.
- After
remove(i), the next element slides into indexi— so don't advancei. - Pattern:
while (i < list.size()) { if (match) list.remove(i); else i++; } - Only increment
iwhen you keep an element.
Why the index trick
- A forward
forloop withi++andremove(i)skips the element after each removal. - The removed element's neighbor takes its index but is never checked.
- Staying at the same
iafter a remove re-checks the shifted element. - This is the standard "remove-while-traversing" fix.
Building a new list
- Sometimes it's cleaner to build a new list of the elements you want to keep.
- Traverse the original,
addeach keeper to a fresh ArrayList. - No shifting to worry about — the original is left unchanged.
- Choose this when in-place removal logic gets tricky.
ArrayList operations
Step through building and changing an ArrayList and watch it grow and shrink.
When removing from an ArrayList in a loop, only advance the index when you DON'T remove. After list.remove(i), the next element moves into position i; a blind i++ skips it. Use while (i < list.size()) { if (remove-it) list.remove(i); else i++; }. Or sidestep the whole problem by building a new list of the keepers.
Removing all zeros from an ArrayList
int i = 0;while (i < list.size()) { if (list.get(i) == 0) list.remove(i); else i++; }- Each removal leaves
iunchanged so the shifted element is still checked.
ArrayList algorithms reuse array patterns (sum, count, max, search) via get(i)/size(), plus insertion and deletion. To remove matching elements in a loop, only advance i when you keep an element (a remove(i) shifts the rest left). Alternatively, build a new list of the keepers to avoid shifting entirely.
When removing matching elements in a loop, you should advance i only when you...
After remove(i), the next element shifts into i — don't skip it.
A forward for loop with i++ and remove(i) skips the element after each removal.
The shifted neighbor takes index i but is never checked.
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.