Removing in a loop: the skipping bug and the right ways
removeIf marks the doomed elements first, then compacts the array once, so it's O(n) instead of O(n²).
ArrayList is a growable array: an Object[] plus a size counter. Reading by index is O(1), adding at the end is amortised O(1) because the array grows by 1.5x when full, and inserting or removing in the middle is O(n) because System.arraycopy shifts every later element.
Change the code and press Run (Ctrl+Enter). Try to predict the output first, then break it on purpose and read the error. Your edits are saved and match the lesson page.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Write static List<Integer> capacities(int adds) that returns the capacity sequence an ArrayList goes through (starting from 10 at the first add) while adding adds elements. Print the result for 100 adds.
Given List<String> words = new ArrayList<>(List.of("a", "bb", "ccc", "dd", "e")), remove every word of length 2 in a single O(n) pass without removeIf, by compacting in place with a write index, then trimming the tail.
Show that list.subList(1, 3).clear() removes elements from the original list. Start with [0, 1, 2, 3, 4] and print the list after the call.
Explain it without notes
Describe how ArrayList.add works, including what happens when the array is full.
Why is appending to an ArrayList amortised O(1) when a single add can be O(n)?
What is the difference between capacity and size, and how do ensureCapacity and trimToSize relate to them?
Why is ArrayList usually faster than LinkedList even for some insert-heavy workloads?
What is the cost of add(0, e), remove(0), contains(e) and get(i) on an ArrayList of n elements?
Expected output
forward loop: [4, 5, 8]
backward loop: [5]
removeIf: [5]