Java › Arrays & Multidimensional Arrays
How would you implement a custom, resizable dynamic array (similar to ArrayList's internal mechanism) from scratch using a raw Java array, including the amortized doubling growth strategy?
AdvancedAnswer
A dynamic array wraps a fixed-size backing array along with a separate size counter (tracking logically used elements, distinct from the backing array's full capacity); when an add operation would exceed capacity, allocate a new backing array (conventionally double the current capacity) and copy existing elements over via System.arraycopy() -- this doubling strategy gives amortized O(1) add performance, since the expensive resize-and-copy operation happens increasingly rarely relative to the number of cheap O(1) adds, exactly matching how java.util.ArrayList is implemented internally.
public class SimpleDynamicArray<T> {
private Object[] data = new Object[10];
private int size = 0;
public void add(T element) {
if (size == data.length) {
data = Arrays.copyOf(data, data.length * 2); // double capacity
}
data[size++] = element;
}
@SuppressWarnings("unchecked")
public T get(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
return (T) data[index];
}
public int size() { return size; }
}Real-world example An educational exercise reimplements a simplified version of ArrayList from scratch to demonstrate the amortized doubling growth strategy, showing why ArrayList's add() operation is described as amortized O(1) despite an occasional individual call actually costing O(n) during a resize event.