数据结构|顺序表、链表数据结构|算法|链表

文章目录

线性表
顺序表
- 概念及结构
- - 1.静态顺序表
  - 2.动态顺序表
- 接口实现
- 相关OJ
- 顺序表的优缺点
链表
- 链表的概念及结构
- 链表的优缺点
- 链表的分类
- 无头+单向+非循环链表实现
- 链表相关练习
- 带头双向循环链表实现
顺序表和链表的区别

本章我们主要学习线性表中的顺序表和链表。
线性表线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表的定义是描述其逻辑结构，而通常会在线性表上进行的查找、插入、删除等操作。
线性表在逻辑上是线性结构（一对一）。但是在物理结构上并不一定是连续的，在计算机存储器中的存储一般有两种形式，一种是顺序存储（内存空间连续，数组），一种是链式存储（内存空间不一定连续）。
线性表描述的是逻辑结构。
常见的线性表：顺序表、链表、栈、队列、字符串…

文章图片

顺序表概念及结构顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表属于线性表的顺序存储。可以把顺序表就理解为数组，但是与数组不同的是，顺序表要求数据必须从头开始连续存储，中间不能跳跃间隔。
顺序表一般可以分为静态顺序表、动态顺序表。
1.静态顺序表
使用定长数组存储元素。

文章图片

2.动态顺序表
使用动态开辟的数组存储。

文章图片

接口实现静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，到底开多大空间合适呢？
现实中，基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
初始化

//SeqList.h typedef int SLTDataType; typedef struct SeqList { SLTDataType* a; //指向动态开辟的空间 int size; //已经存储数据的个数 int capacity; //容量 }SLT; void SeqListInit(SLT* ps);

//SeqList.c void SeqListInit(SLT* ps) { //如果是结构体传参，形参是实参的一份拷贝，改变形参，不会影响实参 //这里想要改变结构体成员a的值 //所以这里选择结构体指针传参 //这里初始化时没有开辟空间，可以选择开辟一定的空间 ps->a = NULL; ps->capacity = 0; ps->size = 0; }

尾插
3种情况：
1.顺序表没有空间
2.顺序表空间不够，需要扩容
3.空间足够，直接尾插
所以插入数据之前，需要先检查顺序表的空间。

//SeqList.c void CheckCapacity(SLT* ps) { if (ps->size == ps->capacity) { int newcapacity = (ps->capacity == 0 )? 4 : (2 * ps->capacity); //当ps是NULL时，realloc的功能和malloc相同 SLTDataType* tmp = (SLTDataType*)realloc(ps->a,sizeof(SLTDataType)*newcapacity); if (tmp == NULL) { printf("realloc failed\n"); exit(-1); } //扩容成功 ps->a = tmp; ps->capacity = newcapacity; } }void SeqListPushBack(SLT* ps, SLTDataType x) { CheckCapacity(ps); ps->a[ps->size] = x; ps->size++; }void SeqListPrint(SLT* ps) { int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ",ps->a[i]); } printf("\n"); }

也可以选择在初始化时，开辟一定的空间。
销毁顺序表

void SeqListDestory(SLT* ps) { free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; }

对于内存的报错（比如越界），一般都是在销毁内存的时候才检查出来。
尾删
2种情况：
1.顺序表是空的，此时做尾删操作，做出处理；
2.顺序表中有数据，正常处理

