线性表的链式表示
单链表的定义
线性表的链式存储称为单链表；
每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继结点的指针；
data为数据域，存放数据；next为指针域，存放指针
单链表中结点类型的描述
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*Linklist;
- 顺序表需要大量连续存储空间，单链表克服了这一缺点，即存储空间不一定要连续
- 但是单链表相对于顺序表多了指针域，因此有浪费空间的缺点
- 单链表的元素是离散地分布在存储空间的，所以无法实现随机存取，寻找特定的结点必须从表头开始遍历，依次查找
头指针与头节点
通常用头指针来标识一个单链表，如单链表L；特别地，头指针为NULL时表示一个空表
为了操作上的方便，在单链表主体的第一个结点前加一个结点，称为头结点；头结点的数据域可以记录表长等信息，也可以不记录任何信息
头指针和头节点的区别
- 头指针始终指向链表的第一个结点，无论头结点是否存在
- 头结点是带头结点链表的第一个结点
引入头结点带来的优点
- 由于开始结点的位置被存放在头结点的指针域中，所以链表第一个位置的操作和其他位置相同（链表的第一个有效位置实际上是第二个结点）
- 引入头结点后，无论链表是否为空，头指针都指向头结点的非空指针；否则空链表与非空链表的处理不同
单链表上基本操作的实现
单链表上的主要操作主要有建立（头插法、尾插法）、查找（按序号、按值）、插入结点、删除结点、求表长
采用头插法建立单链表
LinkList List_HeadInsert(LinkList &L){
LNode *s;int x;
L = (Linklist)malloc(sizeof(LinkList)); //创建头结点
L->next = NULL; //头结点指针为空，初始化为空链表
scanf("d",&x); 输入（第一个）结点的值
while(x != 9999){ //结束条件（如输入9999）
s = (LinkList)malloc(sizeof(LinkList)); //创建一个新结点
s->data = x;
s->next = L->next;
L->next = s; //插入过程
scanf("d",&x);
}
return L;
}
- 头插法建立单链表时，读入数据的顺序和链表中元素的顺序是相反的
- 每个结点插入的时间为O(1)
- 设单链表长为n，则头插法生成单链表的总时间复杂度为O(n)
采用尾插法建立单链表
头插法虽然简单，但是输入顺序和生成链表中结点的顺序相反；尾插法将新结点插入当前链表的表尾，为此必须增加一个尾指针，使其始终指向当前链表的尾结点；时间复杂度与头插法相同
Linklist List_TailInsert(Linklist &L){
int x; //设元素类型为整型
L = (LinkList)malloc(sizeof(LNode));
LNode *s,*r = L; //r为表尾指针
scanf("%d",x); //输入结点的data域值
while(x != 9999){ //结束条件（如输入9999）
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s; //r指向下一个表尾结点
r = s; //r再次成为表尾指针
scanf("%d",x);
}
r->next = NULL; //尾结点指针为空
return L;
}
按序号查找结点值
LNode *GetElem(LinkList L,int i){
int j = 1; //计数器，初始化为1
LNode *p = L->next; //将头结点的指针赋值给p
if(i == 0)
return L;
if(i <= 0)
return NULL;
while(p&&j < i){ //从第1个结点开始，查找到第i个结点
p = p->next;
j++;
}
return p; //返回第i个结点的指针
}
- 按序号查找结点的时间复杂度为O(n)
按值查找表结点
从单链表第一个结点开始，依次比较各个结点中数据域的值；如果链表中某结点数据域的值等于给定值e，则返回该结点的指针；若没有这样的结点，则返回NULL
LNode *LocateElem(LinkList L,ElemType e){
LNode *p = L->next;
while(p != NULL&&p->data != e) //p后面无结点或该结点的data域等于被查找对象时跳出循环
p = p->next;
return p; //找到后返回p，否则返回NULL
}
插入结点操作
插入节点操作将值为x的新结点插入到单链表的第i个位置上；先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点
调用序号查找算法GetElem(L,i-1),查找第i-1个结点
假设返回的第i-1个结点为 *p，令新结点 *s的指针域指向 *p的后继结点
令 *p的指针域指向新插入的结点 *s
1 p = GetElem(L,i-1);
2 s->next = p->next;
3 p->next = s;
- 2句和3句的顺序不能颠倒，否则s将指向自己，显然是错误的
- 算法的主要时间开销在查找第i-1个元素，算法时间复杂度为O(n),插入操作的时间复杂度仅为O(1)
对某一结点实现前插操作
以上面的算法为例，前插操作可以转化为后插操作，但需要调用GetElem函数找到第i-1个结点，而查找第i-1个元素的时间复杂度为O(n)
对于已知结点，可以采取另外一种方式进行前插转换为后插的操作；设待插入结点为 *s,将其插入到 *p的前面，我们仍然可以将其插入到 *p的后面，将p->data与s->data交换，这样既满足了逻辑关系，又能使算法时间复杂度降为O(1)
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;
删除结点操作
删除结点操作是将单链表的第i个节点删除；假设结点 *p为被删除结点 *q的前驱节点，仅需修改 *p的指针域，将 *p的指针域next指向 *q的下一结点
p = GetElem(L,i-1);
q = p->next;
p->next = q->next;
free(q);
- 和插入算法一样，该算法的时间主要耗费在查找上，因此算法的时间复杂度为O(n)
删除结点*p
删除结点 *p，通常的做法是用GetElem找到 *p的前驱节点，然后再执行删除操作，时间复杂度为O(n)
实际上，也可以通过删除 *p的后继结点的方法实现；将其后继结点的值赋给它，并且删除后继结点，可以使算法的时间复杂度降为O(1)
q = p->next;
p->data = q->next->data;
p->next = q->next;
free(q)；
求表长操作
求表长操作就是计算单链表中数据结点（不带头结点）的个数；遍历+计数器，算法的时间复杂度为O(n);不带头结点和带头结点的单链表处理不同；对不带头结点的单链表，当表为空时要单独处理
