JAVA / COLLECTIONS
ArrayList internals, growth and when arrays win
Predict how an ArrayList's backing array grows, cost its inserts and removals by hand, and judge when a plain array beats it.
What you will learn
- Predict capacity growth: 10 on first add, then old + (old >> 1) on each overflow
- Presize with new ArrayList<>(n) to avoid every reallocation and copy
- Cost add(i, e) and remove(i) as O(n - i) because the tail is arraycopy-shifted
- Reach for int[] over ArrayList<Integer> when the data is dense and numeric
Understanding ArrayList internals, growth and when arrays win
An ArrayList holds exactly two pieces of state: an Object[] named elementData and an int size. get(i) is a bounds check plus one array load and set(i, v) is a bounds check plus one array store, which is why indexed access is genuinely constant time and not measurably slower than a raw array. The distinction to hold onto is that capacity, the length of that array, is not size: a fresh new ArrayList<>() points at a shared zero-length array and only allocates its first ten slots when the first element arrives.
When an add would push size past capacity, the list cannot extend the array in place, because array length in Java is fixed at allocation. It allocates a new array of capacity + (capacity >> 1), which is 1.5x rounded down, giving 10, 15, 22, 33, 49, 73, copies the old contents with Arrays.copyOf, and abandons the old array. Any single add that triggers this is O(n), but because capacity grows by a constant factor the copies get rarer at exactly the rate they get more expensive, so n appends do roughly 2.5n element copies in total, which is what amortized constant time means here. Passing the expected count to the constructor skips the whole ladder.
Two costs never amortize away. add(index, e) and remove(index) call System.arraycopy to shift every element after index by one slot, so editing near the front of a long list is O(n) each time, and the array never shrinks on its own: remove and clear null out slots and lower size, but capacity stays until you call trimToSize. Arrays win when the element type is primitive, since an int[] of a million values is one contiguous 4 MB block while ArrayList<Integer> is a million references plus a million heap objects, about five times the memory and one pointer hop per element that defeats the CPU cache. Fixed-size data, multi-dimensional numeric work, and hot loops that only read by index are where the array is the right type.
Presizing is the one portable habit that follows from all this; the exact ladder is an explanation, not an API.
import java.util.ArrayList;
import java.util.List;
public class GrowthLadder {
public static void main(String[] args) {
// Same rule as java.util.ArrayList: first allocation is 10,
// then newCapacity = old + (old >> 1)
int capacity = 0;
long copied = 0;
int growths = 0;
StringBuilder ladder = new StringBuilder();
for (int size = 1; size <= 1000; size++) {
if (size > capacity) {
copied += capacity; // Arrays.copyOf moves the old elements
capacity = (capacity == 0) ? 10 : capacity + (capacity >> 1);
growths++;
if (ladder.length() > 0) ladder.append(" -> ");
ladder.append(capacity);
}
}
System.out.println("capacity ladder: " + ladder);
System.out.println("reallocations for 1000 adds: " + growths);
System.out.println("elements copied: " + copied);
System.out.println("copies per add: " + (double) copied / 1000);
List<String> presized = new ArrayList<>(1000);
for (int i = 0; i < 1000; i++) presized.add("v" + i);
System.out.println("presized size: " + presized.size() + " with 0 reallocations");
}
}An ArrayList is a fixed-length array plus a size counter, so appending is cheap only because capacity grows by a constant factor, while shifting and boxing stay expensive.
Worked examples
Shifting on insert and remove
Shows that removing by index moves the tail left, which breaks an ascending loop, and that remove takes an index unless you hand it an object.
import java.util.ArrayList;
import java.util.List;
public class Shifting {
public static void main(String[] args) {
List<Integer> source = List.of(0, 2, 4, 1, 3);
List<Integer> ascending = new ArrayList<>(source);
for (int i = 0; i < ascending.size(); i++) {
if (ascending.get(i) % 2 == 0) ascending.remove(i);
}
System.out.println("ascending removal: " + ascending);
List<Integer> descending = new ArrayList<>(source);
for (int i = descending.size() - 1; i >= 0; i--) {
if (descending.get(i) % 2 == 0) descending.remove(i);
}
System.out.println("descending removal: " + descending);
List<Integer> overloads = new ArrayList<>(source);
overloads.remove(1); // remove(int index)
overloads.remove(Integer.valueOf(4)); // remove(Object o)
System.out.println("after both removes: " + overloads);
List<String> front = new ArrayList<>(List.of("b", "c"));
front.add(0, "a");
System.out.println("insert at head: " + front);
}
}Example explained
Line 1ascending.remove(i) shifts every later element one index left, so the next i skips the element that slid into place and the 2 survives.
Line 2Counting down from size() - 1 is safe because a removal only disturbs indexes above i, which the loop has already visited.
Line 3overloads.remove(1) matches remove(int index) and deletes the element at index 1, which is the value 2; only Integer.valueOf(4) selects remove(Object).
Line 4The add at index 0 is an O(n) call: System.arraycopy moves the whole existing tail right before the new reference is stored.
Where the list ends and the array begins
Demonstrates that Arrays.asList is a fixed-size window onto an existing array, while an ArrayList copy owns storage it can grow.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ArrayBridge {
public static void main(String[] args) {
String[] backing = {"a", "b", "c"};
List<String> view = Arrays.asList(backing);
view.set(1, "B");
System.out.println("array after set: " + Arrays.toString(backing));
try {
view.add("d");
} catch (UnsupportedOperationException e) {
System.out.println("add on the view: UnsupportedOperationException");
}
List<String> resizable = new ArrayList<>(view);
resizable.add("d");
System.out.println("copy after add: " + resizable);
System.out.println("array unchanged: " + Arrays.toString(backing));
String[] out = resizable.toArray(new String[0]);
System.out.println("back to array: " + out.length + " " + out[3]);
}
}Example explained
Line 1view.set(1, "B") writes straight into backing, because Arrays.asList stores the array itself rather than a copy.
Line 2view.add("d") throws because the view has no capacity concept to grow: its length is the array's length, fixed forever.
Line 3new ArrayList<>(view) copies the three references into a fresh Object[] with room to spare, so the later add cannot touch backing.
Line 4toArray(new String[0]) allocates and fills a new String[4], which is how you hand list-built data to an API that wants an array.
The price of boxed elements
Compares the memory footprint of int[] against ArrayList<Integer> and shows the identity trap that boxing brings with it.
import java.util.ArrayList;
import java.util.List;
public class BoxedCost {
public static void main(String[] args) {
int n = 200_000;
int[] raw = new int[n];
for (int i = 0; i < n; i++) raw[i] = i;
List<Integer> boxed = new ArrayList<>(n);
for (int i = 0; i < n; i++) boxed.add(i);
System.out.println("int[] payload bytes: " + 4L * n);
System.out.println("boxed refs + object bytes: " + (4L * n + 16L * n));
List<Integer> a = new ArrayList<>(List.of(1000));
List<Integer> b = new ArrayList<>(List.of(1000));
System.out.println("1000: == " + (a.get(0) == b.get(0)) + ", equals " + a.get(0).equals(b.get(0)));
List<Integer> c = new ArrayList<>(List.of(100));
List<Integer> d = new ArrayList<>(List.of(100));
System.out.println("100: == " + (c.get(0) == d.get(0)) + ", equals " + c.get(0).equals(d.get(0)));
System.out.println("sums: " + sum(raw) + " and " + sum(boxed));
}
static long sum(int[] xs) {
long total = 0;
for (int x : xs) total += x;
return total;
}
static long sum(List<Integer> xs) {
long total = 0;
for (int x : xs) total += x;
return total;
}
}Example explained
Line 1Each list slot is a 4-byte reference under compressed oops pointing at a separate 16-byte Integer, so the boxed form needs about five times the memory and one pointer hop per read.
Line 2a.get(0) == b.get(0) is false because both lists boxed 1000 into their own Integer object; == on wrapper types compares references, not numbers.
Line 3The same comparison is true for 100 only because autoboxing goes through Integer.valueOf, which returns cached instances for -128 to 127, so identity results depend on the value.
Line 4sum(List<Integer>) unboxes on every iteration while sum(int[]) walks consecutive memory, which is the concrete reason arrays win in numeric loops.
Important notes
The initial 10 and the 1.5x factor are OpenJDK implementation details of java.util.ArrayList, not part of the List contract, so rely on presizing rather than on the exact ladder.
ArrayList is unsynchronized and never shrinks by itself: a resize racing with another thread can leave the array and size inconsistent, and fail-fast iterators only report damage after the fact.
Common mistakes
Treating new ArrayList<>(100) as a list of 100 elements: size is still 0, so get(0) and set(0, x) both throw IndexOutOfBoundsException.
Calling list.remove(1) on a List<Integer> to delete the value 1: remove(int index) wins overload resolution, so index 1 disappears instead, or a short list throws IndexOutOfBoundsException.
Expecting clear() to release memory: it nulls the slots and zeroes size but keeps capacity, so a list that once held a million entries pins a million-slot array until trimToSize().
Try it yourself
Change, predict, then run
Run the growth simulation with the loop bound raised from 1000 to 100000 and note the reallocation count and total elements copied. Divide the copies by the element count and confirm the ratio stays between 2 and 3 rather than climbing with n.
Open the Java workspaceCheck your understanding
Appending to an ArrayList is called amortized constant time even though some appends copy the entire backing array. What makes that claim hold?
- System.arraycopy is a native intrinsic, so the growth copy costs nothing measurable
- The array grows by one slot per add, so no single copy ever moves more than one element
- Each reallocation multiplies capacity, so the total elements copied over n appends stays proportional to n
- The copy is deferred until the next get, spreading its cost over later reads
Show answer
Because capacity grows by a factor of 1.5, the capacities form a geometric sequence and the copies sum to roughly 2 to 3 times n, a bounded amount of work per append. Option 0 is tempting since arraycopy really is an intrinsic, but a fast O(n) copy on every add would still make n appends O(n squared); the guarantee comes from how rarely the copy happens, not how fast it runs.