0.引言
我们在学习过顺序表之后，会发现两点不是很优秀的操作：
1.顺序表的头插和中间的插入，头删和中间的删除：
需要不断的覆盖数据，时间复杂度是O(n)，当我们的顺序表存入100w个数据的时候，花费的时间是非常之多的。
2.动态开辟空间：
a. 一般动态开辟的空间都是以2倍的形式开辟，当我们已经开辟了100个空间，并且存满了，此时我们还需要存放5个数据，那么就又需要开辟200个空间了，我们存放5个数据之后，还剩余了195个空间没有放数据，这也就导致了空间的浪费。
b. 而且我们开辟新空间，拷贝数据，释放旧空间还会有一定的消耗。
注意⚠️⚠️⚠️：
我们在申请空间的时候必须要主动给它释放掉，因为申请空间的时候，是在堆上申请的，这段空间不会随着程序的结束而自然释放掉，所以要在我们程序结束之前，主动释放掉这段空间。
那有没有一种结构会很简便呢？即不需要O(n)的时间复杂度，也解决了空间浪费的缺点，答案肯定是有的，就是我们本次要讲解的链表。
1.链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的 。也就是说链表的物理结构不连续，但逻辑结构连续。
上面的是什么意思呢？博主用通俗的语言讲一下：
我们先明确一点，链表的元素叫做节点，这里的链表，首先是一个线性表，需要存入数据的，顺序表是通过什么来找到下一个元素的呢？答案是数组下标，而链表是如果找到下一个节点的呢？是指针，链表是通过指针链接起来的。那我们链表主要的结构就出来了，元素和指向下一个元素的指针。如何将它们组合起来呢？就又用到了我们的结构体了。
我们定义一个结构体来表示链表的节点，结构体内部要包括节点的值和指向下一个节点的指针。
首先先了解如下概念
前驱节点：一个节点前面的节点
后继节点：一个节点后面的节点
链表开始的节点称作：头节点
链表末尾的节点称作：尾结点
其余节点称作：中间节点。
指向头节点的指针：头指针
指向尾结点的指针：尾指针
在知道这些之后，我们继续往下读，去了解链表的逻辑模型和物理模型吧！
2.链表的逻辑模型
下图是链表的逻辑模型，黄色的正方形代表的是链表的节点，节点是由结构体组成的，而结构体里面有本节点的值和指向下一个节点的指针。通过图片就把我们上面说的理论形象化了。
从图中看，链表的逻辑模型一定是连续的，链表通过节点组成，节点之间通过指针链接的，是线性的。
3.链表的物理模型
如图：在物理模型中，我们看到每个节点的地址都不是连续的，所以链表的物理模型不是连续的，不是线性的。我们所说物理上的线性是根据每个节点的物理地址来的，如果物理地址是挨着的就是线性，反之就不是。很显然，链表物理模型并不是线性的。
在学习完链表的逻辑模型和物理模型之后，就让我们一起看看链表具体有哪几种呢？
4.链表的分类
4.1 单向链表
单向链表是最简单的链表结构，但是在实现接口的时候却是最鸡肋的，具体实现会在后面提供源代码。
单向链表顾名思义，链表是单向的，1->2->3->4->5->NULL，缺点是某一个节点找不到它的前驱节点，只能找到后继节点，因为是单向的。
4.2 双向链表
这个双向链表就比单向好很多了，通过一个节点可以找到前驱节点，也可以找到后继节点。
4.3 带头单向链表（带哨兵位）
带头单向链表，这个带头是带一个哨兵位，方便咱们的头插和头删。
哨兵位节点不存放元素。
4.4 带头双向链表（带哨兵位）
4.5 循环单链表
4.6 循环双向链表
4.7 带头循环单链表
4.8 带头循环双向链表
这个结构是链表的最优结构，我们会后面的接口实现也提供了这个链表。
5. 单链表的实现（接口实现代码）
5.1 单链表的定义
我们对单链表的定义是看节点需要什么，因为链表的节点是结构体构成的，节点需要什么就往结构体里存放对应的数据类型。
单链表的每个节点需要该节点的值和指向下一个节点的指针
所以我们定义一个结构体，包括 值和指针 。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
5.3 单链表的动态申请一个节点空间
这个函数是当我们需要往节点里存放值的时候必须经过的一步，在存放值之前，需要malloc一个节点的空间，开辟空间之后再把值放入，这里不要忘了将节点的next置为空，否则就是野指针。
SLTNode* BuySListNode(SLTDataType x) //创造新节点 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
5.4 单链表的销毁
销毁这里就看创造了多少个节点的空间，挨个销毁就行。但是我们思考一个问题，当销毁了当前空间，那如何找到下一个节点呢？
如图：
如果我们只是释放phead指向的节点，删除之后是无法找到下一个节点的，也就没办法继续释放后面的节点空间，那这里我们就需要一个指针over来指向phead指向的节点的下一个节点。
这里我们就新建个指针over指向的是phead指向的节点的下一个节点，当释放当前节点之后，让phead指向over，over再指向phead指向节点的下一个节点就OK了。
void SLT_Destroy(SLTNode*phead)//销毁 { while (phead != NULL) { SLTNode *over = phead->next; free(phead); phead = over; } }
5.5 单链表的头插头删
头插：
单链表的头插就比顺序表的头插快多了，不再需要覆盖数据，只需要将我们创建的新节点的next指向现在的头节点，再将指向头节点的指针指向新节点。但是需要注意的是我们改的是指针，如果想更改指针，就需要传入指针的地址，也就是用到了我们的二级指针。
头删：
头删只需要删除当前节点，让下一个节点当新的头节点即可，这里需要用assert断言一下，assert函数在<assert.h>这个头文件里，是用来判断括号里的条件是否成立，成立就继续，不成立就报错。
删除头节点之后，还要更新头节点，也需要一个指针 指向要删除的头节点的下一个节点，再将指向原头节点的指针指向新的头节点，这里也是更改指针，所以传入的也是二级指针。
void SLTPushFront(SLTNode** pphead, SLTDataType x) //头插 { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void SLTPopFront(SLTNode** pphead) //头删 { // 空 assert(*pphead); // 非空 SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }
头删：
头删只需要删除当前节点，让下一个节点当新的头节点即可，这里需要用assert断言一下，assert函数在<assert.h>这个头文件里，是用来判断括号里的条件是否成立，成立就继续，不成立就报错。
删除头节点之后，还要更新头节点，也需要一个指针 指向要删除的头节点的下一个节点，再将指向原头节点的指针指向新的头节点，这里也是更改指针，所以传入的也是二级指针。
void SLTPushFront(SLTNode** pphead, SLTDataType x) //头插 { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void SLTPopFront(SLTNode** pphead) //头删 { // 空 assert(*pphead); // 非空 SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }
5.6 单链表的尾插尾删
尾插：
尾插这里要分两种情况：
1.没有节点的尾插：
这里的插入的节点就是头节点，需要更改一下指向头节点的指针phead，更改指针就用到二级指针。
2.有节点的尾插：
对于有节点的尾插，我们首先应该找到链表的尾结点，再将尾结点的next指向新节点。
尾删：
尾删分三种情况：
1.链表为空：
这里就需要用assert断言一下，为空就报错。
2.链表只剩一个节点：
当链表只有一个节点的时候，也就是*pphead->next == NULL。改变的就是头节点，因为我们对头节点进行删除，链表就没有节点了，需要置为空，所以头指针就要等于空指针，更改了指针，就用到了二级指针。
3.链表还有两个及以上的节点：
void SLTPushBack(SLTNode** pphead, SLTDataType x) //尾插 { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { // 改变的结构体的指针，所以要用二级指针 *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } // 改变的结构体，用结构体的指针即可 tail->next = newnode; } } void SLTPopBack(SLTNode** pphead) //尾删 { // 1、空 assert(*pphead); // 2、一个节点 // 3、一个以上节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
5.7 单链表的在pos位置之前的插入
这里需要判断pos所在位置是否是头节点，如果是头节点就是头插；如果不是就正常的在pos位置之前插入就可以了
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//pos之前插入 { assert(pphead); assert(pos); if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } }
5.8 单链表的在pos位置之后的插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//在pos之后插入 { assert(pos); SLTNode* newnode = BuySListNode(x); pos->next = newnode; newnode->next = pos->next; }
5.9 单链表的删除pos位置的节点
如果pos是头，就需要头删
如果pos不是头，就正常删除。
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); //pos = NULL; } }
5.10 单链表的删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos) { assert(pos); // 检查pos是否是尾节点 assert(pos->next); SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; }
5.11 单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) //查找 { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
