【数据结构】链表与顺序表的比较

不同点：

顺序表和链表是两种常见的数据结构，他们的不同点在于存储方式和插入、删除操作、随机访问、cpu缓存利用率等方面。

一、存储方式不同:

顺序表：

顺序表的存储方式是顺序存储，在内存中申请一块连续的空间，通过下标来进行存储；

链表：

链表的存储方式是链式存储，申请的空间是未必连续的，以节点的形式连接，每个节点会有一个next指针，指向下一个节点，通过指针来访问元素；

二、插入、删除的效率不同:

顺序表:

插入删除元素时，需要移动元素的位置也就是搬移元素，导致效率低下

链表：

插入删除时只需要修改指针指向。

三、内存利用率：

顺序表：

需要扩容，创建空间大小是固定的，当空间不够时需要进行扩容，以2倍的关系扩增的，你少一个空间，我增大到原来的2倍，还会有多余空间未使用，所以扩容会造成空间浪费的现象。

但是注意我们因为用的realloc扩容，所以扩容本身会有消耗！！👉👉👉

由于realloc扩容的特性，不确定是原地还是异地扩容，这个与编译器有点关系

原地扩容：扩容的空间地址与原来地址相同

异地扩容：扩容的空间地址与原来地址不同（将原来的数据拷贝过来，还要销毁原来的空间）

链表：

按需申请的空间，不会存在空间浪费现象，利用率极高

四、随机访问：

顺序表：

支持用下标随机访问

链表：

不支持，因为空间在物理上就不是连续的，next找到下一个节点，在用该节点的next找一个，找起来比较麻烦

五、缓存利用率：

缓存👉CPU高速缓存🧑‍🎓🧑‍🎓 内存在带电的情况下存储，当断电后未保存的数据会丢失（就像我们在用画板时，画了画，你给电脑关机，下次进去就找不到了）但其速度快，而硬盘可以不带电存储，但是速度慢。

🤔🤔为啥有寄存器和三级缓存？？

✨✨主要是cpu的运行速度很快，看不上内存日常不会去访问内存，但是寄存器和三级缓存的速度还是能入下眼✨✨

我们写的代码时，变量存在内存里面，当你要修改变量时会将数据放到寄存器，然后cpu对其接收指令进行修改

看下面代码的反汇编，mov 是将 i 放到 eax（寄存器）中，然后对寄存器的数据进行inc指令也就是加1， 在讲寄存器的数据放到可i中

但是寄存器个数有限，一般对于4个 8个字节会放到寄存器，数据比较大会加载到缓存，（ 缓存里面还要涉及到三级缓存的调用，有点深奥，不讲这么难的，可以自己去查资料）

cpu访问数据会先访问数据是否在缓存中，在---》缓存命中，直接访问。

                                                                不在---》不命中，先将数据加载到缓存中，再进行访问。

🤔怎么加载到缓存的？？

cpu会按cpu字长去读，会认为你访问当前数据后面（连续在一起的）都不在缓存中，给它加载进去

举个例子：数组为例子，下面的20个人就是一个数组。度假村相当于缓存，领导是cpu，大巴车也是cpu，cpu给你加载到缓存，再访问

注意：缓存有一定的范围，新进来的过多，放不下了，就给旧的清理掉！

---

对于链表了，你的物理空间是不连续，拉的数据太多，会把缓存区之前的一些数据排挤走了

顺序表：

 CPU缓存利用率高。

链表：

CPU缓存利用率低。

六、总结：

不同点	顺序表	单链表
存储空间	物理上一定连续（底层是数组）	只是逻辑上连续，物理上并不连续
随机访问	下标访问 O(1)	不支持：要遍历O(N)
任意位置的增删	需要搬运元素，效率低O(N)	无需搬运，只需要修改指针指向
插入	动态顺序表，需要扩容（成倍扩容，可能会造成空间浪费）	按需申请，没有扩容这一说法
应用场景	元素的高效存储+频繁的访问	任意位置插入+删除频繁
CPU缓存利用率	缓存利用率高	缓存利用率低

链表和顺序表各有优势，互相弥补各自的缺点

总之，顺序表用于数据元素较少、读取操作频繁的场景，而链表更适用于数据元素较多、插入、删除操作频繁的场景。

  就到               这吧  ❤️🫰