数据结构基础-数组动态扩容版[JAVA]

小半 • 2022年8月1日下午9:43 • 后端开发 • 阅读 240

1数组实现–动态扩容版

上篇文章数据结构基础-数组实现[JAVA]介绍了数组的构建，数组容量是静态的：即初始化的容量满了之后，不能增加数组容量，但JAVA中的数组ArrayList是支持动态扩容的，为了了解动态扩容机制，我们先简单实现一个动态扩容版的数组体验一下。

2动态扩容策略

当数组达到数组最大容量时，进行数组的扩容，即扩大数组的最大容量，这个事件发生在添加元素的函数里。

1. 原始add(index,element)函数如下

public void add(int index,int element){
        //如果size等于capacity，则说明数组已满
        if (size==arr.length){
            throw new IllegalArgumentException("数组已满");
        }
//        判断访问下标是否超出范围
        if (index<0||index>size){
            throw new IllegalArgumentException("超过下标");
        }
//        将index所在的元素及index后面的元素后移
        for (int i = size-1;i>=index;i--){
            arr[i+1]=arr[i];
        }
//        设置新元素
        arr[index] = element;
        this.size+=1;
        }

就发生在下面这段代码中，原始的add函数，判断size等于Capacity(arr.length)时，直接抛出异常，现在要动态扩容的话，就应该从这里下手。

if (size==arr.length){
            throw new IllegalArgumentException("数组已满");
        }

2. 增加动态扩容后的add函数

 public void add_v2(int index,int element){
        //如果size等于capacity，则说明数组已满
        if (size==arr.length){
            resize();
        }
//        判断访问下标是否超出范围
        if (index<0||index>size){
            throw new IllegalArgumentException("超过下标");
        }
//        将index所在的元素及index后面的元素后移
        for (int i = size-1;i>=index;i--){
            arr[i+1]=arr[i];
        }
//        设置新元素
        arr[index] = element;
        this.size+=1;
    }

当size等于capacity时，调用resize()函数进行动态扩容。

3.resize()函数内部机制

private void resize() {
//        创建一个capacity为2倍的arr.length，即为原始capacity的2倍
        int[] arr2 = new int[arr.length*2];
//        将原始数组中的数据copy到新数组arr2中
        for (int i=0;i<arr.length;i++){
            arr2[i]=arr[i];
        }
//        将arr2更新到arr中，达到arr数组扩容的目的
        arr=arr2;
    }