数据结构：线性表中顺序表和单链表的比较

看到一道选择题是线性表中顺序表与单链表的区别对比，感觉对于这二者的区别了解不是很全面，决定来一波总结。至于什么是线性表，可以参考该博客。

线性表中顺序表和单链表的比较

一、什么是顺序表和单链表

顺序表：
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

单链表：
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。它的数据以结点来表示，每个结点包括数据和指针。

---

二、二者的比较

1.基于空间的比较

（1）存储分配的方式：

从二者的定义我们能看出来，
顺序表是地址连续存储，并且具有固定的空间大小，是静态存储；
而单链表存储地址可以不连续，没有固定空间，需要添加数据时可通过尾部指针指向所要添加存储数据的空间即可，是动态存储。

这里我们加一个存储密度的概念：
存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量

显然我们可以得出这样的结果：
顺序表的存储密度 = 1
链表的存储密度 < 1（链表中指针也占用存储量，但指针不是数据）

（2）空间的利用率：

对于未知数量的数据存储，用单链表较好，每需要存储一个数据，就会开辟一个空间，即使有指针占据空间，所产生的浪费也比顺序表对于未知数量数据开辟较大空间的浪费少。

对于已知存储数据量来说，顺序表开辟对应的空间大小，来存储数据，因为顺序表存储密度为 1，就完全没有浪费的空间，而单链表就会造成空间浪费。而且编译器在进行内存分配时，由于单链表是随机开辟空间存储，这样容易在磁盘产生碎片空间，造成更大的空间浪费。

（3）对CPU高速缓存的影响：

因为顺序表存储地址连续，一次性会开辟存储多个元素的空间，所以在使用顺序表时，可以一次把多个数据写入高速缓存，再写入主存，顺序表的CPU高速缓存效率更高，且CPU流水线也不会总是被打断；而单链表是每需要存储一个数据开辟一次空间，所以每个数据存储时都要单独的写入高速缓存区，再写入主存，这样就造成了，单链表CPU高速缓存效率低，且CPU流水线会经常被打断。

2.基于时间的比较

通常我们比较时间就是针对其时间复杂度进行比较，由于我之前的博客：数据结构 : 数组 / 链表 / 二叉排序树增删改查的时间复杂度解析对于该部分有详细的概述，这里就补在阐述了，可以直接看得出的总结图

顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针

---

三、总结

使用顺序表和链表都必须满足每个元素占有相同大小的内存空间，并且这个大小是固定的。

一般来说线性表（顺序表和单链表都属于线性表）的插入删除操作会被执行的频繁一些，因此，使用单链表的频率较大。

在查询操作使用的比较频繁时，使用顺序表会好一些；在插入、删除操作使用的比较频繁时，使用单链表会好一些。