一、链表的简单理解与引入
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题解答看下一章）
