1.个人人为，链表和顺序表最大的差别，即是链表可以描述各元素间的逻辑关系
链表有一个个结点构成，每个结点有两部分：数据域+指针域
2.一般的，可以理解为【链表=头结点+首元结点+其它结点】构成，或者
【链表=首元结点+其它结点】构成（链表不一定有头节点）
如下图所示：
3.链表的分类：单链表，双链表，循环链表
二.单链表操作的引入1.首先我们定义一个带头节点的指针
2.1 【带头节点的链表定义】
typedef Struct Lnode{ //声明结点
ElemType data; //结点的数据域
Struct Lnode *next; //结点的中指针域
}Lnode,*LinkList; //LinkList为指向结构体Lnode的指针类型
对于这个结构体的理解有点容易把人搞昏，我用自己的话表达一下。在结构体的末尾有Lnode,*LinkList，均是代表“类型”，而这里的类型可以理解为int型，float型，只是这里类型里面的，是代表一个结构体，且是一个指针类型。把这里搞清楚以后，这个结构体typedef的是struct Lnode作为结构体名，那么在结构体的末尾又出现了一个Lnode，这里用到了嵌套，那么指针*LinkList即会指向下一个仍含有data和next的结构体。
注：之前文章有同学私信我问typedef加到这里的意思，其实这里用typedef之后，就可以用Lnode来代替结构体。
2.操作链表L：
2.1定义链表L： LinkList L； //定义一个头指针，指向某一个链表
2.2定义结点指针p：Lnode *p；或LinkList p； //虽然两者意义相同，但当用于指向结点时，个人认为用Lnode *p会更好
3.实例
我们用一个存储学生学号，姓名，成绩的单链表的例子，可以让大家初步认识链表并理解之前讲到的关于结构体的内容
2.2【存储学生学号，姓名，成绩的单链表】
typedef Struct student{
char num[8]; //数据域
char name[8]; //数据域
int score; //数据域
Struct student *next //指针域
}Lnode,*LinkList; //*LinkList指针就会指向跟Lnode一个类型包含这四项的结构
另一种表示，也是更常用的操作，就是先定义一个结构体存储数据项，然后再定义一个结构体有data，next形成链表的结构。
typedef Struct{
char num[8]; //数据域
char name[8]; //数据域
int score; //数据域
}ElemType;
typedef Struct Lnode{
ElemType data; //数据域
Struct Lnode *next; //指针域
}Lnode,*LinkList
上一篇文章讲到，ElemType不是具体的哪一种类型，而是要靠你自己定义一个名称，这个你自己定义的类型，就是代表含有char num，char name，int score这三个数据项的一种结构体类型
三.单链表操作的实现1.初始化
算法：生成新的结点作为头节点，用头指针L指向头节点,将头节点的指针域置空（即next域）
2.3【单链表的初始化】
Status InitList_L(LinkList &L){ //首先构造一个函数
L=（LinkList）malloc(sizeof(Lnode)); //动态分配内存
L->next=NULL; //next域指针置为空（相当于初始化）
return OK;
}
这里就不得不提到malloc函数；（LinkList）malloc(sizeof(Lnode))
分配内存的大小：sizeof（Lnode）
（*LinkList）的含义：强制类型转化，将分配的内存用于该结构
2.判断链表是否为空
算法：判断头节点的指针域是否为空
2.4【判断链表是否为空】
int ListEmpty(LinkList L){ //判断是否为空表，如果是，返回值为1
if(L->next==NULL)
return 1;
else
return 0；
}
3.单链表的销毁（注意：链表销毁后不存在）
算法：从头指针开始，依次释放所有结点（要让指针指向哪一结点，即将那一结点的地址赋给他）即让L指向下一结点：将next域赋值给L（即L=L->next;),并且这里引入新的指针接受L的地址（防止地址丢失后找不到下一个结点） 循环条件：L！=NULL
2.5【单链表的销毁】
Status DestroyList_L(LinkList,&L){
Lnode *p; //或LinkList p;这个的意思是定义结点指针p
while（L!=NULL){
p=L; //用P保存L指向位置的地址（从头节点开始）
L=L->next; //L指针指向下一个结点
delete p; //删除p所处位置的结点
}
return OK;}
4.清空链表（链表任然存在）
算法：依次释放所有结点，并将结点指针域设置为空
与销毁最大的不同：p指针指向的开始位置不同！ 这里是p=L->next，是从首元结点开始的，而删除是p=L,是从头节点开始的引入q指针指向p后面的一个结点，防止清空p后找不到下一个结点，q=p->next;然后再删p即可。
2.6【清空单链表】
Status ClearList(LinkList &L){
Lnode *p,*q; //定义结点指针
p=L->next; //让p指向首元结点
while(p!=NULL){
q=p->next; //q指向p的下一个结点
delete p; //删除p指向的结点
p=q; //删除后p，q再次指向同一结点
}
L->next=NULL; //将头节点的指针域也置为空
return OK；
}
5.求链表的表长
算法：从首元结点开始，依次计数所有结点（不是从头节点开始）
p=p->next 并判断是否为空 p==NULL
2.7【求链表的表长】
int ListLength_L(ListList &L){
Lnode *p; //先创建一个结点指针p
p=L->next; //让p指向首元结点（注意不是头节点）
i=0
while(p==NULL){
i++;
p=p->next; //p指向下一个结点
}
return i;}
四.重要操作
1.取值操作：取单链表中第i个元素的内容
算法：从头指针开始延链表一个个到第i个结点为止（因此这里可以说明，链表不是随机存取）
初始：p=L->next 还需要引入变量j作为计数器
2.8【单链表的取值操作】
Status Getelem_L(LinkList L,int i,Elemtype &e){//获取线性表L中第i个位置的内容，并通过变量e返回
p=L->next; //初始化，令p从首元结点开始
j=1;
while(p!=NULL&&jnext; //p向下一个结点扫描，直到p指向第i个元素或P为空
j++;
}
if(p==NULL||j>i) return ERROR;//代表第i个元素不存在
e=p->data; //取第i个元素（第i个结点的data域）
return OK;
}//Getelem_L
2.按值查找：根据指定数据获取该数据(设所找的数据值为e）所在位置
算法：从第一个元素开始，p=L->next 比较：p->data!=e 再移动指针的位置p=p->next
没有找到（结束条件）p==NULL
2.9【单链表按值查找】
Lnode *LocateElem_L(LinkList L，Elemtype e){
//在线性表L中查找值为e的元素
//找到了，则返回L中值为e的数据元素的地址，查找失败则返回NULL
p=L->next;
while(p!=NULL&&p->data!=e){
p=p->next;
}
return p; //找到了p本身就是值，没找到它就变成了NULL
}
3.插入操作：在第i个结点前插入值为e的新结点
那么如果要插i这个地方，首先要找到i-1这个结点，再在后面生成新结点，并令data域为e
现在p指针指向ai-1的位置，那么p->next域则代表ai这个结点，那么插入语结点后，则s结点s->next即为ai,所以可以通过赋值得：s->next=p->next,好的，现在让 ai-1的后面不是ai而是s指向的新插入的结点，所以第二步关键操作时p->next=s。
2.10【单链表的插入操作】
Status ListInsert_L(LinkList &L,int i,ElemType e){
p=L;j=0;
while(p!=NULL&&jnext;
j++;
}
if(p==NULL||j>i-1) return ERROR; //插入位置非法
s=new Lnode; //生成新结点s（这里偷懒没有用malloc
s->data=e //设s的数据域为e
s->next=p->next;
P->next=s; //将s插入L中
return OK;
}//ListInsert_L
4.删除第i个结点
算法：找到第i-1个结点（用p指针指向），令ai-1结点的后一个结点是ai+1（因为要删除ai），故有：p->next=p->next->next(因为p指向的是ai-1位置，因此p->next->next代表ai+1），现在引入q来保存ai的地址并释放，上述式子亦可改为：p->next=q->next;
2.11【删除第i个结点】
Status ListDelete_L(LinkList &L,int i,ElemType &e){//删除i位置的结点，并用e保存删除结点的数据域
p=L,j=0,i,q; //这里没有详细定义了
while(p->next!=NULL&&jnext; //p指针指向i-1这个位置
j++;
}
if((p->next)==NULL||j>i-1) return ERROR; //删除位置不合法
q=p->next; //q指向i位置
P->next=q->next; //让ai-1的下一个结点是a1+1
e=q->data; //用e保存i位置的data
delete q; //删除结点
return OK;}
五.单链表的建立
1.头插法：从一个空表开始，重复读入数据，生成新结点，将读入的数据存到新结点的数据域中，从最后一个结点开始，依次将各结点插入到链表的前端（头节点）（这里可能有点抽象，下面给大家具体讲解一下）
算法：
设要插入的元素是：a1,a2,a3......an 思路：头结点-新节点-老结点（所有的老结点）
插入顺序是：an,an-1......a1
step 1：建立一个头节点
L=(LinkList)malloc(sizeof(Lnode)); L->netx=NULL; //创立头节点并将头节点指针域置为空
step 2：从最后一个元素开始创建新结点
p=(LinkList)malloc(sizeof(Lnode)); p->data=an; //创立结点指针并将数据域保存最后一个元素
step 3：将新结点（an）放在头节点后
p->next=L->next； L->next=p； 这一步有很多同学都难以理解，首先我们要明白，无论是第一个还是后面的结点，我们插入新节点时，永远都是放在头节点的后面，老结点的前面（老节点就是L->next),因此这里把L头结点的next域赋值给p指向结点的next域使得插入结点在老节点前，再有：L->next=p使得新节点在头节点后。
step 4：同理就轮到an-1插入了
p=(LinkList)malloc(sizeof(Lnode)); p->data=an-1; p->next=L->next； L->next=p；
然后循环step 3和step 4
2.12【头插法创建单链表】
void CreatList_L(LinkList $L,int n){
L=new Lnode; //用malloc也可以,反正就创建结点指针嘛
L->next=NULL; //这两步是创建头节点
for(i=n;i>0;i--){ //从最后一项开始插入
p=new Lnode; //创建结点指针
scanf(&p->data) //接受输入的元素值
p->next=L->next; //让新结点插入到以前的结点之前
L->next=p; //让新结点插入到头节点之后
}
}//CreatList_L
2.尾插法
算法：从空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点，初始时，r同L共同指向头节点，每读入一个元素，则申请一个新结点，将新结点插入到尾结点后，r指向新节点（这时新结点所处位置在表尾），然后循环下去。
2.13【尾插法创建单链表】
void CreatList_L(LinkList &L,int n){
L=(LNode*)malloc(sizeof(LNode)); //这里用new用malloc全凭个人
L->next==NULL; //这两步还是创建头节点
r=L; //尾指针r指向头节点
for(i=0;i<=n,i++){
p=(LNode*)malloc(sizeof(LNode)); //创建结点指针
scanf(&p->data); //接受输入元素值
p-next==NULL; //结点指针域置空（理解为初始化）
r->next=p //r结点的next域就是新插入的结点
r=p; //再把r指针的位置指向表尾
}
}//CreatList_L
好了，这就是单链表最基本的所有操作了，下一期会为大家介绍循环链表以及双向链表
感谢各位阅读！
