数组

专业定义：数组是一种线性的数据结构，用一组连续的内存空间来存储相同类型的数据。

线性指的是数据排列成像线一样的结构，只有向前或向后两个方向，同是线性的数据结构还有链表，栈，队列等。相对来说非线性的数据结构就比如树，图，堆等。

我们知道，数组是支持随机访问的。比如说我们想得到 a[5] 的数据，直接就能够定位到这个位置，而不用从a[0] 开始一个一个的向后找。能够支持这个特性，正是因为数组是在连续内存空间且数据类型相同。

不过数组也有个弊端，创建时必须指定大小且不支持扩容。在Java中为我们提供了ArrayList来解决这个问题。

不管学习什么，最好的方式就是站在设计者的角度来思考为什么要这么设计。那么，为了检验我们是不是真的掌握了这种数据结构，我们来自己实现一个支持动态扩展的工具类。

public class Array<E> {

    private Object[] data; // 用于存储数据的数组
    private int size; // data中元素的个数
    // 无参构造方法，默认容量为10
    public Array() {
        this(10);
    }

    public Array(int initCapacity) {
        this.data = new Object[initCapacity];
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    // 获取当前数组的容量
    public int getCapacity() {
        return data.length;
    }
}

首先列出的是类的结构和几个基本的方法。那么接下来我们还需要哪些方法呢？比如，add、get、set、remove、contains、find、resize。

我们先看扩容方法resize()

private void resize(int newCapacity) {
    Object[] newData = new Object[newCapacity]; // 创建一个新的数组，容量为方法传入的参数
    for (int i = 0; i < size; i++) {
        newData[i] = data[i];
    }
    data = newData; // data 指向新的数组
}

添加方法 add()

// 在数组的最后位置添加数据 e
public void add(E e) {
    add(e, size);
}
// 在指定的位置 index 添加数据 e
public void add(E e, int index) {
    // 判断 index 是否合法
    if (index < 0 || index > size)
        throw new IllegalArgumentException("illegal index: " + index);
    // 考虑扩容，在添加此数据前，当前数组已经满了，则需要扩容，当前容量 * 2
    if (size == data.length - 1)
        resize(data.length * 2);
    for (int i = size; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = e;
    size++; // 记得维护size
}

get()、set()、find()、contains()

// 获取下标为 index 的值
public E get(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("illegal index: " + index);
    return (E) data[index];
}
// 修改下标为 index 的值
public void set(E e, int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("illegal index: " + index);
    data[index] = e;
}
// 找到元素 e 所在的位置
public int find(E e) {
    for (int i = 0; i < size; i++) {
        if (e.equals(data[i]))
            return i;
    }
    return -1;
}
// 判断元素 e 是否存在
public boolean contains(E e) {
    return !(find(e) == -1);
}

删除方法 remove()

// 删除指定元素 e
public void remove(E e) {
    int index = find(e); // 首先判断元素 e 是否存在
    if (index != -1)
        remove(index);
}
// 删除下标为 index 的元素
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("illegal index: " + index);
    E delData = (E) data[index]; // 记录删除的元素
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];
    }
    size--;
    data[size] == null;
    if (size <= data.length / 4 && data.length / 2 != 0) // ？
        resize(data.length / 2);
    return delData;
}

我们来重点关注一下 ? 处的代码。当我们一直删除元素的时候，到了某一个临界值的话，我们会“缩容”来避免内存空间的浪费，那么临界值是什么呢？我们看图

那么，图中的情况，我们要不要“缩容”呢？显然是不可以的。因为如果“缩容之后”，那么一旦有添加操作，又会触发扩容，这样是很消耗性能的。那么，临界值是多少呢？如下图所示

以上就是我们自己实现的支持动态扩容的数组。

动态数组的扩容是很消耗性能的，在某种场景下还会触发OOM，比如我们的内存空间是20M，有一个动态数组的大小是10M，此时向动态数组中再添加一个元素，就会触发扩容。此时会创建一个新的数组，大小为20M，但这时内存空间只剩了10M，所以就会触发OOM。

在Java中，不只是ArrayList，还有很多支持动态扩容的数据结构。所以为了避免频繁的扩容操作，在能估算出数据个数的情况下，在构造对象的时候，尽量指定初始化大小。

其实，对于数组的删除操作，在某些情况下，我们还可以换一种实现的思路。比如，当我们要删除其中的一个数据时，只是给这个数据添加一个特殊的标记，等到某一个特殊的时刻（比如数组空间满）触发一次删除操作，这样的话，效率会比单个删除要高，因为每次删除都要遍历并移动数组中的元素。想一想，这种思路是不是有点熟悉？在JVM的GC算法中，标记清除或者标记整理是不是跟这个思路很像。