datastructures0DynamicArray

1package pkg3datastructures;2 3/*4 * datastructures0DynamicArray.java5 * --------------------------------6 * Resizable array (like ArrayList internals): append, get, set, insert, remove.7 *8 * COMPLEXITY:9 *  - get/set at index: O(1)10 *  - append: O(1) amortized (doubling resize)11 *  - insert/remove at index: O(n)12 *13 * WHEN TO USE: need indexed random access with unknown/growing size.14 */15import java.util.Arrays;16 17public class datastructures0DynamicArray {18 19    private int[] data;20    private int size;21 22    datastructures0DynamicArray() {23        data = new int[4];24        size = 0;25    }26 27    int size() { return size; }28 29    int get(int index) {30        checkIndex(index);31        return data[index];32    }33 34    void set(int index, int value) {35        checkIndex(index);36        data[index] = value;37    }38 39    void append(int value) {40        ensureCapacity(size + 1);41        data[size++] = value;42    }43 44    void insert(int index, int value) {45        if (index < 0 || index > size) throw new IndexOutOfBoundsException(index);46        ensureCapacity(size + 1);47        System.arraycopy(data, index, data, index + 1, size - index);48        data[index] = value;49        size++;50    }51 52    int removeAt(int index) {53        checkIndex(index);54        int removed = data[index];55        System.arraycopy(data, index + 1, data, index, size - index - 1);56        size--;57        return removed;58    }59 60    private void ensureCapacity(int min) {61        if (min <= data.length) return;62        int newCap = Math.max(data.length * 2, min);63        data = Arrays.copyOf(data, newCap);64    }65 66    private void checkIndex(int index) {67        if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);68    }69 70    @Override71    public String toString() {72        return Arrays.toString(Arrays.copyOf(data, size));73    }74 75    public static void main(String[] args) {76        datastructures0DynamicArray arr = new datastructures0DynamicArray();77        for (int i = 1; i <= 6; i++) arr.append(i * 10);78        System.out.println("after append: " + arr);79 80        arr.insert(2, 25);81        System.out.println("after insert(2,25): " + arr);82 83        System.out.println("removeAt(3)=" + arr.removeAt(3) + " -> " + arr);84        arr.set(0, 99);85        System.out.println("after set(0,99): " + arr + " get(0)=" + arr.get(0));86    }87}