skip to content

How do you delete a contiguous range from an ArrayList efficiently, and why is subList(...).clear() the idiomatic approach?

level: seniorimportance: should knowfreq 35%

answer

  1. subList(from,to).clear() = range delete
  2. View routes clear to parent
  3. One System.arraycopy, not k removes
  4. Avoids forward-loop index bug
  5. Naive remove loop is O(n*k)

basics

~10 s

Use list.subList(from, to).clear(). Because the sublist is a view of the original, clearing it removes that whole range from the original list in one operation, instead of removing elements one at a time.

solid answer

~50 s

The idiomatic range delete is list.subList(from, to).clear(). Since subList returns a view backed by the parent, calling clear on the view structurally modifies the parent, removing the entire [from, to) range. List has no range-delete method of its own, and the subList Javadoc names this form as the idiom. This is both concise and efficient: for an ArrayList it shifts the tail elements left exactly once and adjusts size, rather than the naive loop of repeated remove(i) calls, each of which shifts the tail (O(n) per removal, O(n*k) total). It also avoids the classic bug of indices shifting under you while removing in a forward loop. The same view trick supports other bulk range ops, e.g. retaining a slice via copying subList, or processing a window. Just remember the view's validity rule: do the clear before any other direct structural change to the parent.

code

java · 8 lines
java
List<Integer> nums = new ArrayList<>(List.of(0, 1, 2, 3, 4, 5, 6, 7));

// Idiomatic, efficient range delete: removes positions [2, 5) -> values 2,3,4
nums.subList(2, 5).clear();
System.out.println(nums); // [0, 1, 5, 6, 7]

// Naive and slower (O(n*k)); the FORWARD version is also buggy:
// for (int i = 2; i < 5; i++) nums.remove(i); // BUG: skips elements

go deeper

for a junior

Knows subList(from, to).clear() removes a range from the original list and is cleaner than a manual loop.

for a middle

Can implement it correctly, knows it routes through the view to the parent, and recognizes the forward-loop removal bug.

for a senior

Explains the O(n) single-arraycopy vs O(n*k) repeated-remove cost difference and the correctness benefits, plus view-lifetime caveats.

for a principal

Weighs readability/perf tradeoffs across List implementations, codifies the idiom in team standards, and reasons about when a different data structure avoids range churn entirely.

## The problem You want to remove a contiguous block of elements, positions `[from, to)`, from an `ArrayList`. ## The naive approaches and why they hurt **Repeated remove by index:** ``` for (int i = to - 1; i >= from; i--) list.remove(i); // backward to keep indices valid ``` Each `ArrayList.remove(i)` shifts every element after `i` one slot left — O(n) work — and you do it `k = to - from` times, giving **O(n*k)**. A common variant removes forward (`for i from `from``) which is a **bug**: after each removal the later elements shift down, so you skip elements. ## The idiomatic approach ``` list.subList(from, to).clear(); ``` Why it works: `subList` returns a **view** sharing the parent's storage. `clear()` on that view is a structural modification routed to the parent that removes the whole range. `ArrayList`'s implementation does a **single** `System.arraycopy` to shift the tail down by `k` and then nulls out the freed slots and updates `size` — overall **O(n)** for the shift regardless of `k`, with one bulk move instead of `k` moves. ## Worked example ``` List<Integer> nums = new ArrayList<>(List.of(0,1,2,3,4,5,6,7)); nums.subList(2, 5).clear(); // removes positions 2,3,4 (values 2,3,4) // nums == [0, 1, 5, 6, 7] ``` ## Why it is preferred 1. **It is the documented idiom:** `List` has no range-delete method. The `subList` Javadoc says the view "eliminates the need for explicit range operations" and gives `list.subList(from, to).clear()` as the idiom. `ArrayList.removeRange` exists, but it is `protected`, so ordinary calling code cannot reach it; clearing the view ends up there. 2. **Performance:** one bulk shift vs. repeated shifts. 3. **Correctness:** no index-shifting bug, no off-by-one in a manual loop. 4. **Clarity:** the intent (delete this range) reads directly. ## Related range operations using the same view - **Keep only a slice:** `List<T> slice = new ArrayList<>(list.subList(from, to));` (copy out), or remove everything outside the range with two `clear` calls on the ends. - **Process a window:** iterate `list.subList(from, to)` read-only. - **Replace a range:** call `clear()` on the view, then `addAll` on the same view. Both go through the view, so it stays valid and the new elements land where the range was: on `[1, 2, 3, 4, 5]`, `subList(1, 4)` cleared and given `7, 8` leaves `[1, 7, 8, 5]`. ## Caveats - **View lifetime:** do the `clear` while the view is fresh; do not interleave direct parent structural changes. - **Not all lists are arrays:** for `LinkedList`, removal cost differs, but `subList(...).clear()` is still the correct, readable idiom. - **Bounds:** `from`/`to` must satisfy `0 <= from <= to <= size`, else `IndexOutOfBoundsException` (or `IllegalArgumentException` if `from > to`).

  • Why is removing forward in a for loop a bug?
    Each removal shifts the remaining elements left, so index i now points at what used to be i+1; iterating i upward skips every other element. Iterate backward, or use subList(...).clear().
  • Is subList(from,to).clear() O(1)?
    No. It is one bulk operation rather than k operations, but ArrayList still shifts the tail elements down by k via a single arraycopy, which is O(n). It avoids the O(n*k) of repeated removes.

  • Removing forward by index in a loop (skips elements)
  • Thinking subList(...).clear() only clears the view, not the parent
  • Claiming it is O(1) (the tail shift is still O(n))
  • Believing a view dies after its own clear: only changes made outside it invalidate it

context