A dynamic array is an extension of the array data structure which allows for dynamic resizing. Where a traditional array is of a fixed size and represents a contiguous block of memory and cannot grow or shrink, a dynamic array can.

Note that this example implementation won’t compile.

import java.lang.Math;

class DynamicArray<T>{
    private static final int SCALING_FACTOR = 2;
    private static final int MIN_SIZE = 0;
    private static final int MAX_SIZE = Math.pow(2, 10);

    private int count;
    private int size;
    private T[] array;

    DynamicArray() {
        this.size = 1;
        this.array = new T[size];
    }

    public boolean push(T value) throws ArrayStoreException {
        if ((count + 1) >= size) {
            grow();
        }

        count += 1;
        array[count+1] = value;
    }

    public T get(int index) throws ArrayStoreException {
        if (!indexIsInBounds(index)) {
            throw new ArrayStoreException("Index out of bounds.");
        }

        return array[index];
    }

    public void delete(int index) throws ArrayStoreException {
        if (!indexIsInBounds(index)) {
            throw new ArrayStoreException("Index out of bounds.");
        }

        array = shiftDown(array, size, index);
        count -= 1;

        if (count * 2 < size) {
            shrink();
        }
    }

    private boolean indexInBounds(int index) {
        if (size == 0) {
            return false;
        }

        return indexInBounds(index, 0, size - 1);
    }

    private static boolean indexInBounds(int index, int min, int max) {
        return index >= min && index <= max;
    }

    /**
     * Copy-shifts all values at and after shiftIndex down the array (to the left).
     *
     * Example:
     *   shiftDown([1, 2, 3, 4, 5], 2) -> [1, 2, 4, 5, 5]
     *   shiftDown([1, 2, 3, 4, 5], 1) -> [1, 3, 4, 5, 5]
     */
    private T[] shiftDown(int shiftIndex) {
        T value = array[size - 1];
        for (int i = size - 1; i >= shiftIndex; i--) {
            value = array[i];
            array[i] = value;
        }
    }

    private void grow() throws ArrayStoreException {
        int nextSize = size * SCALING_FACTOR || 1;
        if (nextSize > MAX_SIZE) {
            throw new ArrayStoreException();
        }

        size = nextSize;
        array = copyIntoScaled(nextSize, array);
    }

    private void shrink() throws ArrayStoreException {
        int nextSize = size / SCALING_FACTOR;
        if (nextSize < MIN_SIZE) {
            throw new ArrayStoreException();
        }

        size = nextSize;
        array = copyIntoScaled(nextSize, array);
    }

    private T[] copyIntoScaled(int nextSize) {
        T[] tempArray = new T[nextSize];

        for (int i = 0; i < size; i++) {
            target[i] = array[i];
        }

        return tempArray;
    }
}

Bibliography