数据结构与算法之美学习总结数组

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

1.线性表

线性表就是数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。常见的线性表结构：数组、栈、链表、队列等。

2. 数组具有连续的内存空间和相同类型的数据

优点：连续的内存空间和相同类型的数据使得数组具有随机访问的特性。

缺点：数组在删除，插入数据时效率低下下。

3、数组怎么根据下标随机访问的？

通过寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

4、为什么数组插入和删除低效？

插入：

若有一元素想往int[n]的第k个位置插入数据，需要把k~n这部分数据的位置往后移。

最好情况时间复杂度 O(1)。

最坏情况时间复杂度为O(n)。

平均时间复杂度为O(n)。

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。这样时间复杂度就将为 O（1）了。

删除：

跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为O(n)。实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。

最好情况时间复杂度 O(1)。

最坏情况时间复杂度为O(n)。

平均时间复杂度为O(n)。

提高效率：将多次删除操作中集中在一起执行，可以先记录已经删除的数据，但是不进行数据迁移，而仅仅是记录，当发现没有更多空间存储时，再执行真正的删除操作。这也是 JVM 标记清除垃圾回收算法的核心思想。

5、数组访问越界问题

C语言中的数据越界是一种未决行为，并没有规定数组访问越界时编译器应该如何处理，因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。相比之下，Java会有越界检查。

6、容器能否完全替代数组？

数组先指定了空间大小； 容器可以动态扩容，需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。

什么情况下选择数组：

a.希望存储基本类型数据，可以用数组。

b.事先知道数据大小，并且操作简单，可以用数组。

c.直观表示多维，可以用数组。

d.业务开发，使用容器足够；开发框架，追求性能，首先数组。

7、为什么数组要从 0 开始编号？

由于数组是通过寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

如果数组是从 1 开始计数，那么就会变成：

a[i]_address = base_address + （i-1）* data_type_size

对于CPU来说，多了一次减法的指令。

当然，还有一定的历史原因