Arrays in Different Programming Languages

Every array — whether a Java int[], a Python list, or a Go slice — is a thin language-level wrapper around the same physical idea: a block of contiguous memory addressed as base + index * elementSize, giving O(1) random access. Languages diverge only in what sits on top of that block: a fixed-capacity raw buffer (Java/C++/Go arrays), or a resizable handle that owns a buffer plus a length/capacity pair and reallocates it by geometric growth when it fills up (ArrayList, Python list, JS array, C++ vector, Go slice, C# List<T>). Understanding that handle-plus-buffer mechanism — not just syntax differences — is what interviewers are actually probing when they ask "how does ArrayList resize?" or "why is appending to a Python list amortized O(1)?"

Recognize the pattern

• Question mentions "array vs. list", "why is append usually fast but occasionally slow", or "what happens when a dynamic array runs out of space".
• You need to reason about amortized complexity, not worst-case-per-call complexity.
• You're asked to implement a growable array/vector/ArrayList from scratch — a classic "design a data structure" interview question.
• Cross-language trivia: fixed-size stack arrays (C++ std::array, Go [N]T) vs heap-backed dynamic containers, or the exact growth factor a given language's dynamic container uses.

Brute force vs. optimal growth

Brute force (grow-by-1): every time the backing buffer is full, allocate a new buffer exactly one slot larger and copy everything over. Appending n elements costs 1+2+3+...+n = O(n²) total copy work — each individual append can be O(1) or O(n), but the running average degrades badly as n grows.

Optimal (geometric growth): when full, allocate a new buffer that is some constant factor g > 1 times the current capacity, copy elements once, then continue appending into the spare room. Any fixed g > 1 gives amortized O(1) append — the exact factor is an implementation choice, and real languages disagree: Java's ArrayList grows by 1.5x (OpenJDK's newCapacity = oldCapacity + (oldCapacity >> 1)), C#'s List<T> grows by 2x (newcapacity = 2 * _items.Length, doubling), C++'s std::vector is implementation-defined (libstdc++ doubles at 2x, MSVC uses 1.5x), and CPython's list uses a gentler ~1.125x to reduce peak waste. Go's append roughly doubles for small slices and tapers to ~1.25x for large ones.

Complexity, derived

To see why geometric growth works, take the simplest case — growth factor g = 2 (doubling) — starting at capacity 1. After n appends, resizes happen at sizes 1, 2, 4, 8, ..., up to the largest power of two ≤ n — about log₂n resizes. The total copy work across all resizes is:

1 + 2 + 4 + 8 + ... + n  ≈ 2n   (geometric series sums to ~2x the last term)

So n appends cost O(n) total copying, spread over n calls → amortized O(1) per append, even though any single append that triggers a resize is O(n) in that instant. The same argument holds for any g > 1, just with a different constant: for growth factor g, the series sums to at most g/(g-1) × n, still O(n) total.

