链式存储是最常用的动态存储方法。为了克服顺序表的缺点，可以采用链式方式存储线性表。通常将采用链式存储结构的线性表称为线性链表。可以从两个角度来讨论线性链表：从链接方式的角度看，链表可分为单链表、循环链表和双链表。从实现角度看，链表可以分为动态链表和静态链表。
单链表
在顺序表中，用一组地址连续的存储单元来依次存放线性表的结点，因此结点的逻辑顺序和物理顺序是一致的。而链表则不然，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置上。因此，链表中结点的逻辑顺序和物理顺序不一定相同。为了正确的表示结点间的逻辑关系，必须在存储线性表的每个数据元素的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映像称为结点（Node）。
结点包括两个域：数据域用来存储结点的值，指针域用来存储数据元素的直接后继的地址（或位置）。线性链表正是通过每个结点的指针域或将线性表的n个结点按其逻辑顺序链接在一起的。由于此线性链表的每一个结点只有一个next指针域，故将这种链表称为单链表。
单链表中每个结点的存储地址存放在其前驱结点的指针域中，由于线性表中的第一个结点无前驱，所以应设一个头指针H指向第一个结点。由于线性表的最后一个结点没有直接后继，则指定单链表的最后一个结点的指针域为“空”（NULL）。
单链表的头指针H指示着整个单链表的开始，习惯上用头指针代表单链表。给定单链表的头指针H，即可顺着每个结点的next指针域得到单链表中的每个元素。因此对于整个单链表的操作必须从头指针开始。
一般情况下，使用链表，只关心链表中节点间的逻辑顺序，并不关心各个结点的实际存储位置，因此通常用箭头来表示链域中的指针，于是链表就可以更直观的化成箭头链接起来的结点序列。
为了操作的统一，方便，可以在单链表的第一个结点之前附设一个头结点，头结点的数据域可以存储一些关于线性表的长度等附加信息，也可以不存储任何信息，对头结点数据域信息无特别规定，而头结点的指针域则用来存储指向第一个结点的指针（即第一个结点的存储位置）。此时头指针就不再指向表中第一个结点而是指向头结点。如果线性表为空表，则头结点的指针域为“空”。
单链表的存储结构描述如下：
typedef struct Node /*结点类型定义*/
{ ElemType data;
struct Node* next;
}Node, *LinkList; /*LinkList为指针结构类型*/
LinkList与Node*同为结构指针类型，这两种类型是等价的。通常习惯上用LinkList说明指针变量，强调它是某个单链表的头指针变量。例如，使用定义LinkList L,则L为单链表的头指针，从而提高程序的可读性。用Node *来定义指向单链表中结点的指针，例如，Node *p，则p为指向单链表中结点的指针变量。
L是单链表的头指针，它指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若L==NULL（对于带头结点的单链表为L->next==NULL）表达式为真，则表示单链表为一个空表，其长度为0.若是非空表，则可以通过头指针L访问表中结点，从而找到要访问的所有结点的数据信息。例如，对于带头结点的单链表L，另p=L->next，则p指向表中的第一个元素结点（也称首元结点），通过p->data就可以访问到表中第一个元素的数据值了。
单链表上的基本运算
以单链表作存储结构实现线性表的基本运算。
1.初始化单链表
【算法描述】初始化单链表
InitList(LinkList *L)
{
*L=(LinkList)malloc(sizeof(Node)); /*建立头结点*/
(*L)->next=NULL; /*建立空的单链表L*/
}
注意：L是指向单链表的头结点的指针，用来接收主程序中待初始化单链表的头指针变量的地址，*L相当于主程序中待初始化单链表的头指针变量。
2.建立单链表
假设线性表中结点的数据类型是字符，逐个输入这些字符，并以“$”作为输入结束标志符。常见的建表方法有如下两种。
（1）头插法建表
【算法思想】从一个空表开始，每次读入数据，生成新节点，将读入数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头结点之后，直至读入结束标志为止。
【算法描述】用头插法建立单链表
void CreateFromHead(LinkList L)
/*L是带头结点的空链表头指针，通过键盘输入表中元素值，利用头插法建单链表L*/
{ Node *s;
char c;
int flag=1;
while(flag) /*flag初值为1，当输入“$”时，置flag为0，建表结束*/
{
c=getchar();
if(c!='$')
{
s=(Node *)malloc(sizeof(Node)); /*建立新节点s*/
s->data=c;
s->next=L->next; /*将s结点插入表头*/
L->next=s;
}
else flag=0;
}
}
采用头插法得到的单链表的逻辑顺序与输入元素顺序相反，也称头插法建表为逆序建表法。
注意：在上述运算中，L是指向单链表的头指针，习惯上称为单链表L。
（2）尾插法建表
【算法思想】头插法建立链表虽然算法简单，但生成的链表中结点的次序与输入的顺序相反。若希望二者顺序一致，可采用尾插法建表。该方法是将新节点插入到当前单链表的表尾上。为此增加一个尾指针r，使之指向当前单链表的表尾。
【算法描述】用尾插法建立单链表
void CreateFormTail(LinkList L)
/*L是带头结点的空链表头指针，通过键盘输入元素值，利用尾插法建单链表L*/
{ Node *r,*s;
int flag=1; /*设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/
r=L; /*循环输入表中元素值，将建立新节点s插入表尾*/
{
c=getchar();
if(c!='$')
{
s=(Node *)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/
}
} /*while*/
} /*CreateFormTail*/
3.查找
（1）按序号查找
【算法思想】在单链表中，由于每个结点的存储位置都放在其前一节点的next域中，所以即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取，而只能从链表的头指针出发，顺链表域next逐个结点往下搜索，直至搜索到第i个结点为止。
要查找带头结点的单链表中第i个结点，则需要从单链表的头指针L出发，从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点，初值指向头结点，用j做计数器，累计当前扫描过的结点数（初值为0），当i=j时，指针p所指的结点就是要找的第i个结点。
【算法描述】在单链表L中查找第i个结点
Node * Get(LinkList L,int i)
/*在带头结点的单链表L中查找第i个结点，若找到（1<=i<=n）,则返回该结点的存储位置；否则返回NULL*/
{ int j;
Node *p;
if(i<=0)return NULL;
p=L;j=0; /*从头结点开始扫描*/
while (p->next!=NULL)&&(j<i)
{ p=p->next; /*扫描下一结点*/
j++; /*已扫描结点计数器*/
}
if(i==j) return p; /*找到了第i个结点*/
else return NULL; /*找不到，i<=0或i>n*/
} /*Get*/
（2）按值查找
【算法思想】按值查找是指在单链表中查找是否有值等于e的结点。查找过程从单链表的头指针指向的头结点出发，顺链逐个将结点值和给定值e作比较，返回结果。
【算法描述】在单链表L中查找值为key的结点
Node * Locate(LinkList L,ElemType key)
/*在带头结点的单链表L中查找其结点值等于key的第一个结点，若找到则返回该结点的位置p，否则返回NULL*/
{ Node * p;
p=L->next; /*从表中的第一个结点开始*/
while(p!=NULL) /*当前表未查完*/
if(p->data!=key)
p=p->next;
else break; /*找到结点值=key时退出循环*/
return p;
} /*Locate*/
这两个算法的平均时间复杂度均为O(n).
4.求单链表长度操作
在顺序表中，线性表的长度是它的属性，数组定义时就已确定。在单链表，整个链表由“头指针”来表示，单链表的长度从头到尾遍历的过程中统计计数，得到的长度值未显示保存。
【算法思想】采用“数”结点的方法求出带头结点单链表的长度。即从“头”开始“数”(p=L->next),用指针p依次指向各个结点，并附设计数器j计数，一直“数”到最后一个结点(p->next==NULL),从而得到单链表的长度。
【算法描述】求单链表的长度
int ListLength(LinkList L)
/*求带头结点的单链表L的长度*/
{ Node *p;
p=L->next;
j=0; /*用来存放单链表的长度*/
while(p!=NULL)
{ p=p->next;
j++;
}
return j; /*j为求得的单链表长度*/
} /*ListLength*/
5.单链表插入操作
【问题要求】在线性表的第i（1<=i<=n+1）个位置之前插入一个新元素e。
【算法思想】插入过程分为以下三步。
①查找：在单链表中找到第i-1个结点并由指针pre指示。
②申请：申请新节点s,将其数据域的值制为e。
③插入挂链：通过修改指针域将新节点s挂入单链表L.
【结果】将长度为n的线性表(a1,……ai-1,ai,……,an)变成长度为n+1的线性表(a1,……，ai-1,a,ai,……,an).
【算法描述】单链表插入操作
void InsList(LinkList L,int i,ElemType e)
/*在带头结点的单链表L中第i个位置插入值为e的新节点*/
{
Node *pre,*s;
int k;
if(i<=0)return ERROR;
pre=L; k=0; /*从头开始，查找第i-1个结点*/
while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/
{ pre=pre->next;
k=k+1;
} /*查找第i-1个结点*/
if(pre==NULL) /*如当前位置pre为空表示已找完，但还未找到第i个，说明插入位置不合理*/
{printf("插入位置不合理！");
return ERROR;
}
s=(Node*)malloc(sizeof(Node)); /*申请一个新的结点s*/
s->data=e; /*值e置入s的数据域*/
s->next=pre->next; /*修改指针，完成插入操作*/
pre->next=s;
return OK;
}
说明：若单链表中有m个结点，则按头插法操作时插入位置有m+1个，即1<=i<=m+1.当i=m+1，则认为是在单链表的尾部插入一个结点。
6.单链表的删除操作
【问题要求】将线性表的第i(1<=i<=n+1)个元素e删除。
【算法思想】删除过程分为以下两步。
①查找：通过计数方式找到第i-1个结点并由指针pre指示。
②删除第i个结点并释放结点空间。
【结果】将长度为n的线性表(a1,……,ai-1,ai,……,an)
变成长度为n-1的线性表(a1,……,ai-1,ai+1,……,an)
【算法描述】单链表删除操作
int DelList(LinkList L,int i,ElemType *e)
/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/
{
Node *pre,*r;
int k;
pre=L;k=0;
while(pre->next!=NULL&&k<i-1)
/*寻找被删除结点i的前驱结点i-1使p指向它*/
{ pre =pre->next;
k=k+1;
} /*查找第i-1个结点*/
if(pre->next==NULL)/*while循环是因为p->next=NULL或i<1而跳出的，因为pre->next为空，没有找到合法的前驱位置，说明删除位置i不合法*/
{
printf("删除结点的位置i不合理！");
return ERROR;
}
r=pre->next;
pre->next=r->next; /*修改指针，删除结点r*/
*e=r->data;
free(r); /*释放被删除的结点所占内存空间*/
return OK;
}
说明：删除算法中的循环条件(pre->next!=NULL &&k<i-1)不同，因为前插时的插入位置有m+1个（m为当前链表的数据元素的个数）。i=m+1是指在第m+1个位置前插入，即在单链表的末尾插入。而删除操作中删除的合法位置只有m个，若使用与前插操作相同的循环条件，则会出现指针指空的情况，使删除操作失败。
例. 有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：利用新表LC利用现有的表LA和LB中的元素结点空间，而不要额外申请结点空间。例如LA=(2,2,3),LB=(1,3,3,4),则LC=(1,2,2,3,3,3,4)。
【算法思想】要求利用现有的表LA和LB中的结点空间来建立新表LC，可通过更改结点的next域来重建新的元素之间的线性关系。为保证新表仍然递增有序，可以利用尾插法建立单链表方法，只是新建表中的结点不用malloc，而只要从表LA和LB中选择合适的点插入到新表LC中即可。
【算法描述】合并两个有序的单链表
LinkList MergeLinkList(LinkList LA,LinkList LB)
/*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/
{ Node *pa,*pb;
LinkList LC;
/*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一个结点，r初值为LC且r始终指向LC的表尾*/
pa=LA->next;
pb=LB->next;
LC=LA;
LC->next=NULL;r=LC;
/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。*/
while(pa!=NULL&&pb!=NULL)
{if(pa->data<=pb->data)
{r->next=pa;r=pa;pa=pa->next;}
else
{r->next=pb;r=pb;pb=pb->next;}
}
if(pa) /*若表LA未完，将表LA中后续元素链到新表LC表尾*/
r->next=pa;
else /*否则将表LB中后续元素链到新表LC表尾*/
r->next=pb;
free(LB);
return(LC);
} /*MergeLinkList*/
