顺序表和链表

目录

1.线性表

2.顺序表

3.链表

1.线性表

线性表是n个具有相同特征的数据元素的有限序列。线性表是一种在实际中被广泛应用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…………

线性表在逻辑上是线性结构，也就是一条连续的直线，但是在物理上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成对数据的增删查改。

顺序表与数组的区别就是不能跳跃着存储，顺序表必须是依次连续存储数据。

#define N 10
typedef int SLDataType

typedef struct SeqList
{
	SLDataType a[N];//存储数据的数组
	int size;//数据个数
}SL;

这是一个简单的顺序表的定义，我们一般用对要存储的数据类型 tyepedef 一下，方便后续数据类型改变时更方便。上面的代码是一个静态的顺序表，虽然我们用#define定义了一个N来表示数组长度，但是他还是一个定长数组，使用定长数组来存储数据有很大的缺陷。所以我们一般用动态的数组来实现顺序表。

#define INIT_CAPACITY 10

typedef struct SeqList
{
	SLDataType* a; //维护动态数组
	int size;		//数据个数
	int capacity;	//数组容量
}SL;

动态的顺序表可以用malloc、realloc等函数来实现动态增长，但是在扩容的时候我们要注意一次扩容的大小，如果每次扩容的空间太小，会导致我们需要频繁扩容，我们之前讲到过realloc扩容有两种方式，原地扩容和异地扩容，而异地扩容的效率是很低的，还有一个拷贝的过程。但是如果一次扩容太多的话，可能会造成较大的空间浪费。在我的想法中，每次扩容INIT_CAPACITY个数据大小的空间还算适合，既不需要频繁扩容，也不会造成太大的浪费。

顺序表的实现

顺序表的实现-CSDN博客

实现完顺序表之后我们会发现顺序表的一些问题（缺点）：

1.中间和头部的插入删除效率低，时间复杂度为O(N)

2.增容可能需要申请新空间，拷贝数据，释放旧空间，会有不小的系统开销（主要原因是因为顺序表必须空间上连续造成的）

3.增容会存在一定的空间浪费。

那么如何解决这些问题呢？

为了避免空间浪费，能不能按需申请内存呢？有一个数据就申请一个空间，要增加数据就再申请一个，删除数据就把他的空间释放了，其实这种方法实现起来并不难，只要空间与空间之间有一个指针将他们联系起来，既能保持线性结构，也能实现对单个数据的释放申请，而这样的结构就是链表，链表能够按需申请和释放空间，而且不需要挪动数据，也不需要空间连续。

3.链表

链表共有八种结构：

1.带头和不带头（这里的头指的是哨兵位的头，也就是不存储数据的结构体）

2.单向和双向

3.循环和非循环

这三种类型组合起来就有八种结构的链表。

我们使用最多的两种链表结构：

1.无头单向非循环链表：结构简单，一般不会用来单独存储数据，实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等；

无头单向非循环链表的实现-CSDN博客

2.带头双向循环链表：结构最复杂，一般用来单独存储数据，是实际中使用的链表数据结构。虽然这种结构最复杂，但是使用代码实现之后会发现结构会带来很多优势，实现起来反而会更简单，这个结构才是完美解决了顺序表的缺点。

带头双向循环链表实现-CSDN博客

如果单纯从存储数据的方面来说，其实顺序表的存储效率更高，顺序表扩容是一次开辟多个空间，虽然存在一定的空间浪费，但是节省了时间，而链表虽然是按需申请空间，但是每一次插入数据都要malloc一块空间，时间开销大。

顺序表的优点：1.尾插尾删的效率很高

                         2.支持随机访问（用下标访问），而链表做不到，链表要有节点的地址才能访问到。

                         3.缓存命中率高，效率更快

顺序表的缺点：1.头部和中部的插入删除效率低，但是在实际中这些功能用的不多

                         2.扩容，单次扩容性能消耗大，当要异地扩容时，如果原顺序表存储的数据已经很多了，这时拷贝数据的时间开销就很大，而且存在空间浪费。

链表的优点：1.任意位置的插入删除效率很高O(1)

                      2.按需申请释放，单次申请比顺序表效率高，不会浪费空间，但是实际上因为每插入一次都要申请，所以总体效率不见得比顺序表好。

链表的缺点：1.不支持随机访问

上面说了顺序表有一个优点是缓存命中率高，我们可以简单来了解一下。

首先我们是找到计算机的存储分层的，呈现一个三角形的趋势，上面的寄存器高速缓存等更小更快相应的价格更高，而下面的磁盘网盘等空间更大访问速度更慢价格相应也更低。而我们写的这些数据结构的程序都是存储在内存中的，也就是上图中的主存，而代码经过编译之后是要到我买电脑的cpu中去执行的，代码运行过程中呢，cpu就会去访问我们的数据，由于 cpu 的访问速度很快，而如果cpu是直接去内存中访问的话，内存的访问速度又相对而言慢，这时候cpu的性能就没发挥出来，程序运行速度就会很慢。我们发现上面的图中在主存上面还有三级缓存，这三种高速缓存都是环绕在cpu周围的，而且速度也很快，所以cpu一般都是直接去高速缓存中访问数据的。cpu查找数据时，首先会在缓存中看有没有要找的数据，如果有，那就直接访问，这就叫命中。如果数据不在高速缓存中，这就叫不命中，这时就会先把数据加载到缓存中之后cpu再去缓存中查找数据。 在计算机设计时有一个局部性原理，就是当cpu去访问数据时，不会只将要访问的数据加载到缓存中，而是会把这个数据开始的一端内存都加载到缓存中，这样做的目的就是将于这个数据可能相关的数据都加载到缓存中，下次要访问与数据相关的数据可能就包含在这一段内存中，能提高效率，这一段内存的具体的长度取决于cpu的字长，与硬件有关。而当我们第一次访问数据时一般是不命中的，这时候就会把数据开始的一段内存都加载到缓存中以便cpu访问。 因为顺序表是连续存储的，所以加载顺序表的数据到缓存中时不知会把这一个数据加载进来，而是会加载多个数据（具体取决于cpu的字长），再访问后面的数据时可能就直接能在缓存中查找到了。而链表的空间是独立的，不一定连续，可能加载一个节点进来也可能加载多个节点，但是肯定是比不上顺序表的，所以链表的缓存命中率是要比顺序表低的。 同时，加载到缓存的那一段内存中有些是与我们所需要的信息完全无关的数据，这些无关数据加载到缓存中就浪费了缓存空间，当无关数据多了之后，缓存满了就会把缓存中那些长时间没有使用的数据清除来加载新的数据，而新加载进来的内存大多是无关信息，这就导致了缓存污染。 从这里看来，链表的缓存污染肯定是要比顺序表严重得多的。

所以我们一般单纯存储数据的时候还是用顺序表比较多，而当我们要频繁对数据进行修改的时候就更适合用链表来存储数据。