> 上一篇博客学习了顺序表，最后也说明了顺序表属于静态存储，数据元素的个数不能自由的扩充。为了解决这个问题我们引入了链表
### 链表存储结构
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻，因此线性表的链式表示又称为非顺序映像或链式映像。
### 各个结点有两个域组成：
* 数据域:存储元素数值数据
* 指针域：存储直接后继结点的存储位置
### 名词解析
1. 结点：数据元素的存储映像。有数据域和指针域两部分组成。
2. 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
3. 单链表、双链表、循环链表：
* 结点只有一个指针域的链表，称为单链表或线性链表
* 有两个指针域的链表，称为双链表
* 首尾相接的链表称为循环链表
4. 头指针是指向链表中第一个结点的指针
5. 首元结点是指链表中存储第一个数据元素a1的结点
6. 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（可无）
当头结点的指针域为空时表示空表
头结点不能计入链表长度值
### 单链表的定义和实现
非空表
空表
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名
若头指针名是L，则把链表称为表L
单链表的存储结构定义
~~~
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; //*LinkList为Lnode类型的指针
~~~
注意：
指针变量p：表示结点地址
结点变量*p：表示一个结点
### 单链表基本操作的实现
#### 1.初始化(构造一个空表)
【算法思想】
(1)生成新结点作为头结点，用头结点L指向头结点。
(2)头结点的指针域置空。
【算法描述】
~~~
Status InitList_L(LinkList &L)
{
L=new LNode;
L->next=NULL;
return OK;
}
~~~
#### 2.查找
##### （1）按序号查找
【算法思想】
从链表的第一个结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点，p的初始值指向第1个结点（p=L->next）。用j做计数器，累计当前扫描过的结点数，j的初值为1，当p指向扫描到的下一个结点时，计数器j相应加1.当j=i时，p所指向的结点是想要找的第i个结点。
【算法描述】
~~~
Status GetElem_L（LinkList L，int i，ElemType &e）
{
p=L->next;j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR;
e=p->data;
return OK;
}
~~~
#### 按值查找
【算法思想】
链表中查找其值与给定e相等的数据元素的过程和顺序表类似，从第一个结点起，依次和e相比较，如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”；如果查遍整个链表都没有找到其值和e相等的元素，则返回“NULL”。因此需要设置一个指针变量p顺链扫描，直至p为“NULL”，或者p->data和e相等为止。
【算法描述】
~~~
LNode *LocateElem_L(LinkList L,ElemType e)
{
p=L->next;
while(p&&p->data!=e)
{
p=p->next;
}
return p;
}
~~~
### 3.插入
【算法思想】
将值为e的新结点插入到表的第i个结点的位置上，即插入到结点ai-1与ai之间，分为一下几步：
1. 找到结点ai-1并由指针p指向该结点。
1. 生成一个新结点*s。
1. 将新结点*s的数据域置为e。
1. 将新结点*s的指针域指向结点ai。
1. 令结点ai-1的指针域指向新结点*s。
【算法描述】
~~~
Status ListInsert_L(LinkList &L,int i,ElemType e)
{
p=L;j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1)
return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
~~~
### 4.删除
【算法思想】
要删除单链表的第i个结点ai，分以下几步：
1. 找到结点ai-1并由指针p指向该结点。
2. 临时保存待删除结点ai的地址在q中，以备释放。
3. 令p->next指向ai的直接后继结点。
4. 将待删除结点ai的值保留在e中
5. 释放结点ai的空间。
【算法描述】
~~~
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;++j;
}
if(!(p->next)||j>i-1)
return ERROR;
q=p->next;
e=q->data;
delete q;
return OK;
}
~~~
### 5.创建单链表
#### （1）前插法
【算法思想】
前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表。首先建立只有一个头结点的空链表，每读入一个数据元素则申请一个新结点，并将新结点插入到头结点之后。
【算法描述】
~~~
void CreateLst_F(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
for(i=n;i>0;--i)
{
p=new LNode;
cin>>p->data;
p->next=L->next;L->next=p;
}
}
~~~
#### (2)后插法
【算法思想】
后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，首先要创建一个只有头结点的空链表L，不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点，初始化时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点*r之后，然后使r指向新的尾结点。
【算法描述】
~~~
void CreateList_L(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i<n;++i)
{
p=new LNode;
cin>>p->data;
p->next=NULL;r->next=p;
r=p;
}
}
~~~
### 循环链表
循环链表是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
两个线性表合并成一个表，将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。
~~~
p=B->next->next;
B->next=A->next;
A->next=p;
~~~
