线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。

非线性表

在非线性表中，数据之间并不是简单的前后关系。

数组

用一组连续的内存空间，来存储一组具有相同类型的数据

数组支持随机访问原因分析

• 数组是线性表结构，数据成一条线；
• 连续的内存空间和相同类型的数据；

具体实现

• 一维数组寻址 其中，内存的首地址为base_address=1000； 当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址： c a[i]_address = base_address + i * data_type_size
• 二维数组寻址 对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为： c address = base_address + ( i * n + j) * type_size
• 三维数组寻址 对于 m * n * q 的数组，a [ i ][ j ][k] (i < m,j < n,k < q)的地址为： c address = base_address + ( i * n * q + j * q + k) * type_size

常见误区

链表适合插入、删除，时间复杂度 O(1)；数组适合查找，查找时间复杂度为 O(1)。 表述不准确，数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，用二分查找，时间复杂度也是 O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

低效的插入与删除

插入

假设数组的长度为 n，现在需要将一个数据插入到数组中的第 k 个位置 - 如果数组中的数据是有序的，如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)。 因为在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+...n)/n=O(n)。 - 如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。

删除

删除第 k 个位置的数据 - 为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n) - 在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢，比如数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。 为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。（大意就是，每次都不删除，最后一次性删除，删除后也没有将后面的元素移动到前面，这样就会导致删除的位置是空的，也就会造成不连续的储存空间）这与JVM标记清除算法的原理非常相似。 - JVM标记清除算法 大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。其缺点表现在： 1. 标记和清除的效率不高，只有在少量垃圾产生的时候较为高效。 2. 会产生不连续的内存空间碎片。（可以将存活的对象像一端倾斜，直接清理掉边界以外的内存）

警惕数组访问越界

c int main(int argc, char* argv[]){ int i = 0; int arr[3] = {0}; for(; i<=3; i++){ arr[i] = 0; printf("hello world\n"); } return 0;//无限打印hello world 栈是向下增长的，首先压栈的i，a[2]，a[1]，a[0]，这是我在我vc上调试查看汇编的时候看到的压栈顺序。相当于访问a[3]的时候，是在访问i变量，而此时i变量的地址是数组当前进程的，所以进行修改的时候，操作系统并不会终止进程。

对于数组访问越界造成无限循环，对于不同的编译器，在内存分配时，会按照内存地址递增或递减的方式进行分配。如果是内存地址递减的方式，就会造成无限循环。

访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。

很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。

数组的缺陷

• 需要预先指定大小，因为需要分配连续的内存空间
• 申请了10的空间，需要存储第11个数据时，就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

为什么数组的下标是从0开始而不是1呢？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式： c a[k]_address = base_address + k * type_size 如果从1开始，那计算数组元素 a[k]的内存地址就会变为 c a[k]_address = base_address + (k-1) * type_size 这样每次随机访问就会多了一道减法的运算，对于CPU来说也就多了一道指令。但这可能不是主要原因，还有一些其他原因，比如历史原因等。

资料来源

https://time.geekbang.org/column/article/40961