为什么数组查询比链表要快？而插入删除比链表效率低

问：为什么数组查询比链表要快？而插入删除比链表效率低

已知：

1、数据存储结构分为顺序存储、链接存储、索引存储、散列存储。
2、数组属于顺序存储，用一段连续的内存位置来存储。
3、链表属于链接存储，用一组任意的存储单元来存储，不要求物理上相邻。

抽象：

1、顺序存储可以想象成吃饭排队，每个人领的号都是按顺序来的，服务员只要喊号就里立即可以找到对应的人，新来的人都自动加到队尾，如果有人想插队，那么从他插队的位置后面所有的人都要挪动位置。
2、链接存储可以想象成手拉手做游戏，每个人只知道自己手拉的是谁，想要找到某个人必须从一个节点开始往一个方向按顺序一个一个查，直到查到这个人，新来的人可以插到任意两个人之间，只要原来的那两个人把手放开，和新来的拉起手即可，不需要其他人都跟着挪动。

查询涉及到CPU特性

处理速度由快到慢排序：
1、CPU寄存器
2、CPUL1缓存
3、CPUL2缓存
4、内存
5、硬盘

总结：

因为CPU缓存会读入一段连续的内存，顺序存储符合连续的内存，所以顺序存储可以被缓存处理，而链接存储并不是连续的，分散在堆中，所以只能内存去处理。
所以数组查询比链表要快。
而数组大小固定，插入和删除都需要移动元素，链表可以动态扩充，插入删除不需要移动元素，只需要更改元素中的指针。所以链表的插入删除比数组效率高。

多说一句：查询比数组快，删除插入效率又高的方式就是散列存储，散列是什么？散列的英文：hash