准备弄一个算法面试题系列。列举下面试中常问的一些问题。
一、链表和数组的区别是什么？插入和查询的时间复杂度分别是多少？
1、从逻辑结构上来说，
这两种数据结构都属于线性表。
线性表，就是所有数据都排列在只有一个维度的“线”上，就像羊肉串一样，把数据串成一串。对其中任意一个节点来说，除了头尾，只有一个前趋，也只有一个后继。
2、在内存中，
数组占用的是一块连续的内存区，而链表在内存中，是分散的。
数组，与生俱来具有“线性”的成分。
而链表比数组多了一个“串起来”的额外操作，这个操作就是加了个指向下个节点的指针。
数组在物理内存上是连续存储的，硬件上支持“随机访问”，也就是你访问一个a[3]的元素与访问一个a[10000]，使用数组下标访问时，这两个元素的时间消耗是一样的。
但是链表也没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，因为下个节点的位置信息只能通过上个节点知道（这里只考虑单向链表），所以访链表中的List(3)与List(10000)，时间就不一样了，访问List(3)，只要通过前两个节点，但要想访问List(10000)，不得不通过前面的9999个节点。
数组是一下子就跳到了a[10000]，无需逐个访问a[10000]之前的这些个元素。所以对于访问，数组和链表时间复杂度分别是O(1)与O(n)，方式一种是“随机访问”，一种是“顺序访问”。
3、插入：
数组在内存中是连续存储的，要想在某个节点之前增加，必须要把此节点后的元素依次后移。
链表只需要改变节点中的“指针”，就可以。自身在内存中所占据的位置不变，只是这个节点所占据的这块内存中数据（指针）改变了，
比如 A->B->C 变成A-A2->B->C。只是A的指针本来指向B，变成指向A2，然后A2的指针指向B，就可以。
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
4、操作系统内存预读：
内存管理会将连续的存储空间提前读入缓存，所以数组往往会被都读入到缓存中，而链表由于在内存中分布是分散的，往往不会都读入到缓存中，这样本来访问效率就低，这样效率反而更低了。
在实际中，因为链表带来的动态扩容的便利性，在做为算法的容器方面，用的更普遍一点。
5、总结：
数组：
在内存中，数组是一块连续的区域。
数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。
随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
不利于扩展，数组定义的空间不够时要重新定义数组。
链表：
内存中可以存在任何地方，不要求连续。
每一个数据都保存了下一个数据的内存地址。
增加数据和删除数据很容易。
查找数据时效率低。
不指定大小，扩展方便。链表大小不用定义，数据随意增删。
6、优缺点对比
数组的优点
随机访问性强
查找速度快
数组的缺点
插入和删除效率低
可能浪费内存
内存空间要求高，必须有足够的连续内存空间。
数组大小固定，不能动态拓展
链表的优点
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。
学习很辛苦也很幸福，最后来张美图。为了让大家好好学习，我容易吗。。。。。
