目录
关于链表：以下文章仅仅代表我自己的看法，如果哪有不对还请各位大佬批评指出问题所在，互相交流，互相学习！！！
一、链表的简单理解与引入
1.1 链表的引入
首先！！！链表与顺序表的区别是顺序表在物理空间上和逻辑上都是连续的，而对于链表来说，链表在物理上不一定连续，因为其保存的元素是空间通过malloc从堆空间上申请出来的，而malloc在一次中申请多个空间是连续的，如果是多次申请的话就不是连续的。但是！！链表在逻辑上是连续的。
1.2 节点的理解
在链表中，用来保存元素的一段空间（这里边有俩个元素，一个是这个元素的值，一个是下一个元素的空间地址）。
1.3 链表的分类
链表主要有单向和双向、带头和不带头、循环和不循环三类，这三类通过组合就产生了8中链表情况。
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
虽然但是有这么多链表，我们最最最最常用的就是“无头单向非循环链表”和“带头双向循环链表两种”！！！！大家只要把这俩种弄懂，那么其他的也就差不多了
无头单向非循环链表：
带头双向循环链表
注：无头单向非循环链表结构简单，一般不会单独用来存储数据，但是它会跟随其他的结构，作为它的子结构，这种链表种类在面试中考的比较多。而带头双向循环链表在实际中使用的比较多一些，它结构比较复杂，但是优势也是比较大的。
二、常用链表功能的实现
2.1 首先是节点的定义，
链表嘛，就是一个个节点串起来的。如2.1所见，节点就是俩个变量，一个是值域，一个是下一个节点的地址，我们只需要把它定义出来就行！！！如：
typedef int DataType;//这里是吧变量类型重新命名了，方便修改
typedef struct SListNode//这个是节点的定义
{
DataType data;
struct SListNode* next;
}SListNode; //这里为它重新命名了，方便后边使用，否则每次都得加上struct
2.2 节点的创建
这里没啥难的，大家可以去看看malloc的用法。
SListNode* BuySListNode(DataType x) {
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//这里是给这个新的节点在堆上申请了一处空间
if (newnode == NULL) //这个就是申请空间失败了，即节点创建失败
{
printf("创建节点失败！！");
exit(0);
}
newnode->data = x; //将参数x保存到值域
newnode->next = NULL; //在没有串起来的时候，将下一个地址保存为NULL
return newnode; //将新创建的节点保存起来
}2.3 单链表的尾插
尾插说白了就是找到最后一个元素，然后将它指向我们要插入的这个节点就行。但是注意要分情况，链表为空和链表不为空
assert: assert是一个调试宏，即assert是一个宏，这个宏只在debug模式下有效assert是断言，assert(表达式)，表达式的结果是真或者假；如果assert内部的表达式为真，assert就不会触发，程序可以继续往下执行如果assert内部的表达式为假，assert就触发，assert就会中断程序的执行---弹出一个窗口因此：assert是用来断言非法情况的，即当assert触发了之后，程序一定是处于非法的状态if(表达式)：当表达式为假，程序处于合法的情况，就使用if来检测条件链表不存在：根本就没有链表，就不能对链表进行任何操作 ----当往链表中插入或者删除元素时候，将链表不存在视为非法情况空链表：链表中没有插入任何节点---合法情况
*/
//单链表的尾插
void SListPushBack(SListNode** pplist, DataType x)
{
assert(pplist); //保证品牌pplist这个链表存在
if (*pplist == NULL) //如果链表首地址为空，说明这块插入的节点就充当这个单链表的第一个元素
*pplist = BuySListNode(x);
else { //如果链表中还有其他的元素，这时候需要找到链表的最后一个元素，将他的next地址指向我们插入的这个节点
SListNode* cur = *pplist; //要进行遍历，故构建了一个相同类型的变量
while (cur->next) //如果是最后一个元素，这个元素的下一个就会为空，跳出循环
{
cur = cur->next; //相当数组中的i++
}
cur->next = BuySListNode(x); //跳出循环说明他是最后一个元素了。将它指向我们要插入的元素就行啦
}
}2.4 单链表的尾删
找到最后一个元素，让他的上一个元素指向NULL，注意要释放空间（free）。有两个注意，一个是注意控制最后一个元素和倒数第二个元素的移动，第二个是注意分类，下面代码的第二个else和第三个else可以直接合并为第三个一种情况。
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(pplist);
if (*pplist == NULL)
return;
else if((*pplist)->next==NULL) { //若链表只有一个元素的时候，将他释放掉，再讲链表的首地址指向NULL，否则会造成野指针的产生
free(*pplist);
*pplist = NULL;
}
else {
SListNode* cur = *pplist; //用来遍历数组
SListNode* prev = NULL; //保存上一个元素的地址
while (cur->next)
{
prev = cur;
cur = cur->next;
} //当cur为最后一个的同时，prev刚好是倒数第二个，想不来的用
free(cur); //123456自己推一下就懂啦
prev->next = NULL;
}
}2.5 单链表的头插
注意最后更新*pplist的值
// 单链表的头插
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
if ((*pplist) == NULL)
{
*pplist = BuySListNode(x);
}
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}2.6 链表的头删
注意：每个删除都需要提前保存这个节点，然后将这个节点释放
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(pplist);
if ((*pplist) == NULL)
{
return;
}
SListNode* cor = *pplist;
*pplist = cor->next;
free(cor);
}
2.7 单链表的查找
这个和数组的查找没啥区别，主要变通就行
// 单链表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
assert(plist);
if (plist == NULL)
{
return NULL;
}
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}2.8 删除pos后边的值
注意条件与地址保存释放就行
//删除pos之后的值
void SListEraseAfter(SListNode* pos) {
if (pos == NULL || pos->next == NULL) //如果pos是空或者他是最后一个元素，都不能进行尾删
{
return;
}
SListNode* cur = pos->next; //保存next的地址，以便释放
pos->next = cur->next;
free(cur);
}2.9 在元素pos后插入x
这里注意链接链表的先后就行，这样的好处是2的位置不容易遗失
//在某个元素之后插入X
void SListInsertAfter(SListNode* pos, DataType x) {
if (pos == NULL)
return;
else {
SListNode* cur = BuySListNode(x);
cur->next = pos->next;
pos->next = cur;
}
}2.10 链表的销毁
注意点与上一个相同，要先保存下一个元素的地址，要不会造成地址遗失。
//链表的销毁
void SListDestroy(SListNode** plist)
{
assert(plist);
SListNode* cur = *plist;
while (cur)
{
*plist = cur->next;
free(cur);
cur = *plist;
}
plist = NULL;
}（链表相关oj题解答看下一章）