数组

在内存中开辟连续的内存空间，储存多个相同类型数据的结构，这就是数组的定义，通常用 Array表示，也称之为线性表。

比如说：创建了 int 类型的数组你就不能存 float 类型的数据， 也不能存 double 类型的数据。

int[] ints = new int[10];
ints[0] = 5;   //正确
ints[1] = 5.0; //报错，不能进行添加

表现形式

• （1）一维数组 ：int a[]，String a[]。

• （2）多维数组 ：int a[][]，int a[][][]。

优点

1、元素可以通过数组下标进行访问，访问速度快。

缺点

• 1、数组大小固定后无法进行扩容，不适合动态存储。
• 2、插入、删除元素速度慢，要移动数组其他元素。
• 3、在使用前要先申请内存的大小，会浪费内存空间。

自定义ArrayList

在 Java 中，使用到数组的典型容器就是 ArrayList！那现在小杰就带大家来写一个。对数组进行基本的增删改查。

基本属性

那这个MyArrayList里至少需要哪些属性呢？

• 1、存放数据的数组
• 2、记录数组中元素的个数

public class MyArrayList {

    //存放数据
    private String[] data;

    //元素个数
    private int size;
}

构造方法

再准备一个有参构造方法，可以初始化数组容量。

// initialCapacity 初始化数组容量
public MyArrayList(int initialCapacity){
    if (initialCapacity > 0) {
        this.data = new String[initialCapacity];
    } else if (initialCapacity == 0) {
        this.data = new String[0];
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    }
}

构造方法的代码很简单。

增删改查

然后就是基本的增删改查！

add(String e)

将元素添加到数组的末尾。

public void add(String e){
    //扩容
    grow();
    data[size] = e;
    size++;
}

private void grow() {
    int minCapacity = size + 1;
    //判断是否需要扩容
    if(minCapacity > data.length){
        //扩容两倍
        int newSize = minCapacity * 2;
        //需要进行扩容
        String[] temp =  new String[newSize];
        for (int i = 0; i < data.length; i++) {
            //将老数组的值赋值给新数组
            temp[i] = data[i];
        }
        //将扩容后的数组赋值给 data
        data = temp;
    }
}

如果需要进行扩容，可以发现效率就会慢下来了，时间复杂度变为了 O(n)，所以，如果能确认数组的大小，请给数组长度赋初始值。各位也可以将 grow() 方法进行注释，然后添加元素个数超过数组长度，看看会发生什么情况。

add(int index,String e)

指定下标添加元素！

public void add(int index,String e){
    //下标越界 指定下标添加元素的下标值不能大于 size。
    if (index > size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
    //扩容
    grow();
    //把 index 后的数据往后移一个
    for(int i = data.length - 1; i > index; i--){
            //将前一个元素赋值给后面一个元素
            data[i] = data[i - 1];
    }
    data[index] = e;
    size++;
}

指定下标添加元素，这个方法是比较复杂的，效率也是比较慢的。 可以看到上面有一个for遍历，需要在其中进行元素移动。看图理解理解。

remove(int index)

根据下标删除元素！

public void remove(int index){
    //下标越界 index >= size，下标从 0 开始的，肯定要比 size 小
    if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
    for(int i = index ; i < size ; i++){
            //将后一个元素赋值给前一个元素
            if(i != size - 1){
                    data[i] = data[i + 1];
            }else{
                    //直接将最后一个元素赋值为 null
                    data[i] = null;
            }
    }
    size--;
}

根据下标删除元素这个方法的效率也是比较慢的，跟add(int index,String e)方法是一致的，都有可能对元素进行移动。

update

修改指定下标元素值是很简单的。

public void update(Integer index,String e){
    //下标越界
    if (index > size || index < 0){
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
    data[index] = e;
}

get

获得指定下标元素也是很简单的。

public String get(Integer index){
    //下标越界
    if (index > size || index < 0){
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    }
    return data[index];
}

时间复杂度

下面总结一下上面各个方法的时间复杂度。

方法	时间复杂度
add(String e)	O(1)
add(int index,String e)	O(n)
remove(int index)	O(n)
update	O(1)
get	O(1)