前言
我们知道了数据结构中线性表的概念，我们应该会感觉比较好理解，因为顺序表的建立主要涉及到结构体和动态内存管理函数，是类似于数组的一种形式。
我们要思考这样一个问题
1.增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
2.增容一般都是2倍扩容，有时候也会浪费一定的空间
于是，为了解决上面这样的问题，我们引入了线性表中的链表，这一概念。
一、链表是什么？
1.链表的概念和结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
图示如下：
由上图可知，链表的特征为：
1.链式结构在逻辑上是连续的，但是在物理上是不一定连续的。 （每一个结点的地址是不一定的）
2.现实中的结点一般都是从堆中申请出来的。
3.从堆上申请的空间，是按照一定策略来分配，根据编辑器的不同而不同，再次申请的空间可能连续，也可能不连续。
2.链表的分类
实际上链表的结构有很多中，以下组合起来有8种主要的链表结构的情况
1.单向或者双向
2.带头或者不带头
头节点使用的话，就不需要对其数据域赋值，只起到一个成为建立链表的基点的作用，不使用的话，第一个结点存储数值就可以，创建一个新节点给这个第一个结点phead即可，这样头节点链表，就变成了非头结点的链表
主要就是看第一个结点是否用到了其数值域
用第一结点数据域 非头节点
没用 头节点
3.循环或者非循环
以上这些类型情况，我们常用的有两种，无头单向非循环链表，带头双向循环链表
如图所示
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
二、链表的实现
1.无头单向非循环链表
结构体为：
typedef int SLDataType; //单向链表的实现、 typedef struct ListNode { SLDataType data;//数据域 struct ListNode* next;//指针域 }List;
要实现的函数为：
//打印单链表 void ListPrint(List* ps); //单链表的尾插 void ListPushBack(List** ps, SLDataType data); //单链表的头插 void ListPushFront(List** ps, SLDataType data); //单链表的尾删 void ListPopBack(List** ps); //单链表的头删 void ListPopFront(List** ps); //单链表的查找 List* ListFind(List* ps); //在pos位置上插入数据 void ListInsertBefore(List** ps, SLDataType x, List* pos); //在pos位置之后插入数据 void ListInsertAfter(List** ps, SLDataType x, List* pos); //在pos位子删除数据 void ListErase(List** ps, List* pos); //在pos位置之后一位删除数据 void ListEraseAfter(List* pos); //单链表的摧毁 void ListDestory(List** ps);
2.函数功能的实现
1.初始化和打印链表
//初始化链表 void InitList(List* ps) { ps->data = 0; ps->next = NULL; } //打印单链表 void ListPrint(List* ps) { List* cur = ps; while ((cur) != NULL) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULL\n"); }
2.头插和尾插
尾部插入图示如下：
代码如下：
//创建一个新节点 List* CreateNode(SLDataType x) { List* newNode = (List*)malloc(sizeof(List)); if (newNode == NULL) { perror("malloc fail\n"); exit(-1); } else { newNode->data = x; newNode->next = NULL; } return newNode; } //单链表的尾插 void ListPushBack(List** ps, SLDataType data) { //创建新的节点 assert(ps);//断言 List* newNode = CreateNode(data); if (*ps == NULL) { //说明是空链表 *ps = newNode; } else { List* tail = *ps; while (tail->next != NULL) { tail = tail->next; } tail->next = newNode; } }
头部插入如图所示：
代码如下：
//单链表的头插 void ListPushFront(List** ps, SLDataType data) { //先断言是否为空 assert(ps); //将新地址指向头结点下一个next结点的地址，然后在用头结点指向新节点 List* newNode = CreateNode(data); newNode->next = (*ps); //new指向ps当前的位置，然后new是第一个位置了，将new赋值给ps，这样new就作为头部连接链表了 (*ps) = newNode;//原本ps位置的数值不变，这样的话就成 new->next=ps,new数值在前，ps的数值在后 }
3.头删和尾删
尾部删除如图所示：
代码演示：
//单链表的尾删 void ListPopBack(List** ps) { assert(ps);//断言 //三种情况 //1.空链表 //2.一个节点 //3.多个节点 if (*ps == NULL) { return; } //只有一个节点的情况为 else if ((*ps)->next == NULL) { free(*ps); //如果只有一个头节点的话 *ps = NULL; } else { //多个节点的情况下、 List* tail = *ps; while (tail->next->next!= NULL) { tail = tail->next; } free(tail->next); tail->next= NULL; } }
头部删除如图所示：
代码如下：
//单链表的头删 void ListPopFront(List** ps) { assert(ps); //1.空 //2.非空 if (*ps == NULL) { //为空 return; } else { List* tail = (*ps)->next;//创建临时变量tail，将头节点之后的地址给tail free(*ps);//滞空头节点 *ps = NULL;//可有可不有，接下来也要用 *ps = tail;//将tail也就是ps的下一个List节点给ps } }
4.单链表的查找
代码如下：
//单链表的查找 List* ListFind(List* ps,SLDataType data) { //进行查找就是进行判断是否为空链表，为空直接返回 if (ps == NULL) { printf("链表为空、无法查找\n"); return; } List* tail = ps; while (tail != NULL) {//从头节点开始，进行循环， if (tail->data == data) { return tail; } tail = tail->next; } return tail;//最后还找不到data，tail就为NULL了 }
5.在pos结点位置之前或之后插入数据
在pos结点位置之前插入数据，如图所示：
代码如下:
//在pos位置上插入数据 void ListInsertBefore(List** ps, SLDataType x, List* pos) { //先判断是否为空 assert(ps); assert(pos); //空链表排除 //1.pos是第一个节点 //2.pos不是第一个节点 if (*ps == pos) { //是第一个节点，那就直接头插 ListPushFront(ps, x); } else { List* prev = *ps; while (prev->next != pos) { prev = prev->next; } List* newnode = CreateNode(x); prev->next = newnode; newnode->next = pos; } }
在pos结点位置之后插入结点，如图所示：
代码如下：
//在pos位置之后插入数据 void ListInsertAfter(List** ps, SLDataType x, List* pos) { assert(ps); //assert(pos);//断言 List* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; }
