一、链表介绍
????????链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。（引自百度百科）
二、单链表
? ? ? ? n个节点链接成一个链表，即为线性表的链式存储结构。又由于此链表的每个节点中只包含一个指针域，故又称线性链表或者单链表。
????????指针为数据元素之间的逻辑关系的映像，则逻辑相邻的两个数据元素其存储的物理地址可相连也可不相连。
???????????? ? ? ? ??
????????单链表的存储结构：
typedef struct LNode
{
ElemType data; //定义数据域
struct LNode *next; //用相同的数据类型定义一个指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型在使用时，一般会在单链表的第一个节点之前设置一个头节点。
在这里要弄清楚头指针，头节点，首元节点
? ? ? ? 头指针：指向链表中第一个节点的指针。
? ? ? ? 头节点：在首元节点之前附设的一个节点，指针域指向首元节点，一般数据域不储存数据，或者根据自己需要存储一些附加信息。?
? ? ? ? 首元节点：链表中存储的第一个数据元素a1的节点。
? ? ?
判断单链表是否为空表：
? ? ? ? 无头结点：L==NULL
? ? ? ? 有头节点：L->next==NULL?
????????
单链表的初始化：
Status InitList(LinkList &L)
{
L=new LNode; //生成新节点作为头节点，用头指针L指向头节点
L->next=NULL; //头指针的指针域置空
return OK;
}单链表的取值：
Status GetElem(LinkList L,int i,ElemType &e) //用e返回取到的第i个数据元素的值
{
p=L->next;j=1; //初始化，p指向首元节点，计数器j赋初值1
while(p&&j<i)
{
p=p->next; //p指向下一个节点
++j; //计数器加1
}
if(!p||j>i) return ERROR; //i值不合法，i<=0或者i>n
e=p->data;
return OK;
}单链表的插入：
? ? ? ? 和取值操作有相同之处，就是遍历，在第i个节点插入元素，所以我们要找到第i-1个节点，找到之后进行如下操作
s->next=p->next; //将新节点s和第i-1个节点之后的链连接起来
p->next=s; //将第i-1个节点和s连接起来????????有一点需要注意的是在操作的时候，这两步的顺序不能颠倒，不然会丢失第i个节点的地址，导致插入失败。
单链表的删除：
? ? ? ? 和取值操作有类似，先循环找到要删除元素前一个元素，然后做如下操作
q=p->next; //用一个变量q存储要删除节点i的地址
p->next=q->next; //p原本指向第i个节点，先直接略过i指向i+1
free(p); //释放第i个节点的内存
三、循环链表
? ? ? ? 循环链表是一种特殊的单链表，其特点是表中最后一个元素的指针域指向头节点，整个链表连成一个环。
单链表中遍历的终止条件是p！=NULL或者p->next！=NULL
循环单链表的遍历终止条件是p！=L或者p->next！=L
四、双向链表
双向链表的节点中有两个指针域，一个指向直接后继，一个指向直接前驱，存储结构如下：
typedef status DulNode
{
ElemType data; //定义数据域
struct DulNode *prior; //定义直接前驱
struct DulNode *next; //定义直接后继
}DulNode,*DulLinkList;双向链表的插入：
????????与之前遍历找节点一样，找到第i个节点的位置，然后进行如下操作接入链表
s->prior=p->prior; //s的直接前驱指向第i-1个节点
p->prior->next=s; //第i-1个节点的next指向s
p->prior=s; //p直接前驱指向s
s->next=p; //s的next指向p? ? ? ? 类似的可以做到双向链表的删除：
p->prior->next=p->next; //第i-1个节点的直接后继指向第i+1个节点
p->next->prior=p->prior; //第i+1个节点的直接前驱指向第i-1个节点
free(p); //释放第i个节点总之，在双向链表中利用好 p->prior->next=p和p->next->prior=p就行了