数据结构（回顾）

数据结构（回顾）

回顾

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，物理上不一定连续
随机访问	支持，时间复杂度O(1)	不支持，时间复杂度O(N)
任意位置插入或者删除元素	可能需要挪动元素，效率低，时间复杂度O(N)	只需要修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入删除频繁
缓存利用率	高	低

缓存利用率

这里的缓存利用率给大家简单讲一下就是存储也是分结构的：

然后顺序表由于它在存储的时候物理空间一定是连续的，在高速缓存的时候会命中率更高。这个缓存其实大概就是我加载一个数据，我连带着这个数据后面的数据也一起加载了，后面被使用的时候直接用就好了，不用重新加载一次。然后这个连着后面的数据一起加载是按照存储的物理空间连续的，线性的来的。就好比如有一组数据12345，现在要用1就加载了1，系统考虑到你后面可能会用到后面的数据，就把2345也给你加载缓存好了。这样后面你再去用这些数据的时候就会快很多。

但是链表就没有这个优点。为什么？因为链表是逻辑上连续，但是存储的时候物理空间是不连续的，可能那边一个数据，这边一个数据，然后村门口一个数据，山头一个数据。但是缓存不会管你连不连续，它就只是帮你连续的加载好后面的数据，后面的数据和你这个项目本身有没有关系，不管你，所以就涉及到了一个命中率的问题。

顺序表因为它是物理空间连续的，所以缓存的时候，缓存得到的数据就大部分都是和本项目，本问题有关的，所以命中率就高。就是缓存的后续数据和我的目标数据是否重合，重合度越高，那么命中率越高。链表反之。

对比

那么通过上面表格顺序表和链表的对比，其实大家可以发现，这两种数据结构其实有种互补的关系，有没有。好比如，顺序表适合干随机访问数据，链表不适合，顺序表不适合频繁的插入数据（因为涉及到挪动数据问题），但是链表合适。等等。

总结

还有我们后续用数组或者链表实现的栈和队列，也是顺序表的一种，不过操作比较特殊。那么大家也能察觉，这类数据结构其实比较基础，能具体解决的问题其实不算多。它们在结构中都是1对1的关系，只有一个直接前驱或后继。但是等会讲到的树，就不是这么简单的结构了，已经开始是1对多了。说这么多，都是为了让大家更明白我们前面学的大概是什么东西，也为了和后续学的东西有个区别。

再总结

这里给大家做个比喻，我们最开始学的数组，就其实像是大米，小麦。然后简单的操作一下，把大米煮一下就变成了粥（顺序表），粥改良了一下，有的人不爱喝粥，那就变成米饭（链表）。如果有人手法精巧，加上一些鸡蛋，米饭就可以变成蛋炒饭（队列），粥放点猪肉，就变成了猪肉粥（栈）。然后还有把米整成淀粉，加点青菜，加点猪肉，玉米煮一下就变成了饺子（哈希表、堆、树…）。大概的意思就是后面的很多复杂结构都是基于前面的简单结构，通过一些操作的改动，或者再加上一些佐料，就变成了复杂结构，这样也可以更好的去解决更多问题。就是想让大家也有一个这样的理解。