- 定义：
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储具有相同类型的数据。
- 线性表：
数据排列成一条线一样的结构。每个线性表上的数据最多只有前和后两个方法。除数组外，数据结构：链表、数据结构：队列、数据结构：栈等也是线性表数据结构。
- 非线性表：
有除了前和后，还有其它关系，如树、堆、图等
- 连续的存储空间和相同类型的数据
- 优势：根据数组下标随机访问数组元素，时间复杂度仅为 O(1)
由于在计算机内存中，会给数组中每一个元素，都给一个连续的内存空间。计算机只要借助寻址公式，就能找到对应元素的内存地址。
a[i]_address = base_address + i * data_type_size
- 劣势：为了保证连续性，在数组中插入、删除一个数据，要做大量的数据搬移工作
- 插入操作：假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。
- 最好情况时间复杂度：在末尾插入，复杂度为 O(1)
- 最坏情况时间复杂度：在开头插入，复杂度为 O(n)
- 平均情况时间复杂度：插入任意一个位置的概率是一致的，复杂度为 (1+2+…n)/n = O(n)
- 优化点：如果数组是无序的，可以直接把第 k 个元素放到数组最后，然后在第 k 位放新元素，这样复杂度就只会是 O(1)
- 删除操作：假设数组的长度为 n，现在，如果我们需要删除第 k 个位置的元素
- 最好情况时间复杂度：在开头删除，复杂度为 O(1)
- 最坏情况时间复杂度：在末尾删除，复杂度为 O(n)
- 平均情况时间复杂度：删除任意一个位置的概率是一致的，复杂度为 (1+2+…n)/n = O(n)
- 优化点：假设数组是 a[10]，包含 8 个元素：a, b, c, d, e, f, g, h，我们要依次删除 a, b, c 三个元素，为了避免d, e, f, g, h 在内存地址中被搬移三次，我们可以先把要删除的数据做一个标记 ，只有当数组没有更多空间存储数据时，我们再触发一次真正的删除操作。这个是JVM 标记清除垃圾回收算法的核心思想。