那个网站开发三味,设计接单的网站,wordpress建设下载网站,兰州装修公司排名前十数据结构#xff08;回顾#xff09;
回顾
不同点顺序表链表存储空间上物理上一定连续逻辑上连续#xff0c;物理上不一定连续随机访问支持#xff0c;时间复杂度O(1)不支持#xff0c;时间复杂度O(N)任意位置插入或者删除元素可能需要挪动元素#xff0c;效率低#…数据结构回顾
回顾
不同点顺序表链表存储空间上物理上一定连续逻辑上连续物理上不一定连续随机访问支持时间复杂度O(1)不支持时间复杂度O(N)任意位置插入或者删除元素可能需要挪动元素效率低时间复杂度O(N)只需要修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入删除频繁缓存利用率高低
缓存利用率
这里的缓存利用率给大家简单讲一下就是存储也是分结构的 然后顺序表由于它在存储的时候物理空间一定是连续的在高速缓存的时候会命中率更高。这个缓存其实大概就是我加载一个数据我连带着这个数据后面的数据也一起加载了后面被使用的时候直接用就好了不用重新加载一次。然后这个连着后面的数据一起加载是按照存储的物理空间连续的线性的来的。就好比如有一组数据12345现在要用1就加载了1系统考虑到你后面可能会用到后面的数据就把2345也给你加载缓存好了。这样后面你再去用这些数据的时候就会快很多。
但是链表就没有这个优点。为什么因为链表是逻辑上连续但是存储的时候物理空间是不连续的可能那边一个数据这边一个数据然后村门口一个数据山头一个数据。但是缓存不会管你连不连续它就只是帮你连续的加载好后面的数据后面的数据和你这个项目本身有没有关系不管你所以就涉及到了一个命中率的问题。
顺序表因为它是物理空间连续的所以缓存的时候缓存得到的数据就大部分都是和本项目本问题有关的所以命中率就高。就是缓存的后续数据和我的目标数据是否重合重合度越高那么命中率越高。链表反之。
对比
那么通过上面表格顺序表和链表的对比其实大家可以发现这两种数据结构其实有种互补的关系有没有。好比如顺序表适合干随机访问数据链表不适合顺序表不适合频繁的插入数据因为涉及到挪动数据问题但是链表合适。等等。
总结
还有我们后续用数组或者链表实现的栈和队列也是顺序表的一种不过操作比较特殊。那么大家也能察觉这类数据结构其实比较基础能具体解决的问题其实不算多。它们在结构中都是1对1的关系只有一个直接前驱或后继。但是等会讲到的树就不是这么简单的结构了已经开始是1对多了。说这么多都是为了让大家更明白我们前面学的大概是什么东西也为了和后续学的东西有个区别。
再总结
这里给大家做个比喻我们最开始学的数组就其实像是大米小麦。然后简单的操作一下把大米煮一下就变成了粥顺序表粥改良了一下有的人不爱喝粥那就变成米饭链表。如果有人手法精巧加上一些鸡蛋米饭就可以变成蛋炒饭队列粥放点猪肉就变成了猪肉粥栈。然后还有把米整成淀粉加点青菜加点猪肉玉米煮一下就变成了饺子哈希表、堆、树…。大概的意思就是后面的很多复杂结构都是基于前面的简单结构通过一些操作的改动或者再加上一些佐料就变成了复杂结构这样也可以更好的去解决更多问题。就是想让大家也有一个这样的理解。
