数组存储结构(结构化数组)

微信公众号同步更新

欢迎和小白一起成长，985计算机硕士，有任何学习，保研等问题都可以公众号私信留言哦！

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

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

原始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("数组已满");
        }

增加动态扩容后的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 
图解
 
 
 
 
这就实现了一个简单的数组动态扩容的操作，但是和java自身的动态扩容比起来，还是存在很大一部分优化空间，这次先说到这里，下篇摸索一下java自身的动态扩容机制再来更新！