单链表的实现和典型操作
单链表的实现和典型操作可有很多。只讨论：创建、历、插入和删除；
以上操作需要相关一些指针，除“头指针”必须外，还需要一个或几个辅助指针。在操作过程中要知道哪个指针不变，哪个指针要变。
单链表的创建
- 创建带“头结点”单链表
-
从链尾向链头创建（反向创建，即“头插法”）
由于每次创建的新结点为当前链表实际的头结点，所以称为“头插法”。
image.png
操作需要“头指针”和一个辅助指针。即
LNode L,p;
第一步：创建专用的“头结点”（其数据域不用理睬）
L=(LNode *)malloc(sizeof(LNode));
L->next=NULL;
image.png
第二步：创建第一个结点（即当前的头结点，实际也是尾结点）
p=(LNode *)malloc(sizeof(LNode));
p->data=a[0];
p->next=L->next;//相当于p->next=NULL;
L->next=p;
image.png
第三步：创建第二个结点（实际是倒数第二个结点，也是当前的头结点）
p=(LNode *)malloc(sizeof(LNode));
p->data=a[1];
p->next=L->next;
L->next=p;
image.png
// 创建n个结点，数据由数组提供
void LinkListCreat1(LinkList L,ElemType a[],int n)
{
//L为头指针，p为协助指针
int i;
LinkList p;
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL){ printf(“申请空间失败！”);exit(0);}
L->next=NULL; // 生成“带”头的结点（对数据域不予理睬）
for(i=0;i<n;i++) {
p=(LNode *)malloc(sizeof(LNode));
//生成新结点（首次时建立尾结点）
if(p==NULL)
{printf(“申请空间失败！”);exit(0);}
p->data=a[i];
p->next=L->next;
L->next=p;
}
}
时间复杂度：O(n)
-
从链头向链尾创建（正向创建，即“尾插法”）
由于每次创建的新结点为当前链表的尾结点，所以称为“尾插法”。
image.png
操作需要“头指针”和两个辅助指针。即
LNode *L,*p,*r;
第一步：创建专用的“头结点”（其数据域不予理睬）
image.png
L=(LNode *)malloc(sizeof(LNode));
L->next=NULL;
第二步：创建第一个结点（尾结点也是实际的头结点）
image.png
r=L;
p=(LNode *)malloc(sizeof(LNode));
p->data=a[0];
p->next=NULL;
r->next=p;
r=p;
挪动r指针
image.png
第三步：创建第二个尾结点
image.png
p=(LNode *)malloc(sizeof(LNode));
p->data=a[1];
p->next=NULL;
r->next=p;
r=p;
挪动r指针
image.png
//创建n个结点，数据由数组提供
void LinkListCreat2(LinkList L,ElemType a[],int n)
{
//L为头指针，p,r为协助指针
int i;
LinkList p,r;
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL){ printf(“申请空间失败！”);exit(0);}
L->next=NULL;
// 生成“带”头的结点（对数据域不予理睬）
r=L;
for(i=0;i<n;i++)
{
p=(LNode *)malloc(sizeof(LNode));
if(p==NULL)
{printf(“申请空间失败！”);exit(0);}
p->data=a[i];
p->next=NULL;
r->next=p;
r=p;
}
}
时间复杂度：O(n)