The growth factor also sets the worst-case memory overhead — the wasted space right after a resize, when capacity has just grown but few new elements have been added yet. For g = 2 (doubling, as in C#'s List<T> or libstdc++'s vector), the buffer can be up to 2x the stored element count, i.e. up to 100% overhead. For g = 1.5 (Java's real ArrayList, MSVC's vector), the worst case is smaller: capacity is at most 1.5x the count needed, so overhead tops out around 50%, not 100%. Fixed-size arrays (Java int[], Go [N]T, C++ std::array) have zero overhead and O(1) guaranteed (not amortized) access/writes, but cannot grow at all — you allocate a new array and copy manually.

Traced example: appending 5 ints with doubling growth (g = 2, illustrative)

Total element copies = 0+1+2+0+4 = 7 for 5 appends (< 2n = 10), confirming the O(n) total / O(1) amortized bound. This table uses g = 2 purely because the arithmetic is cleanest; a g = 1.5 trace (Java's real ArrayList) follows the identical logic with smaller capacity jumps (1, 2, 3, 4, 6, 9, ... — from capacity 1 the 1.5× step 1+(1>>1)=1 is bumped up to the required minCapacity, so it never stalls).

Minimal hand-rolled growable array (illustrative doubling model, not any specific language's exact internals)

class GrowableIntArray {
    private int[] buf = new int[1];
    private int size = 0;

    void add(int x) {
        if (size == buf.length) {
            int[] bigger = new int[buf.length * 2]; // g = 2, for teaching clarity
            System.arraycopy(buf, 0, bigger, 0, size);
            buf = bigger;
        }
        buf[size++] = x;
    }

    int get(int i) {
        if (i < 0 || i >= size) throw new IndexOutOfBoundsException();
        return buf[i];
    }

    int size() { return size; }
}

This deliberately uses g = 2 because it is the easiest growth factor to reason about by hand. Java's real ArrayList does not double — its actual internal resize (in ArrayList.grow()/newCapacity()) computes newCapacity = oldCapacity + (oldCapacity >> 1), i.e. 1.5x growth. Swap the line marked above for buf.length + (buf.length >> 1) (with a minimum of 1) to mirror the real ArrayList behavior exactly.

Cross-language comparison

Note: Python's list stores references to objects, not the objects inline — that's why it can hold mixed types, at the cost of pointer-chasing and per-element boxing overhead versus C++/Java/Go's inline contiguous primitives.

Pitfalls

• Assuming every append/add call is O(1) worst-case — it isn't; the resize call is O(n). Latency-sensitive code (real-time systems) sometimes pre-sizes (new ArrayList<>(n), Go's make([]T, 0, n)) to avoid resize spikes.
• Holding references into a dynamic array's old buffer across an append — in Go, appending to a slice may or may not reallocate, silently detaching a previously-aliased slice from further mutations.
• Confusing a fixed array's O(1) guarantee with a dynamic array's amortized O(1) — they are not the same guarantee under a hard real-time deadline.
• Assuming Java's ArrayList doubles like C#'s List<T> — it actually grows by 1.5x, so its worst-case memory overhead (~50%) is lower than a true doubling container's (~100%). Mixing up which language uses which factor is a common interview slip.
• In Python, using a list where a fixed-type array module or NumPy array would save substantial memory for large numeric datasets.

When to use / when not — trade-offs vs linked list

Use a (dynamic) array when you need O(1) random access by index and appends are mostly at the end — the vast majority of interview and real-world cases. Use a fixed-size array/std::array when the size is known at compile time and you want zero allocation overhead and best cache locality (e.g. tight numerical loops, embedded systems). Prefer a linked list instead when you need frequent insertion/deletion at arbitrary (non-end) positions without shifting elements — but you give up O(1) random access (becomes O(n)) and cache locality (nodes scattered on the heap) in exchange.

Takeaways

• All arrays reduce to contiguous memory + O(1) indexing; dynamic arrays add a resizable buffer with geometric growth at some factor g > 1.
• Geometric growth turns O(n²) grow-by-1 copying into O(n) total copying → amortized O(1) append, for any fixed g.
• The growth factor sets the worst-case memory overhead: g = 2 (C# List<T>, libstdc++ vector) tops out around 100% overhead; g = 1.5 (Java ArrayList, MSVC vector) tops out around 50%.
• Language choice of array type (fixed vs list vs vector vs slice) reflects the same core mechanism with different growth factors and type-safety trade-offs — memorize the real factor per language rather than assuming they all double.

Recall: Java's ArrayList grows by 1.5x, not 2x. Given that, after n appends starting from capacity 1, is the total number of element copies still O(n), and what does that make the amortized cost per append?

Source: adapted and deepened from the original "Arrays in Different Programming Languages" reference page; growth-factor corrections verified against OpenJDK's ArrayList.grow()/newCapacity() (1.5x) and .NET's List<T>.Grow() (2x).