数组，链表

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

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

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

数组和链表的优缺点：
数组
使用方便，，查询效率比链表高，内存为一连续的区域
缺点：大小固定，不适合动态存储，不方便动态添加。
链表
优点：可动态添加删除，大小可变，内存可能是不连续内存，链式存储。
缺点：只能通过顺次指针访问，查询效率低。

访问：
数组可以随机访问其中的元素，链表则必须是顺序访问，不能随机访问
链表可以随意扩大，数组不能

处理速度由快到慢排序：
CPU寄存器 -> 缓存 -> 内存 ->硬盘

• CPU 寄存器 – immediate access (0-1个CPU时钟周期)
• CPU L1 缓存 – fast access (3个CPU时钟周期)
• CPU L2 缓存 – slightly slower access (10个CPU时钟周期)
• 内存 (RAM) – slow access (100个CPU时钟周期)
• 硬盘 (file system) – very slow (10,000,000个CPU时钟周期)

各级别的存储器速度差异非常大，CPU寄存器速度是内存速度的100倍，这就是为什么CPU产商发明了CPU缓存。而这个CPU缓存，就是数组和链表区别的关键所在。

总结
CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，平均读取 每个元素的时间只要3个CPU时钟时间。而链表的节点分散在堆空间里面，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。 这样算下来，数组访问的速度比链表快33倍！

而数组大小固定，插入和删除都需要移动元素，链表可以动态扩充，插入删除不需要移动元素，只需要更改元素中的指针。所以链表的插入删除比数组效率高。

查询比数组快，删除插入效率又高的方式就是散列存储，hash