# 数据结构和算法

# 为啥数组会比链表快

• 数据存储结构分为顺序存储、链接存储、索引存储、散列存储。
• 数组属于顺序存储，用一段连续的内存位置来存储。
• 链表属于链接存储，用一组任意的存储单元来存储，不要求物理上相邻。
• 因为CPU缓存会读入一段连续的内存，顺序存储符合连续的内存，所以顺序存储可以被缓存处理，而链接存储并不是连续的，分散在堆中，所以只能内存去处理。 所以数组查询比链表要快。 而数组大小固定，插入和删除都需要移动元素，链表可以动态扩充，插入删除不需要移动元素，只需要更改元素中的指针。所以链表的插入删除比数组效率高。
• 1、顺序存储可以想象成吃饭排队，每个人领的号都是按顺序来的，服务员只要喊号就里立即可以找到对应的人，新来的人都自动加到队尾，如果有人想插队，那么从他插队的位置后面所有的人都要挪动位置。 2、链接存储可以想象成手拉手做游戏，每个人只知道自己手拉的是谁，想要找到某个人必须从一个节点开始往一个方向按顺序一个一个查，直到查到这个人，新来的人可以插到任意两个人之间，只要原来的那两个人把手放开，和新来的拉起手即可，不需要其他人都跟着挪动。