如何实现一个支持动态扩容的数组

  支持动态扩容的数组, 其实就是实现一个简单的ArrayList, 那么我们需要实现哪些方法呢？

1. this(int capacity) // 构造方法
2. add(int element) // 增
3. remove(int index) // 删除
4. add(int index, int element) // 改
5. get(int index) // 查

  完整的代码以及测试代码如下:

public class DynamicArray {
    private static final int DEFAULT_CAPACITY_SIZE = 10;

    private int[] elementData;
    private int size = 0;

    public DynamicArray() {
        this.elementData = new int[DEFAULT_CAPACITY_SIZE];
    }

    public DynamicArray(int capacitySize) {
        if (capacitySize <= 0) {
            capacitySize = DEFAULT_CAPACITY_SIZE;
        }
        elementData = new int[capacitySize];
    }

    public boolean add(int element) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = element;
        return true;
    }

    public int add(int index, int element) {
        rangeCheck(index);

        int oldElement = elementData[index];
        elementData[index] = element;
        return oldElement;
    }

    public int get(int index) {
        rangeCheck(index);

        return elementData[index];
    }

    public int remove(int index) {
        rangeCheck(index);

        int element = elementData[index];
        int movedNum = size - index - 1;

        System.arraycopy(this.elementData, index + 1, this.elementData, index, movedNum);
        return element;
    }

    private void rangeCheck(int index) {
        if (index + 1 > size || index < 0) {
            throw new IndexOutOfBoundsException(String.format("index: %d, size: %d", index, size));
        }
    }

    /**
     * 判断是否需要扩容
     */
    private void ensureCapacityInternal(int minCapacity) {
        if (minCapacity > elementData.length) {
            grow();
        }
    }

    /**
     * 扩容
     */
    private void grow() {
        // check max value, 可以设定一个阈值, 防止数组无限膨胀
        int newCapacity = this.elementData.length << 1;
        int[] newElementData = new int[newCapacity];

        System.arraycopy(this.elementData, 0, newElementData, 0, this.elementData.length);

        this.elementData = newElementData;
    }

    @Override
    public String toString() {
        return String.format("size: %d, elementData: %s", size, JSON.toJSON(elementData));
    }

    public static void main(String[] args) {
        DynamicArray list = new DynamicArray(5);
        // test add
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println(list.toString());
        list.add(6);
        System.out.println(list.toString());

        // test update
        System.out.println(list.add(5, 5));

        System.out.println(list.toString());

        // test remove
        System.out.println(list.remove(5));

        System.out.println(list.toString());

        // test get
        System.out.println(list.get(4));


        //test error
        list.get(10);
    }
}

本文地址：https://blog.csdn.net/Kirito19970409/article/details/111961954