?
?前言：
顺序表和链表，这两个结构各有优势，很难说谁更优。严格来说，他们两是相辅相成的两个结构。如果链表的各方面的结构都比顺序表优，我们还学个锤子顺序表呢？所以他们各有优缺点。你的缺点就是我的优点，这是一个互相弥补的状态。
一、优缺点分析
顺序表
优点：
① 支持随机访问（最大的优点）
需要随机访问结构的支持的算法可以很好的适用（排序，二分查找）哪怕顺序表有一百个缺点，只要有这一个优点！顺序表就有存在的意义。
② CPU高速缓存命中率更高（相比链表而言）
（下面会讲解，这个是比较底层的知识了，实在理解不了也没关系）
缺点：
① 头部或者中部插入删除时间复杂度效率低 O(N)
② 连续的物理空间，如果空间不够就需要增容
1. 增容有一定程度的消耗，比如现在有10个空间，你要增容2倍，你要开一个20个对象大小的空间，再把10个空间上的值拷贝下来再释放旧的空间，会消耗。
2. 为了避免频繁增容，我们一般都按倍数去增，用不完可能存在一定的空间浪费。
链表（双向带头循环链表）
优点：
① 任意位置插入删除效率高?O(1) ，前后一链接就可以了不需要挪动数据
② 按需申请释放空间， 在空间的利用上一点都不浪费和占用
缺点：
① 不支持随机访问
不能用下标访问，我想访问第 i 个，做不到。这就意味着有些算法不能用，比如一些排序，二分查找在这种结构上不适用。
② 链表存储一个值，同时要存储链接指针，也有一定的消耗
这是一个比较小的缺点了，因为就那几个指针占用不了多少内存。
③ CPU高速缓存命中率更低（相比顺序表而言）
（下面会讲解）
二、浅析CPU高速缓存
刚才说优缺点的时候，我们提到了CPU高速缓存命中率问题。这里我们将进行一个简单的讲解，讲解完后大家应该就能理解为什么顺序表的命中率较高，链表的命中率相对较低了。参考陈皓
0x00 存储器的层次结构
从单个计算机上来说，分为带电存储和不带电存储。如图所示，黄线以上的部分为带电存储，简单来说就是有电它才能存数据。
远程二级存储（分布式文件系统、Web服务器）：不带电存储
比如你把数据存到百度网盘上，就是远程存储。
本地二级存储（本地磁盘）：不带电存储
本地磁盘（local disk）是指安装于同一台计算机主板上，不可随意插拔、移动的磁盘（硬盘），一般包括计算机操作系统所在分区及其他分区。
主存（DRAM）：带电存储
主存储器（Main memory），简称主存。是计算机硬件的一个重要部件，其作用是存放指令和数据，并能由中央处理器（CPU）直接随机存取。
寄存器：带电存储
CPU速度快，会和寄存器交互。假设要计算 a + b。a 和 b 是存储在主存上的，如果 a 和 b 都比较小，会送到寄存器那里进行计算。寄存器一般很小，但是它的速度特别快。
0x01?举例讲解
?? 假设我们的 CPU 现在要分别遍历顺序表和链表。这里其实还涉及到虚拟内存和物理内存映射问题，既然是浅析，我们就谈谈较为简单的部分。
🔑 执行指令：分别遍历顺序表和链表
0x02 回到问题
这就是为什么链表的CPU高速缓存命中率相比顺序表而言低的原因！
顺序表的CPU高速缓存命中率更高（相比链表而言）
链表的CPU高速缓存命中率较低（相比顺序表而言）
三、总结
链表再好，也有他不适用的地方，有时候还是得用顺序表。就这一个缺点，就让链表直接芭比Q了。排序场景用的很多的（比如按价格，按热度）。
🔗 陈皓大佬的CPU缓存知识详解：与程序员相关的CPU缓存知识
参考资料：
陈皓. 与程序员相关的CPU缓存知识[J]. CoolShell, 2020/3/1.
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
📌 笔者：王亦优
📃 更新： 2021.11.16
? 勘误： 无
📜 声明： 由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！