【初阶数据结构】顺序表与链表的比较（附题）

目录

一、顺序表和链表的区别（其他链表存在缺陷，比较意义不大，这里用带头双向循环链表与顺序表进行比较）

1.1插入、扩容与随机访问

二、缓存利用率的比较

2.1前置知识

详解及补充知识（本文仅为比较顺序表及链表，相关缓存与知识可以看下文）

---

一、顺序表和链表的区别（其他链表存在缺陷，比较意义不大，这里用带头双向循环链表与顺序表进行比较）

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

1.1插入、扩容与随机访问

首先链表的，如果知道要插入的位置，我们可以修改前后节点的指针，直接插入数据，不需要挪动其他数据非常方便。而顺序表我们如果在数据间插入数据就要将其他数据前移或后移。可能会出现为了插入一个数据而挪动原先所有数据的情况，成本较大。

其次，链表的本身没有容量的概念，节点都是按需申请的，不需要考虑扩容的问题。

这方面扩容本身就有很大的消耗。使用realloc扩容主要会有原地扩容和异地扩容两种情况。

如果要扩的空间不大，在已有空间接下来的地址够用或者可用，就会使用接下来的地址扩大原空间，这个过程原空间地址不变只是单纯申请空间扩大。一但接下来的空间不可用或者不够，realloc就会另寻一块足够大的可用地址申请空间（地址改变），之后将原空间中数据复制过来，并释放原空间。显而易见的，异地扩容的消耗较大。

此外扩容还会存在的一个问题是存在空间浪费，比如一般来说我们原空间容量是100，现在需要插入5个新元素，我们一般将原空间扩大两倍，但是可能我们只会插入5个数据，这就会浪费95个空间。

需要注意的是扩容存在的两个问题还是相互影响的，我们一般按照二倍扩容其实是通过概率学计算希望减少扩容次数，避免异地扩容的消耗,但是这样扩容大了，又会造成浪费的问题；反过来，为了节省空间，扩容小了，就会需要多次扩容，这样异地扩容的消耗会非常大。

不过一般来说。单次扩容大，减小扩容次数，节省时间；单次扩容小，扩容次数多，节省空间。除了物联网等领域，时间比空间更宝贵，所以一般扩容扩大点。

但是链表有个比较大的缺陷是不支持随机访问（用下标访问），如果大家学过C++的STL,就会发现链表的排序比起顺序表来说没有优势，此外如二分查找等场景都需要使用顺序表或者说数组。

总的来说，顺序表在存储空间连续、支持随机访问等方面占有优势，链表在没有容量和任意位置插入方面占优势。顺序表与链表是互补，各有优势。

二、缓存利用率的比较

2.1前置知识

备注：缓存利用率参考存储体系结构以及局部原理性。

如上图，为我们电脑中存储体系，一般来说我们接触最多的是主存(即内存)和本地磁盘（磁盘或者叫做外存），两者的区别在于内存是带电存储，速度快，但是空间相对较小，8G、16G等；而磁盘是不带电存储，速度慢，但是空间大，可以达到几百G及以上。所谓带电与不带电存储是指程序运行时数据主要在内存上，如果此时断电，数据都会丢失，如果我们按保存，文件就会被保存到硬盘上，这样即使断电，数据也会保留下来。

以上图i++为例，程序运行后由CPU来执行一系列指令，但是CPU的速度与内存的速度相差非常大，两者不同频，所以将内存中的数据加载到寄存器中，CPU再对寄存器中的数据进行操作，然后将数据放回内存中，这是数据较小的情况（四或八个字节），如果数据较大，就会加载到L3高速缓存中，然后L2,L1一级一级加载。

2.2顺序表和链表缓存利用的比较

像顺序表和链表中的数据较大，是加载到缓存中的，CPU执行指令之前，会先拿链表或顺序表的地址，判断数据在不在缓存中，如果数据在缓存中，叫做缓存吗，命中，可以直接访问缓存；如果不在缓存内，叫不命中，这是要先把数据从内存加载到缓存中再访问。

在这个加载的过程中由于计算机局部设计原理与计算机设计逻辑，往往访问当前位置，那么极有可能访问，同时单独只访问当前位置的设计不划算（（使用物理线探测当前位置是0还是1）），所以一般会加载一段一长段（几十个字节，甚至是多少k），具体数值跟CPU的型号（字长）有关系

这时对于数组来说，如果第一个数据不命中，那么就会将第一个数据连同后面一大段数据加载到缓存中（数组不同数据存储的物理地址是连续的），之后我们连续访问多个数据都会出现缓存命中的前情况，我们将这称为缓存命中率高，

但是链表不同节点的物理地址极大概率是不连续的，这时将第一个节点连同后面一大段数据加载到缓存中时，极大概率是无法加载第二个节点到缓存中的（可能加载部分节点），这时内存中就会加载进很多无用数据，因为缓存大小是固定的，根据最近最少用原则（LRU）,这些无用数据会把缓存中之前早期的数据挤走，我们将这种情况称为缓存污染。所以链表的缓存命中率较低。

详解及补充知识（本文仅为比较顺序表及链表，相关缓存与知识可以看下文）

与程序员相关的CPU缓存知识