---

05 数组

什么是数组

• 数组是线性表中的一种
• 数组使用连续的存储空间，存储一组相同类型的数据

数组的下标随机访问

通过寻址公式，计算出该元素存储的内存地址
a[i]_address = base_address + i * data_type_size

值得注意的是，数组的的内存地址分配是[0]在低位，[n-1]在高位。

低效的“插入”和“删除”与巧思

1. 插入操作

一般看来，插入元素到数组的第k位，要将数组k~n位后移。这样的平均时间复杂度是 $\frac{1+2+...+n}{n} \to O(n)$n1+2+...+n​→O(n)，因为在每个位置插入元素的概率是一样的。

• 一种巧妙的插入方法：
  直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。时间复杂度降为 $O(1)$O(1)。
  

2. 删除操作

在我之前看来，删除一个元素，就要把它后面的所有元素都向前挪，不然中间就会出现空洞，内存就不连续了。这样操作的平均情况时间复杂度也为 $O(n)$O(n)。

• 一种巧妙的删除方法：
  将多次删除操作集中在一起执行！每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，再触发执行一次真正的删除操作。此算法类似JVM的标记清除垃圾回收算法的核心思想。
  

注意访问越界问题

首先，我提醒自己平时写代码和刷题时要注意这些边界条件~

再来，看以下这段C语言代码。在C语言中，只要不是访问受限的内存，所有的内存空间都是可以*访问的。数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。当然，其它语言就可能会报错。

用图来解释以上代码的死循环，就是程序内存分布问题，这里i和a为局部变量，被储存在栈区，栈区是从高地址往地址值扩展的。

附操作系统笔记，程序内存分布：

容器 VS 数组

针对数组类型，很多语言都提供了容器类，如 Java 中的 ArrayList、C++ STL 中的 vector。

容器的优点：

• 将很多数组操作的细节封装起来，如数组插入、删除数据时需要搬移其他数据等
• 支持动态扩容，每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小

注意，对于扩容大小，gcc是2倍，VS是1.5倍。两者的区别是，2倍扩容时间复杂度更优，可以保证时间复杂度 $O(n)$O(n) ，而1.5倍扩容时，空间可重用。

参考：
c++STL vector扩容过程
当面试官问我们vector扩容机制时，他想问什么？

06