常见数据结构-数组

一，如何实现随机访问？

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。数组的两个特点是：

• 线性表
• 连续的内存空间和相同类型的数据（随机访问）

计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size
// 如果数组从 1 开始计数
a[k]_address = base_address + (k-1)*type_size
复制代码

数组从 1 开始编号，是因为根据寻址公式，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

注意：数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)O(1)O(1)，但找的时间复杂度并不为 O(1)O(1)O(1)。，毕竟即便是排好序的数组，用二分查找，时间复杂度也是 O(logn)O(logn)O(logn)。

这点很多博客没有注明。

二，低效的“插入”和“删除”

假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。平均情况时间复杂度为 (1+2+...n)/n=O(n)(1+2+...n)/n=O(n)(1+2+...n)/n=O(n)。

三，容器能否完全替代数组？

C++、JAVA 等语言都提供了类似数组的容器类，比如 C++STL 中的 vector。根据我的经验，一般情况下，推荐用容器开发，简单省事、代码易懂，底层和高性能开发用数组，毕竟容器的灵活性还是牺牲了一定性能的。

参考资料

《数据结构与算法之美》