顺序表插入、删除时需要通过移动数据来实现，影响了执行效率。
而链表不要求逻辑上相邻的两个数据元素物理上也相邻，因此对线性表的插入、删除不需要移动数据元素，只需要修改链。
下面介绍带头结点的链式表：
数据结构：
typedef int ElementType;typedef struct LNode * PtrToLNode;struct LNode{ElementType Data;PtrToLNode Next;};typedef PtrToLNode Position;//这里的位置是结点的地址 typedef PtrToLNode List;
1.初始化：
//初始化List MakeEmpty(){List L;L = (List)malloc(sizeof (struct LNode));if (!L)exit (-1);L->Next = NULL;return L;}
2.求表长
在顺序存储表示的线性表中求表长是一件很容易的事，直接返回Last+1值就可以了，但是在链式存储表示中，需要将链表从头到尾遍历一遍；设一个移动的指针p和计数器cnt，初始化后，p从表的第一个结点开始往后移，同时计数器cnt+1.
//求表长int Length(List L){Position p;int cnt = 0;p = L->Next;while(p){p = p -> Next;cnt++;}return cnt;}
3.查找（按序号查找FindKth）
对于顺序存储，按序号查找是很直接的事，要得到第k个元素的值，直接取L->Data[k-1]就可以了。而对于链式表就需要采用求表长的思路，从头遍历，判断当前结点是否是第K个，若是，返回该结点的值，否则继续后一个。
//根据指定的位序查找sint FindKth(List L,int K){Position p;int cnt = 1;//位序从1开始 p = L->Next; while(p&&cnt<K){p = p-> Next;cnt++;}if((cnt==K)&&p) printf("您查找的数为：%d\n",p -> Data);else printf("您查找数不存在");}
4.查找（按值查找Find）
按值查找的方法也是从头到尾遍历，直到找到为止
//按值查找 Position Find(List L,int X){Position p;p = L->Next; while(p&&p->Data!=X){p = p-> Next;}if(p) printf("查找成功，您查找的数为：%d\n",p->Data);else printf("您查找数不存在");}
5.插入
带头结点的链式表的插入
//插入List Insert(List L ,ElementType X,int i){Position tmp,pre;int cnt =0 ;pre = L;while(pre&&cnt<i-1){pre = pre->Next;cnt++;}if(pre==NULL||cnt!=i-1){printf("插入位置参数错误\n");}else{tmp = (Position)malloc(sizeof(struct LNode));tmp->Data=X;tmp->Next=pre->Next;pre->Next=tmp;}}
6.删除
删除指定位序i的元素，首先需要找到被删除结点的前一个元素,然后再删除结点并释放空间。
//删除bool Delete(List L,int i){Position tmp,pre;int cnt = 0;pre = L;while(pre&&cnt<i-1){pre=pre->Next;cnt++;}if(pre==NULL||cnt!=i-1||pre->Next==NULL){printf("删除位置参数错误");}else{tmp = pre->Next;pre->Next = tmp->Next;free(tmp);printf("删除成功"); }}
7.遍历链表并输出
void DisLinkList(List L){List p = L->Next;printf("输出链表： "); while (p){printf("%d ", p->Data);p = p->Next;}}
完整的程序代码：
#include<stdio.h>#include<stdlib.h>typedef int ElementType;typedef struct LNode * PtrToLNode;struct LNode{ElementType Data;PtrToLNode Next;};typedef PtrToLNode Position;//这里的位置是结点的地址 typedef PtrToLNode List; //初始化List MakeEmpty(){List L;L = (List)malloc(sizeof (struct LNode));if (!L)exit (-1);L->Next = NULL;return L;} //根据指定的位序查找int FindKth(List L,int K){Position p;int cnt = 1;//位序从1开始 p = L->Next; while(p&&cnt<K){p = p-> Next;cnt++;}if((cnt==K)&&p) printf("您查找的数为：%d\n",p -> Data);else printf("您查找数不存在");}//按值查找 Position Find(List L,int X){Position p;p = L->Next; while(p&&p->Data!=X){p = p-> Next;}if(p) printf("查找成功，您查找的数为：%d\n",p->Data);else printf("您查找数不存在");}//插入List Insert(List L ,ElementType X,int i){Position tmp,pre;int cnt =0 ;pre = L;while(pre&&cnt<i-1){pre = pre->Next;cnt++;}if(pre==NULL||cnt!=i-1){printf("插入位置参数错误\n");}else{tmp = (Position)malloc(sizeof(struct LNode));tmp->Data=X;tmp->Next=pre->Next;pre->Next=tmp;}} //删除bool Delete(List L,int i){Position tmp,pre;int cnt = 0;pre = L;while(pre&&cnt<i-1){pre=pre->Next;cnt++;}if(pre==NULL||cnt!=i-1||pre->Next==NULL){printf("删除位置参数错误");}else{tmp = pre->Next;pre->Next = tmp->Next;free(tmp);printf("删除成功"); }} //求表长int Length(List L){Position p;int cnt = 0;p = L->Next;while(p){p = p -> Next;cnt++;}return cnt;} void DisLinkList(List L){List p = L->Next;printf("输出链表： "); while (p){printf("%d ", p->Data);p = p->Next;}}int main(){Position pre;Position L = MakeEmpty();pre = L;int i,n,x,len,cz,del;//插入 scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&x);Insert(pre,x,i);}//输出 DisLinkList(pre);printf("\n");//求表长 len = Length(L);printf("表长为：%d",len);printf("\n");//按值查找printf("请输入你要按值查找的数：\n");scanf("%d",&cz);Find(L,cz);printf("\n");//按序号查找printf("请输入你要按序号查找的数的序号：\n");scanf("%d",&cz);FindKth(L,cz);printf("\n");//删除printf("请输入你要删除的数的下标：\n",del);scanf("%d",&del);Delete(L,del);DisLinkList(pre);printf("\n");return 0;}
