Arrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Two flavors of sequence
Java gives you two sequential containers: the built-in array (int[], String[], ...) with a fixed length set at creation, and ArrayList<E>, a class that wraps a backing array and grows on demand. Arrays are lower level and slightly faster; ArrayList is more flexible and where you'll spend most of your time.
Memory layout
An array of primitives is a contiguous block of memory — an int[100] is exactly 400 bytes plus a small object header. That contiguity is why iteration is fast: the CPU prefetches the next cache line before you ask for it. ArrayList<Integer> is a bit different: the backing array holds references to Integer objects scattered across the heap, so each element access is a pointer chase. When performance matters and elements are primitives, prefer plain arrays.
How ArrayList grows
When add is called and the backing array is full, ArrayList allocates a new array — typically 1.5× the current capacity — copies the elements over, and drops the old array for the garbage collector. A single grow is O(n), but because capacity doubles rather than growing by one, the total work across n inserts is O(n). Divide by n and you get O(1) *amortized* per append. That's the magic.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Operations and complexity
Index access get(i) and set(i, v) are O(1). Append add(v) is amortized O(1). Insert or remove in the middle is O(n) because everything to the right shifts one slot. contains(x) is O(n) — it walks the array. When you need frequent middle-insertions, an ArrayList is the wrong structure; when you need fast lookups, use a HashMap or HashSet instead.
When to reach for an array
Use a plain array when the size is known up front, when you need primitives without the boxing tax, or when you're implementing a lower-level structure yourself. Multi-dimensional numeric grids (double[][] matrix), fixed lookup tables, and hot loops that count iterations all benefit. Arrays also have a compact declaration syntax: int[] xs = {1, 2, 3};.
When to reach for ArrayList
Use ArrayList when the size changes over time, when you want the rich Collections API (stream, removeIf, sort), or when you interoperate with libraries that expect a List. Give it an initial capacity if you know the final size — new ArrayList<>(10_000) skips several grow-and-copy cycles.
Gotchas
Arrays.asList(1, 2, 3) returns a fixed-size list backed by the array — you can set but not add or remove. Wrap it in new ArrayList<>(...) if you need a mutable list. List.of(1, 2, 3) is fully immutable and throws on any mutation. And never mix int[] with List<Integer> casually — the boxing round-trip is expensive.