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

~40 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. 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. **Performance:** one bulk shift vs. repeated shifts. 2. **Correctness:** no index-shifting bug, no off-by-one in a manual loop. 3. **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:** `clear()` the view then `addAll` at the position — but be careful, the view is invalid after its own structural change in some implementations; re-derive indices on the parent. ## 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.

saying these in an interview costs you the question

  • 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))
  • Reusing the view after its own structural modification without re-deriving indices

context

resolving links…