在上一篇博文中介绍了线性表的顺序存储方式，它最大的缺点就是在插入和删除操作时会移动大量的元素，这显然会耗费很多时间。后来人们便想到了用链式存储方式来解决上面这一问题。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过 “链” 建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。
一、单链表
1.1 单链表的定义
线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。单链表结点结构如图所示：
其中data为数据域，存放数据元素。next为指针域，存放其后继结点的地址。
单链表节点类型描述如下：
typedef struct LNode{ElemType data;//数据域struct LNode *next;//指针域}LNode,*LinkList;//LNode等价于struct LNodeLinkList等价于struct LNode *
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
通常用头指针来标识一个单链表，如单链表L,头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点， 称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点， 如图所示：
头结点和头指针的区分：头指针始终指向链表的第一个结点（有效数据的第一个节点），而头结点是带头结点的链表中的第一个结点。
引入头结点的好处： .
① 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
② 无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一。
1.2 单链表的基本操作实现
1.2.1 采用头插法建立单链表
头插法也就是将新结点插入到当前链表的表头，即头结点（head）后第一个位置。
头插法的实现代码：
LinkList HeadInsert(LinkList L){LinkList s;int x;L = (LinkList)malloc(sizeof(LNode)); //产生头结点,并使L指向此头结点 L->next = NULL;printf("请输入节点元，以666结束：\n");scanf("%d",&x);while(x != 666){s = (LNode *)malloc(sizeof(LNode));//生成新结点s->data = x;s->next = L->next;// 将头结点的指针域指向下一个结点L->next = s;//将新结点插入表中scanf("%d",&x);}return L;}
采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n,则总时间复杂度为O(n)。
1.2.2 采用尾插法建立单链表
头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。按我们正常的逻辑，应该使生成结点顺序和输入的数据顺序一致， 那么可采用尾插法实现。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针 r ,使其始终指向当前链表的尾结点。
尾插法的实现代码：
/* 建立带表头结点的单链线性表L（尾插法） */LinkList TailInsert(LinkList L){LinkList s,r;//r为表尾指针int x;L = (LinkList)malloc(sizeof(LNode));r = L;printf("请输入节点元，以666结束：\n");scanf("%d",&x);while(x != 666){s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;//r指向新的表尾结点scanf("%d",&x);}r->next = NULL;return L;}
1.2.3 插入结点操作
插入结点操作将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，.然后找到待插入位置的前驱结点，即第 i-1个结点，再在其后插入新结点。
插入结点的实现代码：
bool ListInsert(LinkList L,int i,ElemType e){int j = 1;LinkList p,s;p = L->next;while(p && j < i-1)//这里要查找第i个元素的前一个{p = p->next;j++;}if(!p || j > i-1)return false;//第i-1个元素不存在 s = (LinkList)malloc(sizeof(LNode));//生成新结点s->data = e;s->next = p->next;p->next = s;return true;}
1.2.4 删除结点操作
删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，后查找表中第 i- 1个结点，即被删结点的前驱结点，再将其删除。其操作过程如图：
假设结点*p为找到的被删结点的前驱结点，为实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点。
删除结点的实现代码：
bool ListDelete(LinkList L,int i,ElemType *e){int j = 1;LinkList p,s;p = L->next;while(p && j < i-1)//这里要查找第i个元素的前一个{p = p->next;j++;}if(!p || j > i-1)return false;//第i-1个元素不存在s = p->next;p->next = s->next;*e = s->data;free(s);return true;}
其他求表长，查找某个结点，排序等就不再赘述了，可在后面代码中查看。
1.3 完整代码
#include<stdio.h>#include<malloc.h>#define MaxSize 20typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */typedef struct LNode{ElemType data;//数据域struct LNode *next;//指针域}LNode,*LinkList;//LNode等价于struct LNodeLinkList等价于struct LNode *LinkList HeadInsert(LinkList L);//（头插法）建立单链表LinkList TailInsert(LinkList L);//（尾插法）建立单链表void PrintList(LinkList L);//打印链表int GetElem(LinkList L,int i,ElemType *e);//查找链表中第i个元素的值int LocateElem(LinkList L,ElemType e);//按值查找，返回链表中第一个位置bool ListInsert(LinkList L,int i,ElemType e);//在某个位置插入操作bool ListDelete(LinkList L,int i,ElemType *e);//删除某个位置结点void SortList(LinkList pHead);//对链表排序int ListLength(LinkList L);//获取链表长度int main(){LinkList LHead = NULL;ElemType e;//用于存放查找后的值int location;//用于存放查找某结点的位置int cur;//用于存放返回值//LHead = HeadInsert(LHead);LHead = TailInsert(LHead);PrintList(LHead);cur = ListLength(LHead);printf("该链表的长度为：%d\n",cur);cur = GetElem(LHead,3,&e);if(cur == 1)printf("第3个位置的值为：%d\n",e);elseprintf("未找到该位置的元素！\n");location = LocateElem(LHead,33);if(location != 0)printf("该结点的位置为：%d\n",location);elseprintf("未找到该元素！\n");ListInsert(LHead,2,888);ListInsert(LHead,4,999);printf("插入后");PrintList(LHead);ListDelete(LHead,4,&e);printf("删除的元素为：%d\n",e);printf("删除后");PrintList(LHead);SortList(LHead);printf("排序后");PrintList(LHead);return 0;}/* 建立带表头结点的单链线性表L（头插法） */LinkList HeadInsert(LinkList L){LinkList s;int x;L = (LinkList)malloc(sizeof(LNode)); //产生头结点,并使L指向此头结点 L->next = NULL;printf("请输入节点元，以666结束：\n");scanf("%d",&x);while(x != 666){s = (LNode *)malloc(sizeof(LNode));//生成新结点s->data = x;s->next = L->next;// 将头结点的指针域指向下一个结点L->next = s;//将新结点插入表中scanf("%d",&x);}return L;}/* 建立带表头结点的单链线性表L（尾插法） */LinkList TailInsert(LinkList L){LinkList s,r;//r为表尾指针int x;L = (LinkList)malloc(sizeof(LNode));r = L;printf("请输入节点元，以666结束：\n");scanf("%d",&x);while(x != 666){s = (LinkList)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;//r指向新的表尾结点scanf("%d",&x);}r->next = NULL;return L;}//查找链表中第i个元素的值int GetElem(LinkList L,int i,ElemType *e){int j = 1;//计数器LinkList p;//让p指向链表L的第一个结点p = L->next;while(p && j < i)//p不为空或者计数器j还没有等于i时，循环继续{p = p->next;j++;}if(!p || j > i)//这里!p表示链表循环完没有找到第i个元素，j > i 表示一开始的i < 1return 0;//第i个元素不存在 *e = p->data;return 1;}/* 返回L中第1个与e满足关系的数据元素的位序。若这样的数据元素不存在，则返回值为0 */int LocateElem(LinkList L,ElemType e){int i = 0;LinkList p = L->next;while(p){i++;if(p->data == e)return i;p = p->next;}return 0;}/* 在L中第i个位置之前插入新的数据元素e，L的长度加1 */bool ListInsert(LinkList L,int i,ElemType e){int j = 1;LinkList p,s;p = L->next;while(p && j < i-1)//这里要查找第i个元素的前一个{p = p->next;j++;}if(!p || j > i-1)return false;//第i-1个元素不存在 s = (LinkList)malloc(sizeof(LNode));//生成新结点s->data = e;s->next = p->next;p->next = s;return true;}/* 删除L的第i个数据元素，并用e返回其值，L的长度减1 */bool ListDelete(LinkList L,int i,ElemType *e){int j = 1;LinkList p,s;p = L->next;while(p && j < i-1)//这里要查找第i个元素的前一个{p = p->next;j++;}if(!p || j > i-1)return false;//第i-1个元素不存在s = p->next;p->next = s->next;*e = s->data;free(s);return true;}int ListLength(LinkList L){int len = 0;LinkList p = L->next;while(p){len++;p = p->next;}return len;}void SortList(LinkList pHead){int i,j,t;int len = ListLength(pHead);LinkList p,q;for(i = 0,p = pHead->next;i < len -1;i++,p = p->next){for(j = i+1,q = p->next;j < len;j++,q = q->next){if(p->data > q->data){t = p->data;p->data = q->data;q->data = t;}}}return;}void PrintList(LinkList L){LinkList p = L->next;printf("链表的元素为：");while(NULL != p){printf("%d ",p->data);p = p->next;}printf("\n");}
二、双链表
单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。.为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点，如图所示。
双链表中结点类型的描述如下：
typedef struct DNode{ElemType data;struct DNode *prior,*next;//前驱和后继指针}DNode,*DLinkList;
2.1 双链表的插入操作
在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图：
插入操作代码如下：
① s->next = p->next;//将结点*s插入到结点*p之后② p->next->prior = s;③ s->prior = p;④ p->next = s;
注意：上述代码的语句顺序不是唯一的，但也不是任意的，①和②两步必须在④步之前，否则*p的后继结点的指针就会丢掉，导致插入失败。
2.2 双链表的删除操作
删除双链表中结点p的后继结点q,其指针的变化过程如图：
删除操作代码如下：
① p->next = q->next;② q->next->prior = p;free(q);//释放空间
在建立双链表的操作中，也可采用如同单链表的头插法和尾插法，但在操作_上需要注意指针的变化和单链表有所不同。
三、循环链表
将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。
3.1 循环单链表
若将链表中最后一个结点的next域指向头结点，则得到：
在循环单链表中,表尾结点*r的next域指向L,故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。.
循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是-一个“环”，因此在任何一一个位 置上的插入和删除操作都是等价的，无须判断是否是表尾。
3.2 循环双链表
由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的prior指针还要指向表尾结点，如图所示。
在循环双链表L中，某结点*p为尾结点时，p->next==L; 当循环双链表为空表时，其头结点的prior域和next域都等于L。
