首先需要声明的是，Java本身是提供了变长数组的，即ArrayList。那么自定义一个变长数组有啥用？其实没啥用或者说用处不大，这里主要就是为了了解下变长数组的设计理念而已。实际工作中直接使用ArrayList。

思路分析

主要功能点

1. 新建时可以指定容量大小，不指定时使用默认容量大小。

2. 向数组中追加新元素，当超过容量时应该自动扩容。

3. 向数组中指定位置添加新元素，需要考虑指定的下标是否越界，同样也需要考虑扩容操作。

4. 删除末尾的元素，需要考虑缩小容量。

5. 删除指定位置元素，需要考虑指定的下标是否越界，同样也需要考虑缩小容量。

6. 修改特定位置的元素，需要考虑指定的下标是否越界。

7. 以时间复杂度为O(1)获取任意位置的元素，需要考虑指定的下标是否越界。


主要注意点

1. 扩容：这里扩容 2 倍（ArrayList 是扩容 1.5 倍），扩容时新建一个 2 倍容量的新数组，然后将旧数组中的元素按顺序拷贝到新数组。

2. 缩容：当数组中的元素个数 <= 0.25 * 容量时，自动缩小容量为原来的一半，新建一个容量是原来容量一半的数组，然后将旧数组中的元素按顺序拷贝到新数组。（ArrayList 缩小为和当前元素个数一样大）。

3. 指定位置添加：需要先将指定位置及后面所有的元素都向后移动一位，将指定位置空出来然后再插入。

4. 指定位置删除：先将指定位置删除，然后将后面的所有元素都向前移动一位。

5. 容量大小：需要指定容量的最大值，避免 OOM 的发生。最小值可以指定也可以不指定。


代码实现

/** * 变长数组 * */public class ResizeableArray<E> {    private static final int MIN_CAPACITY = 10;    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;    // 当前实际数据大小    private int size = 0;    // 实际存放元素的数组，容量为 elements.length    private Object[] elements;        public ResizeableArray(){        this(MIN_CAPACITY);    }        public ResizeableArray(int initCapacity){        if(initCapacity < MIN_CAPACITY){            initCapacity = MIN_CAPACITY;        }else if(initCapacity > MAX_CAPACITY){            initCapacity = MAX_CAPACITY;        }        this.elements = new Object[initCapacity];    }        // 数组的特性，根据下标获取元素    public E get(int index){        this.checkIndex(index);        return (E)elements[index];    }        // 添加一个元素到最后    public void add(E element){        if(size == elements.length){            // 需要扩容            this.expandCapacity();        }        elements[size++] = element;    }    // 添加一个元素到指定位置    public void add(int index, E element){        if(index == size){            this.add(element);            return;        }        this.checkIndex(index);        if(size == elements.length){            // 需要扩容            this.expandCapacity();        }        // 需要先将index和之后的所有元素向后移动一位        for(int i = size - 1; i >= index; i--){            elements[i + 1] = elements[i];        }        elements[index] = element;        size++;    }    // 设置下标为index的元素    private void set(int index, E element){        this.checkIndex(index);        elements[index] = element;    }
    /**     * 删除下标为index的元素     * 当 size <= 0.25 * capacity 的时候缩小容量     */    private void delete(int index){        this.checkIndex(index);        elements[index] = null;        // 如果删除的不是最后一个元素，需要将后续元素往前移动一位        if(index < size - 1){            for(int i = index + 1; i < size; i++){                elements[i - 1] = elements[i];            }        }        size--;        if(size <= 0.25 * elements.length){            this.reduceCapacity();        }    }
    private void deleteLast(){        this.delete(size - 1);    }
    private void checkIndex(int index){        if(index < 0 || index >= size){            throw new IndexOutOfBoundsException(String.format("Out of bounds at: %s, size is: %d", index, size));        }    }
    private void expandCapacity(){        if(MAX_CAPACITY == elements.length){            // 容量达到最大限制，无法扩容。            throw new RuntimeException("The capacity has reached its maximum limit and cannot be expanded.");        }        int newCapacity = Math.min(elements.length << 1, MAX_CAPACITY);        Object[] newElements = new Object[newCapacity];        System.arraycopy(elements, 0, newElements, 0, size);        elements = newElements;    }
    private void reduceCapacity(){        if(elements.length == MIN_CAPACITY){            return;        }        int newCapacity = Math.max(elements.length >> 1, MIN_CAPACITY);        Object[] newElements = new Object[newCapacity];        System.arraycopy(elements, 0, newElements, 0, size);        elements = newElements;    }
    public static void main(String[] args){        ResizeableArray<Integer> resizeableArray = new ResizeableArray<>();        System.out.printf("初始化后，size为: %d n", resizeableArray.size);        System.out.printf("初始化后，capacity为: %d n", resizeableArray.elements.length);        System.out.println();
        for(int i = 0; i < 20; i++){            resizeableArray.add(i);        }
        System.out.printf("添加20个元素后，size为: %d n", resizeableArray.size);        System.out.printf("添加20个元素后，capacity为: %d n", resizeableArray.elements.length);        System.out.printf("添加20个元素后，第5个元素是: %d n", resizeableArray.get(4));        System.out.println();
        resizeableArray.delete(4);
        System.out.printf("删除第五个元素后，size为: %d n", resizeableArray.size);        System.out.printf("删除第五个元素后，capacity为: %d n", resizeableArray.elements.length);        System.out.printf("删除第五个元素后，第5个元素是: %dn", resizeableArray.get(4));        System.out.println();
        resizeableArray.add(4, 100);        System.out.printf("在第五个位置插入元素后，size为: %d n", resizeableArray.size);        System.out.printf("在第五个位置插入元素后，capacity为: %d n", resizeableArray.elements.length);        System.out.printf("在第五个位置插入元素后，第5个元素是: %dn", resizeableArray.get(4));        System.out.println();
        for(int i = 0; i < 15; i++){            resizeableArray.deleteLast();        }        System.out.printf("删除后面15个元素后，size为: %d n", resizeableArray.size);        System.out.printf("删除后面15个元素后，capacity为: %d n", resizeableArray.elements.length);        System.out.printf("删除后面15个元素后，第5个元素是: %dn", resizeableArray.get(4));        System.out.println();
        resizeableArray.set(4, 200);        System.out.printf("修改第五个元素后，当前size为: %d n", resizeableArray.size);        System.out.printf("修改第五个元素后，capacity为: %d n", resizeableArray.elements.length);        System.out.printf("修改第五个元素后，第5个元素是: %dn", resizeableArray.get(4));    }}

测试结果

由执行结果可知：

 1. 初始化后默认容量为 10。

 2. 添加元素超过 10 个后会自动扩容。

 3. 删除一个元素后，size 会减 1，后面元素会自动向前移动一位。

 4. 插入一个新元素后，size 会加 1，后续元素后移一位。

 5. 删除到只有 0.25 * 容量 个元素后，会自动缩小容量。

 

本篇文章来源于微信公众号: i余数



微信扫描下方的二维码阅读本文

此作者没有提供个人介绍
最后更新于 2023-06-27
啥也没有呀