skip to content

How do you use System.arraycopy to insert or remove an element within the same array, and why is the in-place overlap correct?

level: seniorimportance: should knowfreq 35%

answer

  1. remove → shift [i+1,n) left onto i
  2. insert → shift [i,n) right, then write at i
  3. src == dest, overlapping ranges
  4. memmove semantics → right shift stays correct
  5. mirrors ArrayList.add(index)/remove(index), O(n)

basics

~20 s

To remove an element you shift the elements after it one slot left; to make room for an insert you shift them one slot right. You call System.arraycopy with the same array as both source and destination — it handles the overlapping ranges correctly.

solid answer

~50 s

ArrayList-style structures use System.arraycopy with src == dest to shift a block of elements. To remove index i from a backing array of size n, you copy the range [i+1, n) onto [i, n-1) — shifting left and overwriting the removed element. To insert at index i, you first shift [i, n) to [i+1, n+1) — moving right to open a gap — then write the new value at i. The crucial point is that arraycopy has memmove semantics: even though source and destination overlap, it behaves as if the source were read into a temporary buffer first, so a right shift does not overwrite elements it still needs to read. A naive forward loop would corrupt a right shift. This is why arraycopy, not a hand-rolled loop, is the idiomatic and safe tool for in-place element shifting, and it is exactly what ArrayList.add(index,e) and remove(index) do internally.

code

java · 15 lines
java
// Remove element at index i from a backing array of logical size n.
static void removeAt(Object[] a, int n, int i) {
    int numToShift = n - i - 1;
    if (numToShift > 0) {
        System.arraycopy(a, i + 1, a, i, numToShift); // shift left
    }
    a[n - 1] = null; // clear freed slot so the reference can be GC'd
}

// Insert value at index i; capacity must be >= n + 1.
static void insertAt(Object[] a, int n, int i, Object value) {
    int numToShift = n - i;
    System.arraycopy(a, i, a, i + 1, numToShift); // shift right (overlap-safe)
    a[i] = value;
}

go deeper

for a junior

Understands that inserting/removing in the middle of an array means shifting other elements.

for a middle

Can write the left-shift remove and right-shift insert calls with correct counts and clear the freed slot.

for a senior

Explains memmove overlap semantics, why a naive right-shift loop corrupts data, and ties it to ArrayList's O(n) middle ops and reference-leak avoidance.

for a principal

Connects it to data-structure design tradeoffs (array-list vs linked-list vs gap buffer), GC implications of stale references, and copy-direction internals of the intrinsic.

## The problem Arrays are fixed-size, so list-like structures (e.g. `ArrayList`) keep a larger backing array and a `size` count, and they *shift* elements to insert or remove in the middle. `System.arraycopy` with the **same array** as source and destination is the tool for that shift. ## Removing an element at index i (array of logical size n) You want to delete `a[i]` and slide everything after it one slot to the left: ```java int numToShift = n - i - 1; // elements after i if (numToShift > 0) { System.arraycopy(a, i + 1, a, i, numToShift); } a[n - 1] = 0; // (or null) clear the now-duplicated last slot // new logical size is n - 1 ``` Reading from `i+1` and writing to `i` is a **left shift**. For a left shift, a simple forward loop would also work, because each destination index is *behind* its source — you read before you overwrite. But arraycopy is still preferred for speed and clarity. ## Inserting a value at index i You must open a gap by sliding `[i, n)` one slot to the **right**, then drop the new value in: ```java // assume capacity >= n + 1 int numToShift = n - i; // elements from i onward System.arraycopy(a, i, a, i + 1, numToShift); // right shift a[i] = value; // new logical size is n + 1 ``` ## Why overlap is correct: memmove semantics Here is the subtle part. A **right shift** has destination indices *ahead* of their sources, and the ranges overlap. Consider `a = [A, B, C]`, inserting at index 0, so we shift `[0,3)` to `[1,4)`. A naive forward loop would do: ``` a[1] = a[0] -> [A, A, C] // we just clobbered the old a[1]=B! a[2] = a[1] -> [A, A, A] // reads the corrupted value ``` It corrupts the data. `System.arraycopy` is specified to behave **as if** the source range were first copied to a temporary array and then written to the destination — this is the same guarantee C's `memmove` gives (as opposed to `memcpy`, which is undefined on overlap). So it produces the correct `[A, A, B, C]`-style result regardless of shift direction. Internally the JVM achieves this by copying back-to-front when needed, but you don't have to think about direction — the contract guarantees correctness. ## Why this matters This exact pattern is what `ArrayList.add(int index, E element)` and `ArrayList.remove(int index)` do. Knowing it explains list performance: a middle insert/remove is **O(n)** because of the shift, while appending at the end is amortized **O(1)** (no shift, just an occasional grow via `Arrays.copyOf`). It also explains why you should clear the freed trailing slot after a remove (`a[n-1] = null`) so you don't leak a reference and prevent garbage collection.

  • What is the time complexity of inserting into the middle of an ArrayList, and why?
    O(n). The backing array must shift all elements after the insertion point one slot right via System.arraycopy, which touches up to n elements. Appending at the end is amortized O(1) because no shift is needed (only an occasional grow).
  • After removing an element by shifting left, why set the last slot to null?
    The shift duplicates the last element's reference into the new last position, leaving a stale reference in the old final slot. Nulling it lets the garbage collector reclaim the removed object and avoids a subtle memory leak.

saying these in an interview costs you the question

  • Claiming a naive forward loop is a safe substitute for a right shift — it corrupts overlapping data
  • Forgetting to null out the freed trailing slot after a remove (reference leak)
  • Off-by-one in the count: remove shifts n-i-1, insert shifts n-i
  • Thinking middle insert/remove is O(1) — the shift makes it O(n)

context

resolving links…