Java如何自定义一个变长数组？

Love The Way You Lie 2024-03-30 12:55 83阅读 0赞

#### 文章目录 ####

*   *  思路分析
     *  实现代码
     *  测试结果

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

### 思路分析 ###

**主要功能点：**

1.  新建时可以指定容量大小，不指定时使用默认容量大小。
2.  向数组中追加新元素，当超过容量时应该自动扩容。
3.  向数组中指定位置添加新元素，需要考虑指定的下标是否越界，同样也需要考虑扩容操作。
4.  删除末尾的元素，需要考虑缩小容量。
5.  删除指定位置元素，需要考虑指定的下标是否越界，同样也需要考虑缩小容量。
6.  修改特定位置的元素，需要考虑指定的下标是否越界。
7.  以时间复杂度为 O ( 1 ) O(1) 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个元素是: %d\n", 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个元素是: %d\n", 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个元素是: %d\n", 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个元素是: %d\n", resizeableArray.get(4));
    
        }
       
    }

### 测试结果 ###

由执行结果可知：

1.  初始化后默认容量为`10`。
2.  添加元素超过`10`个后会自动扩容。
3.  删除一个元素后，`size`会减`1`，后面元素会自动向前移动一位。
4.  插入一个新元素后，`size`会加`1`，后续元素后移一位。
5.  删除到只有`0.25 * 容量`个元素后，会自动缩小容量。

![Java如何自定义一个变长数组？][Java]

[Java]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b20b5958c925483b8af6aad7aff7a538.png