void SeqListPopBack(SLT* ps) { //ps->size应该大于0 assert(ps->size > 0); ps->size--; }

头插
1.顺序表是空的，没有数据
2.空间不够，扩容
3.有数据空间够，所有数据后移

void SeqListPushFront(SLT* ps, SLTDataType x) { //首先判断空间是否满了 CheckCapacity(ps); //所有元素后移，把第1个位置空出来，把x放进去 //移动顺序：从后向前移 int end = ps->size -1; while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; }

头删
1.顺序表是空的，没有数据
2.顺序表有数据，所有的数据前移

void SeqListPopFront(SLT* ps) { assert(ps->size > 0); //所有数据前移 int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }

查找

//找到了返回x位置下标，没有找打返回-1 int SeqListFind(SLT* ps, SLTDataType x) { //遍历数组查找 int i = 0; for (i = 0; i < ps->size; i++) { if (x == ps->a[i]) { return i; } } return -1; }

指定位置插入

void SeqListInsert(SLT* ps, size_t pos, SLTDataType x) { assert(pos >= 0 && pos <= ps->size); CheckCapacity(ps); int end = ps->size-1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }

头插和尾插可以用SeqListInsert来实现。
删除指定位置数据

void SeqListErase(SLT* ps, size_t pos) { assert(pos >= 0 && pos < ps->size); int begin = pos; while (begin < ps->size -1) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; }

头删和尾删可以使用SeqListErase来实现。
相关OJ OJ分类：IO型、接口型
IO型需要自己写头文件、main函数、测试用例通过scanf获取，测试结果需要printf输出。
接口型不需要自己写头文件、main函数等。
当需要返回多个数据时，可以作为输出型参数。
练习1
原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。
练习2
删除排序数组中的重复项
练习3
合并两个有序数组
顺序表的优缺点优点：内存连续，只要知道首地址就可以访问所有数据，也就是支持随机访问，有些算法需要结构支持随机访问，比如二分查找、优化的快排等。
缺点：
1.空间不够了需要扩容（realloc），但是增容是要付出代价的，需要拷贝数据，并释放原来空间；
2.为了避免频繁扩容，内存满了基本都是扩2倍，但是这样可能就导致一定空间的浪费；
3.顺序表要求数据是从开始位置连续存储的，那么我们在头部或者中间位置插入删除数据，就需要挪动数据，时间复杂度是O(N)，效率就不高。
针对顺序表的缺点，设计出了链表。
链表链表的概念及结构链表属于线性表的链式存储。
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
数据结构一般都在堆上开辟空间，因为我们并不知道要存多少数据。
链表逻辑结构：箭头是我们想象出来的

文章图片

链表存储结构：在内存中的真实存储，没有箭头

文章图片

从图中可以看出，链表在逻辑上是连续的，但是物理结构上不一定连续；实际的结点一般都是在堆上开辟的；在堆上申请空间，按照一定的策略来分配，两次申情的空间可能连续，也可能不连续。
链表的优缺点链表是针对顺序表的缺陷来设计的，但是链表也有自己的缺点。
缺点：
1、每个数据都需要有一个指针来记住下一个数据的位置；
2、不支持随机访问（不支持下标访问）。
优点：
1、按需申请空间。不用了就释放空间，更合理的利用空间；
2、头部、中间插入删除数据，不需要挪动数据，不存在空间浪费。
链表的分类实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.单向或者双向

文章图片

对于单向链表，插入和删除需要遍历链表。
对于双向链表，一个结点记住了前一个结点的位置和下一个结点的位置，插入和删除比较方便。
2.带头或者不带头

文章图片

带头也就是多一个哨兵位头结点，这个结点不存储有效数据。使用带哨兵位的头结点，尾插、头删数据时候，就不需要使用二级指针，因为哨兵位头结点是不存储有效数据的，并且位置固定，不会改变。
3.循环或者非循环

文章图片

尾结点的next指向头结点。
使用最多的有两种：无头单向不循环链表、带头双向循环链表。

文章图片

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

无头+单向+非循环链表实现下面，我们来实现一个简单的单向、不带头、非循环链表，无头就是不带哨兵位，phead直接指向第一个结点，该结点是有有效数据的。
定义链表结点结构体类型

typedef int SLTDataType; typedef struct SListNode { struct SListNode* next; SLTDataType data; }SLNode;

1.打印链表

void SListPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d ",cur->data); cur = cur->next; } printf("\n"); }

这里只是打印链表结点数据，不需要改变结点指针，所以不需要传入二级指针。
2.单链表尾插
情况1：
链表为空时

文章图片

此时链表为空，phead的值为NULL，这时要尾插一个结点，那么需要创建一个新的结点，然后phead指向该结点，那么就需要改变phead的值，phead本身是一个一级指针，想要改变一级指针的指向，就需要传入二级指针。

文章图片

情况2：
链表中已经有数据，我们只需要找到尾，然后将新结点链接在尾结点后面即可。

文章图片

文章图片

综合这两种情况，这里使用二级指针，为了解决插入第一个结点的情况。
通过一级指针去改变该指针指向空间的内容；通过二级指针去改变一级指针的指向。

void SListPushBack(SLNode** pphead, SLTDataType x) { //形参不能使用一级指针， //这里，当链表中没有数据时，如果使用一级指针phead，那么phead传进来就是NULL,那么此时不需要找尾，直接创建新结点，将该结点赋值给phead即可 //这里就需要改变phead的值，因为形参的改变不影响实参，如果传入一级指针，不能实现效果 //所以这里需要传递phead的地址，要使用二级指针 //这里二级指针就是为了解决链表为空的情况 assert(pphead != NULL); //创建新结点 SLNode* newNode = (SLNode*)malloc(sizeof(SLNode)); newNode->data = https://www.it610.com/article/x; newNode->next = NULL; if (*pphead == NULL) { //此时链表为空 *pphead = newNode; } else { //链表不为空 SLNode* tail = *pphead; //找到尾 while (tail->next != NULL) { tail = tail->next; } //尾插 tail->next = newNode; } }

当然，这里也可以不使用二级指针，可以以返回值的形式，返回头结点指针，但是这种形式有点奇怪。
3.头插
情况1：
链表为空

文章图片

文章图片

情况2：
链表中已经有数据

文章图片

这里头插同尾插，也需要使用二级指针，每次插入都需要创建新结点，所以写成一个函数。

SLNode* BuyNewNode(SLTDataType x) { SLNode* newNode = (SLNode*)malloc(sizeof(SLNode)); if(newNode == NULL) { exit(-1); } newNode->data = https://www.it610.com/article/x; newNode->next = NULL; return newNode; }//头插 void SListPushFront(SLNode** pphead, SLTDataType x) { assert(pphead != NULL); //创建新结点 SLNode* newNode = BuyNewNode(x); //新结点的next是原链表首个结点，也就是*pphead newNode->next = *pphead; //*pphead指向新结点 *pphead = newNode; }

4.尾删
情况1：
链表为空

文章图片

此时不允许有删除操作，使用断言sassert。
情况2：
链表只有一个结点

文章图片

此时删除一个结点后，phead的值需要改变，phead应该为NULL，所以需要传入二级指针。

文章图片

情况3：
链表有多个结点

文章图片

文章图片

找到倒数第二个结点，记住该位置，释放最后一个结点，将此时最后一个结点的next指向NULL。

//尾删 void SListPopBack(SLNode** pphead) { assert(pphead != NULL); assert(*pphead != NULL); //方式1 只有一个结点 //if ((*pphead)->next == NULL) //{ // //释放空间 // free(*pphead); // *pphead = NULL; //} //else //{ // SLNode* cur = *pphead; // while (cur->next->next != NULL) // { //cur = cur->next; // } // //找到尾 // //释放空间 // free(cur->next); // cur->next = NULL; //} //方式2 //只有一个结点 if ((*pphead)->next == NULL) { //释放空间 free(*pphead); *pphead = NULL; } else { SLNode* prev = NULL; SLNode* tail = *pphead; while (tail->next != NULL) { //记住前一个位置 prev = tail; tail = tail->next; }//找到尾tail //释放空间 free(tail); tail = NULL; //前一个结点的next置为NULL prev->next = NULL; } }

文章图片

tail释放后，置为NULL，prev的next就是tail，就是NULL，为什么prev的next还要置为NULL呢？这里要注意，free是将空间使用权限还给操作系统，但是这块空间还是在这里的，tail置为NULL后，tail就不指向这块空间了，指向0地址空间，而且tail和prev都是局部变量，函数调用结束后，这两个变量都不存在了，所以必须将prev的next置为NULL，否则prev->next就是野指针了，所以我们要使用prev来记住位置。
5.头删
情况1：
链表为空，做出处理，可以使用断言，或者if条件判断，给用户提示。

文章图片

情况2：
只有一个结点

文章图片

文章图片

情况3：
多个结点

文章图片

文章图片

情况2和情况3合并为一种情况，同样需要记住第二个结点的位置，释放第一个节点，将phead指向第二个结点。

//头删 void SListPopFront(SLNode** pphead) { assert(pphead != NULL); assert(*pphead != NULL); //记住第二个结点 SLNode* next = (*pphead)->next; //释放第一个节点 free(*pphead); //*pphead = NULL; //*pphead指向第二个结点 *pphead = next; }

6.查找

// 单链表查找，返回结点指针 SLNode* SListFind(SLNode* phead, SLTDataType x) { SLNode* cur = phead; //遍历查找 while (cur != NULL) { if (cur->data =https://www.it610.com/article/= x) { return cur; } else { cur = cur->next; } } return NULL; }

7.插入
(1)在pos位置之前插入
情况1：
头插

文章图片

情况2：
中间插入

文章图片

//在pos位置之前插入 void SListInsert(SLNode** pphead,SLNode* pos, SLTDataType x) { assert(pphead != NULL); assert(pos != NULL); SLNode* newNode = BuyNewNode(x); if (*pphead == pos) { //头插 newNode->next = *pphead; *pphead = newNode; } else { //找到pos之前一个位置 SLNode* posPrev = *pphead; while (posPrev->next != pos) { posPrev = posPrev->next; }newNode->next = pos; posPrev->next = newNode; } }

(2)在pos位置之后插入
对于单链表，在pos之前插入，不够方便，因为要从头开始找到pos的前一个位置，时间复杂度是O(N)，所以一般是在pos位置之后插入，直接创建新结点，连接到pos节点之后即可，时间复杂度是O(1)。

//在pos位置之后插入一个新结点 void SListInsertAfter(SLNode* pos, SLTDataType x) { assert(pos != NULL); //创建新结点 SLNode* newNode = BuyNewNode(x); SLNode* posAfter = pos->next; pos->next = newNode; newNode->next = posAfter; }

8.删除
(1)删除pos位置的值
情况1：
删除第一个元素

文章图片

这种情况需要改变phead的值，所以需要传入二级指针。
情况2：
删除中间元素

文章图片

//删除pos位置的值 void SListErase(SLNode** pphead, SLNode* pos) { assert(pphead != NULL); assert(pos != NULL); if (pos == *pphead) { //头删 SListPopFront(pphead); } else { 中间删除找到pos位置，并记录pos之前位置 //SLNode* posPrev = NULL; //SLNode* cur = *pphead; //while (cur != pos) //{ // posPrev = pos; // pos = pos->next; //}找到pos位置 //posPrev->next = pos->next; //free(pos); //pos = NULL; //中间删除SLNode* posPrev = *pphead; while (posPrev->next != pos) { //找到pos之前位置 posPrev = posPrev->next; } posPrev->next = pos->next; //释放pos位置 free(pos); pos = NULL; } }

(2)删除pos位置之后的值
【数据结构|顺序表、链表】

文章图片

void SListEraseAfter(SLNode* pos) { assert(pos != NULL); assert(pos->next != NULL); SLNode* next = pos->next; pos->next = next->next; //释放空间 free(next); next = NULL; }

9.销毁链表
考虑phead为NULL的情况

文章图片

当phead为NULL时，不能对phead进行解引用操作，phead->next是错误的。

文章图片

void SListDestroy(SLNode** pphead) { //释放所有结点 assert(pphead != NULL); SLNode* cur = *pphead; 下面写法错误，若cur是NULL,这里有问题 //SLNode* next = cur->next; //while (next != NULL) //{ // free(cur); // cur = next; // next = next->next; //} //free(cur); //cur = NULL; while (cur != NULL) { SLNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }

单链表有很多缺点，比如不能找到当前结点的前一个结点。单链表更多的是作为更复杂数据结构的子结构，比如哈希桶、邻接表。链表存储数据更多的使用双链表。
链表相关练习 1.删除链表中等于给定值 val 的所有节点
2.反转一个单链表
3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个
中间结点
4.输入一个链表，输出该链表中倒数第k个结点
5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成
的
6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
7.链表的回文结构
8.输入两个链表，找出它们的第一个公共结点
9.给定一个链表，判断链表中是否有环
对于带环问题，这里进一步扩展，思考如下两个问题：
问题1：
为什么fast和slow一定会在环中相遇，会不会在环中错过，永远遇不上呢？请证明。
初始条件：fast = slow = head

文章图片

fast先入环，slow走到入环前距离的一半

文章图片

slow入环，fast已经在环中走了一定的距离，假设此时fast和slow之间的距离为N（具体长度和位置由环的长度决定）

文章图片

slow每次走一步，fast每次走两步，此时fast和slow之间的距离变成了N-1

文章图片

slow再走一步，fast又走两步，fast和slow之间的距离变成N-2

文章图片

这样推理下去：

文章图片

fast每追一次，fast和slow之间的距离就减少1，最终fast和slow之间的距离为0，也就是fast和slow相遇。

文章图片

问题2：
为什么slow每次走一步，fast每次走两步？fast每次走三步、四步，甚至更多步可不可以？请证明。
（1）假设slow每次走一步，fast每次走3步
当fast进环时，slow走了距进环距离的1/3

文章图片

slow进环，fast已经在环内走了一段距离，此时fast和slow之间的距离为N，fast追slow

文章图片

slow走一步，fast走3步，此时fast和slow之间的距离为N-2

文章图片

这样推理下去：

文章图片

当slow进环时，如果fast和slow之间的距离为偶数，fast和slow可以相遇；
如果slow进环时，fast和slow的距离为奇数，并且环的长度为奇数，那么fast和slow会相遇；

所以如果fast每次走3步，slow和fast可能会相遇，也可能不会相遇，由环的长度决定。
（2）假设slow每次走一步，fast每次走4步
同上可以得出：

文章图片

所以对于fast一次走3步，4步，fast和slow的相遇是有条件的。
所以选择fast每次走2步，fast和slow一定能够相遇。
10.给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL
11.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝
带头双向循环链表实现结构复杂，但是操作更加简单。
初始化
方式1：使用二级指针作为参数，在函数内部可以改变函数外面的一级指针的指向

//方式1 二级指针 void ListInit(LTNode** phead) { *phead = (LTNode*)malloc(sizeof(LTNode)); if (*phead == NULL) { exit(-1); } (*phead)->next = *phead; (*phead)->prev = *phead; }

方式2：在函数内部动态开辟空间，将指针作为返回值返回

//方式2 返回值 LTNode* ListInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); if (phead == NULL) { exit(-1); } phead->next = phead; phead->prev = phead; return phead; }

尾插
只有哨兵位头结点

文章图片

文章图片

链表中已经有部分数据

文章图片

//尾插 void ListPushBack(LTNode* phead, LTDataType x) { //哨兵位头结点是不可能为空的 assert(phead != NULL); //1.创建新结点 LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); if (newNode == NULL) { exit(-1); } newNode->data = https://www.it610.com/article/x; LTNode* tail = phead->prev; //2.尾插新结点 newNode->next = phead; tail->next = newNode; newNode->prev = tail; phead->prev = newNode; //复用ListInsert //ListInsert(phead,x); }

这里不同于无头单向不循环链表，这里不需要使用二级指针，因为哨兵位头结点，不存储有效数据，phead固定，不会改变。
打印链表

void PrintList(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d -> ",cur->data); cur = cur->next; } printf("\n"); }

尾删
注意没有有效结点的情况

void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); //找到尾 LTNode* tail = phead->prev; //尾前一个结点 LTNode* tailPrev = tail->prev; //释放尾结点 free(tail); tail = NULL; tailPrev->next = phead; phead->prev = tailPrev; //复用ListErase //ListErase(phead->prev); }

头插

文章图片

void ListFrontPush(LTNode* phead, LTDataType x) { assert(phead); //创建新结点 LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); if (newNode == NULL) { exit(-1); } newNode->data = https://www.it610.com/article/x; LTNode* next = phead->next; phead->next = newNode; newNode->next = next; newNode->prev = phead; next->prev = newNode; //复用ListInsert //ListInsert(phead->next,x); }

头删

void ListPopFront(LTNode* phead) { assert(phead); //链表为空 assert(phead->next != phead); LTNode* next = phead->next; LTNode* nextNext = next->next; //释放next free(next); next = NULL; phead->next = nextNext; nextNext->prev = phead; //复用ListErase //ListErase(phead->next); }

查找

//查找 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data =https://www.it610.com/article/= x) { return cur; } else { cur = cur->next; } } return NULL; }

插入

//pos前面结点插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); //创建新结点 LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); if (newNode == NULL) { exit(-1); } newNode->data = https://www.it610.com/article/x; //找到pos之前位置 LTNode* posPrev = pos->prev; posPrev->next = newNode; newNode->next = pos; newNode->prev = posPrev; pos->prev = newNode; }

删除

//pos位置删除 void ListErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos == NULL; }

销毁链表

void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } //释放phead free(phead); phead = NULL; }

但是要注意，调用完ListDestroy函数，在外面需要把实参链表的哨兵位结点指针置为NULL，否则是野指针.
因为经常需要创建新结点，写成一个函数

LTNode* BuyNewListNode(LTNode* phead, LTDataType x) { LTNode* newNode = (LTNode*)malloc(sizeof(LTNode)); if (newNode == NULL) { exit(-1); } newNode->data = https://www.it610.com/article/x; return newNode; }

对于尾插、头插、尾删、头删，可以使用ListErase和ListInsert来实现，所以对于带头双向循环链表，还要实现了ListErase和ListInsert即可。
测试代码：

void TestDoubleList() { LTNode* plist = NULL; //想在ListInit中改变plist的值 //方式1.那么传入二级指针 //ListInit(&plist); //方式2.返回值 plist = ListInit(); //尾插入 ListPushBack(plist,1); ListPushBack(plist,2); ListPushBack(plist,3); ListPushBack(plist,4); PrintList(plist); //头插 ListFrontPush(plist,100); ListFrontPush(plist,200); ListFrontPush(plist,300); PrintList(plist); //尾删 //ListPopBack(plist); //PrintList(plist); //头删 /*ListPopFront(plist); PrintList(plist); */ //查找 LTNode* pos = ListFind(plist,100); //pos之前插入 ListInsert(pos,50); PrintList(plist); //删除pos位置 ListErase(pos); PrintList(plist); ListDestroy(plist); plist = NULL; }int main() { TestDoubleList(); return 0; }

顺序表和链表的区别顺序表和链表各有优劣
顺序表
优点：
1.支持随机访问（可以使用下标进行访问）。
2.cpu高速缓存命中率更高。
缺点：
1.头部和中部插入、需要移动数据，删除数据效率低，O(N)。
2.是一块连续的物理空间，空间不够的时候，需要扩容的，（1）扩容有一定程度的消耗；（2）为了避免频繁扩容，一般都按照倍数去扩容，但是如果空间用不完，就会造成浪费。
链表（带头双向循环）
优点：
1.任意位置插入删除效率高，O(N);
2.按需申请释放空间，空间利用率高，不造成浪费。
缺点：
1.不支持随机访问（不能使用下标访问），意味着一些排序、二分查找等算法不使用。
2.链表存储一个值，同时要存储链接的指针，有一定的消耗。
3.cpu高速缓存命中率更低。

文章图片

文章图片

假设现在有一个顺序表a，和一个链表list
现在需要分别遍历顺序表a和链表list
cpu执行指令，首先会去内存中访问数据，找到首个数据的地址，然后看看该地址在不在高速缓存中，如果在，那么就直接访问，如果不在会先加载到高速缓存中，再访问数据。

文章图片

第一次顺序表和链表都不命中。
对于顺序表，加载第一个元素地址时，就近原则，会加载一块连续的空间，一次加载20byte到高速缓存中（具体一次加载多大由硬件决定），然后访问第二个元素时，发现地址已经在高速缓存中了，命中，访问效率提高。
对于链表，加载第一个元素时，也是加载一块连续空间，但是链表的结点大多数情况下物理上不是连续，访问第二个结点时，发现地址并不在高速缓存中，没有命中。同时这样占用了缓存空间，造成缓存污染，缓存中加载了很多没用的地址。
CPU缓存知识