一、链表的定义
1、定义
（1）n个结点离散分配
（2）彼此通过指针相连
（3）每个结点只有1个前驱结点，每个结点只有1个后续结点。首结点没有前驱结点，尾结点没有后续结点。
2、一些概念
结点：类似数组的元素，单个的逻辑上具有独立意义的个体。
每个结点的结构都相同。有效结点：存放有效数据的结点
首结点：第一个有效结点
尾结点：最后一个有效结点
头结点：不存放任何有效数据；它指向首结点；它的数据类型与其它结点的数据类型相同。
加头结点的目的：对链表进行操作时，在前面添加没有实际含义的头结点，可以方便我们对链表进行操作。头指针：指向头结点的指针变量
尾指针：指向尾结点的指针变量
3、确定一个链表需要几个参数？
1个参数：头指针。
因为通过头指针，可以推算出链表的其它所有信息。
因此，如果通过一个函数来对链表进行处理，我们至少需要接收链表的头指针信息。
4、每个结点的数据类型该如何表示？（如何模拟/表示一个结点）
每个结点可以分为2部分：数据域和指针域。
数据域中的数据可以非常复杂；指针域中的指针指向另外一个和它数据类型相同的结点。
（1）
typedef struct Node
{
int data; // 数据域
struct Node *pNext; //指针域
} NODE, *PNODE;
（2）
PNODE p = (PNODE)malloc(sizeof(NODE));
// 将动态分配的新结点的地址赋给p
（3）
free p; // 删除p指向结点所占的内存
// 不是删除p本身所占内存
（4）
p -> pNext; // p所指向结构体变量中的pNext成员本身
二、链表的分类
单链表
每个结点只有一个指针域，且该指针域只能指向后面的结点。双链表
每个结点有2个指针域。左边的指针域指向前面的结点，右边的指针域指向后面的结点。循环链表
能通过任何一个结点找到其他所有的结点。
尾结点的指针域指向了头结点。非循环链表
三、单链表的操作
创建链表
遍历链表
查找
清空
销毁
判断是否为空
求长度
排序
-
删除结点：删除p所指向的结点后面的结点
// 错误：
p->pNext = p->pNext->pNext; // 删除结点的内存就会被泄漏// 错误：
free(p->pNext); // 直接free掉这个结点，则它指向的结点也都找不到了。 -
插入结点：把q所指向的结点插到p所指向的结点后面
// 错误：
p->pNext = q;
q->pNext = p->pNext;// 方法1：先临时定义一个指向p后面结点的指针r
r = p->pNext; // r指向p后面的那个结点
p->pNext = q;
q->pNext = r;// 方法2：
q->pNext = p->pNext;
p->pNext = q;
