我们在说「数组」的时候有多种不同的语境，因为不同的编程语言提供的数组类型和 API 是不一样的，所以开头先统一一下说辞：可以把「数组」分为两大类，一类是「静态数组」，一类是「动态数组」。

• 「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。
• 「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。

有了动态数组，后面讲到的队列、栈、哈希表等复杂数据结构都会依赖它进行实现。

静态数组

静态数组在创建的时候就要确定数组的元素类型和元素数量。只有在 C++、Java、Golang 这类语言中才提供了创建静态数组的方式，类似 Python、JavaScript 这类语言并没有提供静态数组的定义方式。

静态数组的用法比较原始，实际软件开发中很少用到，写算法题也没必要用，我们一般直接用动态数组。

定义一个静态数组的方法如下：

// 定义一个大小为 10 的静态数组
int arr[10];

// 用 memset 函数把数组的值初始化为 0
memset(arr, 0, sizeof(arr));

// 使用索引赋值
arr[0] = 1;

// 使用索引取值
int a = arr[0];

用 memset 将数组元素初始化为 0 是 C/CPP 的特有操作。
因为在 C/CPP 中，申请静态数组的语句（即 int arr[10] ）只是请操作系统在内存中开辟了一块连续的内存空间，你也不知道这块空间是谁使用过的二手内存，你也不知道里面存了什么奇奇怪怪的东西。所以一般我们会用 memset 函数把这块内存空间的值初始化一下再使用。

其他比如 Java Golang ，静态数组创建出来后会自动帮你把元素值都初始化为 0，所以不需要再显式进行初始化。

动态数组

动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已。

因此，动态数组也不能解决静态数组在中间增删元素时效率差的问题。数组随机访问的超能力源于数组连续的内存空间，而连续的内存空间就不可避免地面对数据搬移和扩缩容的问题。

// java 中创建动态数组不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
// ArrayList 很熟悉了，即可重复的集合，底层是静态数组
ArrayList<Integer> arr = new ArrayList<>();

for (int i = 0; i < 10; i++) {
    // 在末尾追加元素，时间复杂度 O(1)
    arr.add(i);
}

// 在中间插入元素，时间复杂度 O(N)
// 在索引 2 的位置插入元素 666
arr.add(2, 666);

// 在头部插入元素，时间复杂度 O(N)
arr.add(0, -1);

// 删除末尾元素，时间复杂度 O(1)
arr.remove(arr.size() - 1);

// 删除中间元素，时间复杂度 O(N)
// 删除索引 2 的元素
arr.remove(2);

// 根据索引查询元素，时间复杂度 O(1)
int a = arr.get(0);

// 根据索引修改元素，时间复杂度 O(1)
arr.set(0, 100);

// 根据元素值查找索引，时间复杂度 O(N)
int index = arr.indexOf(666);

实现动态数组

手写实现动态数组有这几个关键点：

• 自动扩缩容
  • 在实际使用动态数组时，缩容也是重要的优化手段。比方说一个动态数组开辟了能够存储 1000 个元素的连续内存空间，但是实际只存了 10 个元素，那就有 990 个空间是空闲的。为了避免资源浪费，我们其实可以适当缩小存储空间，这就是缩容。扩容和缩容采用的门限值可以自定义，例如：
    • 当数组元素个数达到底层静态数组的容量上限时，扩容为原来的 2 倍；
    • 当数组元素个数缩减到底层静态数组的容量的 1/4 时，缩容为原来的 1/2。
• 索引越界的检查
  • 自然的，在删/改/查中，都有一件共同要做的事：检查下标是否越界，因此，可以将检查下标越界这个行为，再次提取出作为一个公共方法。增很特殊，由于增是可以放到任意一个位置的，因此不应检查其下标是否越界

 public E remove(int index) {
        // 检查索引越界
        checkElementIndex(index);
        ...
        }

• 删除元素谨防内存泄漏
  • 单从算法的角度，其实并不需要关心被删掉的元素应该如何处理，但是具体到代码实现，我们需要注意可能出现的内存泄漏。给出的代码实现中，删除元素时，我都会把被删除的元素置为 null，

// 删最后一个元素
public E removeLast() {
    E deletedVal = data[size - 1];
    // 删除最后一个元素
    // 必须给最后一个元素置为 null，否则会内存泄漏
    data[size - 1] = null;
    size--;

    return deletedVal;
}

Java 的垃圾回收机制是基于 图算法 的可达性分析，如果一个对象再也无法被访问到，那么这个对象占用的内存才会被释放；否则，垃圾回收器会认为这个对象还在使用中，就不会释放这个对象占用的内存。

如果你不执行 data[size - 1] = null 这行代码，那么 data[size - 1] 这个引用就会一直存在，你可以通过 data[size - 1] 访问这个对象，所以这个对象被认为是可达的，它的内存就一直不会被释放，进而造成内存泄漏。