动态数组

1. 动态数组是什么？
2. 动态数组的使用和扩容。
3. 动态数组的扩容与时间复杂度分析

数组VS动态数组

​ 数组就是一开始有固定长度的，而动态数组和数组不同的事情就是多了一个扩容的功能。

​ 以java中的ArrayList为例子假设一开始ArrayList数组一开始长度为3，可是你往里面加入了4个数字，刚开始加入3个数字的时候没有问题，当开始加入第四个数的时候，ArrayList始自动新建一个长度为原来长度的2倍的数组，即现在数组长度为6，然后将旧数组的数放入到新数组中，继续将剩下的数放入到新数组中，后将老的数组全部销毁掉。

问题：那么动态数组的扩容的一系列操作会影响他的时间复杂度吗？

​ 假设一开始动态数组长度为1（以最差的情况来看），让后往里面放入N个数过程如下：

一开始是长度为1然后扩容为2为4,8,16一直到N而每一次扩容后放入数据的操作都是O（1）

所以整体来说一共进行了1+2+4+8+16+…+N次是一个等比数列也就是说时间复杂度是O（N）

加入所有数据的时间复杂度是O（N）但是加入一个数的时间复杂度是O（1），因为一共是N均摊一下就是1了，所以动态数组和数组的时间复杂度来说差别不大只是常数的差别，也就是说动态数组只是比数组慢了常数级别的时间多了自动扩容这个方法。

代码实现

import java.util.ArrayList;

/**
 * @Auther: ouyy
 * @Date: 2023/5/7 - 05 - 07 - 12:13
 * @Description: class01
 * @version: 1.0
 */


class MyArrayList {
    private int size = 0;//数组的有效元素个数
    private int capacity = 10;//初始容量
    private int[] array = new int[capacity];//空数组

    //加入到最后方法
    public void addLast(int element) {
        //扩容检查
        if(size==capacity){
            //开始扩容
            capacity = capacity * 2;
            int[] newArray = new int[capacity];
            System.arraycopy(array,0,newArray,0,size);
            array = newArray;
        }
        array[size] = element;
        size++;
    }

    //某一个位置加入
    public void add(int index, int element) {
        //扩容检查
        if(size==capacity){
            //开始扩容
            capacity = capacity * 2;
            int[] newArray = new int[capacity];
            System.arraycopy(array,0,newArray,0,size);
            array = newArray;
        }


        if (index >= 0 && index < size) {
            //使用这个方法来拷贝数组，参数1：数组，2：从哪开始，3：目标数组，4：目标数组起始位置，5：拷贝几个元素
            System.arraycopy(array, index, array, index + 1, size - index);
            array[index] = element;
            size++;
        }
    }

    //返回数组元素
    public int get(int index) {
        return array[index];
    }

}

public class Code09_DynamicArray {
    /*
    其实程序里面已经有了ArrayList的实现方法已经准备好了，可以直接利用
    但是为了更好地理解动态数组我们直接实现ArrayList的基础应用
    */
    //这是一个main方法，是程序的入口：
    public static void main(String[] args) {
        ArrayList arr = new ArrayList();
        MyArrayList arr2 = new MyArrayList();
        arr2.addLast(1);
        arr2.addLast(2);
        arr2.addLast(3);
        arr2.addLast(4);
        for (int i = 0; i < 4; i++) {
            System.out.println(arr2.get(i));
        }
    }
}