对比顺序表与链表——纵观与取舍

目录

• • 传统艺能😎
  • 正片开始🤣

传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库（打灰人 ）欢迎访问，点我！

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，背后烟火，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我

正片开始🤣

我们知道双向循环带头链表是链表8种结构中的扛把子，那看起来最low的顺序表，可不可以不要呢？
答案是不能，首先我们一个明白两种结构是相辅相成的

顺序表优点：
1.顺序表空间连续，方便用下标随机访问

可是成也萧何败也萧何，他的优点同时关联出他的缺点：

1.因为空间连续，空间不够就需要扩容，因为存在原地扩和异地扩，扩容本身存在一定消耗，而且扩容机制还存在一定空间浪费；
2.头部或者中部插入删除时，因为是连续存放要挪动数据，效率低下。O(N)；

链表优点：
1.链表空间不连续，可按需申请释放空间
2.任意位置插入删除效率高。O(N);

链表缺点：

1.链表因为空间不连续，不支持下标的随意访问，有些算法不适合在链表中应用，比如二分查找，排序等。

以上是我们之前知识承载下的总结，如果你还想让别人眼前一亮，那么顺序表还有一个优点：

CPU高速缓存命中率会更高（做了解），涉及到局部性原理，我们知道存储体系长这样：

其实平时我们口中的内存指的是电脑的主存，俗称的磁盘或者硬盘就是本地二级存储，软件的实时运行都依赖于内存，内存就是速度快而价格高，而磁盘正好相反。

当然你可能会问为什么不全部换成内存，首先是成本问题，其次内存是带电存储而硬盘是不带电存储，脑补一下写了一个代码，代码还在内存中还没写入硬盘，电脑突然被拔插头或者死机那下次数据就会消失，所以二者是配合着用。

我们电脑还存在一个三级缓存+寄存器（eax,ebx,ebp,esp),比如我们执行一个链表的打印数据在内存里面，会编译链接后生成可执行程序，CPU执行这个程序，CPU要去访问内存。CPU不会直接去访问内存，他嫌弃内存速度太慢，访问三级缓存和寄存器，4、8比特位小数据就放到寄存器，大数据就sei到缓存。

CPU会先看数据是否在缓存，如果在就叫命中，如果不在就叫不命中，先把数据从内存加载到缓存再访问。加载时又局限于局部，访问一个位置会连续加载出该位置之后的一段空间。假设一次加载20字节，5个字符，如果其中4或3处于缓存就叫做命中。

换作是链表，每次就算没有命中也要加载连续的一段空间进去，会带来一个更恶劣的影响叫缓存污染，无关内容被加载进缓存而把原有内容挤出内存，这就是顺序表CPU高速缓存命中率高的优势。

具体加载的这一段连续空间到底是多少取决于硬件。