一、链表概念
链式存储结构：结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中元素的逻辑次序和物理次序不一定相同。
单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。
例如：26个英文小写字母表的链式存储结构
各个结点由两个域组成：
数据域：存储元素数值数据
指针域：存储直接后继结点的存储位置
与链式存储有关的术语
1、结点：数据元素的存储映像。由数据域和指针域两部分组成
2、链表：n个结点由指针链组成一个链表
3、单链表：结点只有一个指针域的链表，称为单链表或线性链表
双链表：结点由两个指针域的链表，称为双链表
循环链表：首尾相接的链表称为循环链表
4、头指针：是指向链表中第一个结点的指针
首元结点：是指链表中存储第一个数据元素a1的结点
头结点：是在链表的首元结点之前附设的一个结点
上面的例子中的链表的存储结构示意图有以下两种形式：
链表(链式存储结构)的特点
（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等
二、单链表的定义和表示
带头结点的单链表
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L。
单链表的存储结构
typedef struct Lnode{ //声明结点的类型和指向结点的指针类型 ElemType data; //结点的数据域 struct Lnode *next; //结点的指针域 }Lnode,LinkList; //LinkList为指向结构体Lnode的指针类型
例如：存储学生学号、姓名、成绩的单链表结点类型定义如下
typedef Struct student{ char num[8]; //数据域 char name[8]; //数据域 int score; //数据域 struct student *next; //指针域 }Lnode,LinkList;
但是此操作不常用。为了统一链表的操作，通常这样定义：
typedef Struct { char num[8]; //数据域 char name[8]; //数据域 int score; //数据域 }ElemType; typedef struct Lnode{ ElemType data; //数据域 struct Lnode *next; //指针域 }Lnode,*LinkList;
三、单链表基本操作的实现
1、初始化
单链表的初始化操作就是构造一个如图所示的空表
算法1 单链表的初始化
【算法步骤】
①生成新结点作为头结点，用头指针L指向头结点。
②头结点的指针域置空。
【算法描述】
Status InitList(LinkList &L) { //构造一个空的单链表L L = new LNode; //生成新结点作为头结点，用头指针L指向头结点 L->next=NULL; //头结点的指针域置空 return OK; }
2、取值
和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样，根据给定的结点位置序号i，在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点触发，顺着链域next逐个结点向下访问。
算法2 单链表的取值
【算法步骤】
①用指针p指向首元结点，用j做计数器初赋值为1。
②从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空(NULL)，并且没有到达序号为i的结点，则循环执行以下操作：
- p指向下一个结点；
- 计数器j相应加1。
③退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，取值失败返回ERROR；否则取值成功，此时j=i时，p 所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。
【算法描述】
Status GetElem(LinkList L,int i,ElemType &e) { //在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值 p=L->next;j=1; //初始化，p指向首元结点，计数器j初赋值为1 while(p&&j<i) //顺链域向后扫描，直到p为空或p指向第i个元素 { p=p->next; //p指向下一个结点 ++j; //计数器j相应加1 } if(!p || j>i) return ERROR; //i值不合法i > n或i ≤ 0 e=p->data; //取第i个结点的数据域 return OK; }
【算法分析】
该算法的基本操作是比较j和i并后移指针p，while循环体中的语句频度与位置i有关。若1 ≤ i ≤ n，则频度为i-1，一定能取值成功；若i > n，则频度为n，取值失败。因此算法的最坏时间复杂度为O(n)。
假设每个位置上元素的取值概率相等，即pi = 1/n，则
由此可见，单链表取值算法的平均时间复杂度为O(n)。
3、查找
链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。
算法3 单链表的按值查找
【算法步骤】
①用指针p指向首元结点。
②从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点。
③返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
【算法描述】
LNode *LocateElem(LinkList L,Elemtype e) { //在带头结点的单链表L中查找值为e的元素 p=L->next; //初始化，p指向首元结点 while(p && p->data!=e) //顺链域向后扫描，直到p为空或p所指结点的数据域等于e p=p->next; ///p指向下一个结点 return p; //查找成功返回值为e的结点地址p，查找失败p为NULL }
【算法分析】
该算法的执行时间与待查找的值e相关，其平均时间复杂度分析类似于算法2，也为O(n)。
4、插入
假设要在单链表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针，如图(a)所示
为插入数据元素x，首先要生成一个数据域为x的结点，然后插入到单链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后单链表如图(b)所示。
假设s为指向结点x的指针，则上述指针修改用语句描述即为
s->next = p->next; p->next = s;
算法4 单链表的插入
【算法步骤】
将值为e的新结点插入到表的第i个结点的位置上，即插入到结点ai-1与ai之间，具体插入过程如图
在单链表第i个位置上插入新结点的过程
图中对应的5个不走说明如下：
①查找结点ai-1并由指针p指向该结点。
②生成一个新结点*s。
③将新节点*s的数据域置为e。
④将新节点*s的指针域指向结点ai。
⑤将结点*p的指针域指向新结点*s。
【算法描述】
Status ListInsert(Linklist &L,int i,ElemType e) { //在带头节点的单链表L中第i个位置插入值为e的新结点 p=L;j=0; while(p && (j<i-1)) {p=p->next;++j;} //查找第i-1个结点，p指向该结点 if(!p || j>i-1) return ERROR; //i>n+1或者i<1 s=new LNode; //生成新结点*s s->data=e; //将结点*s的数据域置为e s->next=p->next; //将结点*s的指针域指向结点ai p->next=s; //讲指针*p的指针域指向结点*s return OK; }
【算法分析】
单链表的插入操作孙然不需要像顺序表的插入操作那样需要移动元素，但平均时间复杂度仍为O(n)。这是因为，为了在第i个结点之前插入一个新结点，必须首先找到第i-1个结点，其时间复杂度与算法2相同，为O(n)。
5、删除
要删除单链表中指定位置的元素，同插入元素一样，首先应该找到该位置的前驱结点。如图所示
在单链表中删除元素b时，应该首先找到其前驱结点a。为了在单链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为
p->next=p->next-next;
但在删除结点b时，除了修改结点a的指针域外，还要释放结点b所占的空间，所以在修改指针前，应该引入另一指针q，临时保存结点b的地址以备释放。
算法5 单链表的删除
【算法步骤】
删除单链表的第i个结点aᵢ的具体过程如图所示
图中的对应的4个步骤说明如下
①查找结点aᵢ₋₁并由指针p指向该结点。
②临时保存待删除结点a，的地址在q中，以备释放。
③将结点*p的指针域指向aᵢ的直接后继结点。
④释放结点aᵢ的空间。
【算法描述】
Status Listɒelete(LinkList<L, int i) { //在带头结点的单链表L中，删除第i个元素 p=L;j=0; while( (p->next) && (j<i-1)) //查找第i-1个结点，p指向该结点 {p=p->next;++j;} if(!(p->next)||(j>i-1)) return ERROR; //当i>n或i<1时,删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 delete q; //释放删除结点的空间 return OK; }
【算法分析】
类似于插入算法，删除算法时间复杂度亦为O(n)。
6、创建单链表
算法1的初始化操作是创建一个只有一个头结点的空链表，而上面链表的其他算法都是假定链表已经存在多个结点。那么，如何建立一个包括若干个结点的链表呢？链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。
根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。
（1）前插法
前插法是通过将新结点逐个插入链表的头部(头结点之后)来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。
算法6 前插法创建单链表
【算法步骤】
①创建一个只有头结点的空链表。
②根据待创建链表包括的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p；
- 输入元素值赋给新结点*p的数据域；
- 将新结点*p插入到头结点之后。
下图为线性表(a，b，c，d，e)前插法的创建过程，因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入e、d、c、b、a，输入顺序和线性表中的逻辑顺序是相反的。
【算法描述】
void CreateList_H(LinkListSL, int n) ( //逆位序输入n个元素的值，建立带表头结点的单链表L L-new LNode; L->next=NULL; //先建立一个带头结点的空链表 for( i=0;i<n;++i) { p=new LNode; //生成新结点*p cin>>p=>data; //输入元素值赋给新结点*p的数据域 p->next=L->next;L->next=p; //将新结点*p插入到头结点之后 } )
显然，算法6的时间复杂度为O(n)
（2）后插法
后插法是通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。
算法7 后插法创建单链表
【算法步骤】
① 创建一个只有头结点的空链表。
② 尾指针r初始化，指向头结点。
③ 根据创建链表包括的元素个数n、循环n次执行以下操作：
- 生成一个新结点*p；
- 输入元素值赋给新结点*p的数据域；
- 将新结点*p插入到尾结点*r之后；
- 尾指针r指向新的尾结点*p。
图所示为线性表(a，b，c，d，e)后插法的创建过程，读入数据的顺序和线性表中的逻辑顺序是相同的。
【算法描述】
void CreateList_R(LinkList6L, int n) { //正位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; //先建立一个带头结点的空链表 x=L; //尾指针r指向头结点 for(i=0;icn;++i) { p=new LNode; //生成新结点 cin>>p->data; //输入元素值赋给新结点*p的数据域 p->next=NULL;r->next=p; //将新结点*p插入尾结点*r之后 r=p; //r指向新的尾结点*p } }
算法7的时间复杂度亦为O(n)。
四、循环链表
循环链表(Circular Linked List)是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，图所示为单链的循环链表。类似地，还可以有多重链的循环链表。
循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为
p != NULL 或 p->next != NULL
而循环单链表的判别条件为
p != L或p->next != L
在某些情况下，若在循环链表中设立尾指针而不设头指针(见下图( a))，可使一些操作简化。例如，将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表以下图(a)的循环链表作存储结构时，这个操作仅需改变两个指针值即可
主要语句段如下
p=B->next->next; B->next=A->next; A->next=p;
上述操作的时间复杂度为O(1)，合并后的表如上图(b)所示。
五、双向链表
以上链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双向链表(Double Linked List)。
顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，结点结构如图2.19(a)所示，在C语言中可描述如下：
typedef struct DuLNode { ElemType data; //数据域 struct DuLNode *prior; //直接前驱 struct DuLNode *next; //直接后继 }DuLNode,*DuLinkList;
和单链的循环表类似，双向链表也可以有循环表，如下图(c)所示，链表中存有两个环，下图(b)所示为只有一个表头结点的空表
在双向链表中，若d为指向表中某一结点的指针(即d为DuLinkList型变量)，则显然有
d->next->prior=d->prior->next=d
这个表示方式恰当地反映了这种结构的特性。
在双向链表中,有些操作(如ListLength、GetElem和LocateElem等)仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向上的指针，下面两个图分别显示了插入和删除结点时指针修改的情况。在插入结点时需要修改四个指针，在删除结点时需要修改两个指针。它们的实现分别如算法8和算法9所示，两者的时间复杂度均为0(n)。
图1 在双链表中插入结点时指针的变化情况
图2 在双向链表中删除结点时指针的变化情况
算法8 双向链表的插入
【算法描述】
Status ListInsert_DuL(DuLinkLiat6L, int i,ElenTypee) { //在带头结点的双向链表L中第i个位置之前插入元素e if(!(p=GetElem_DuL(L,i))) //在L中确定第i个元素的位置指针p return ERROR; //p为NULL时,第i个元素不存在 s=new DuLNode; //生成新结点*s s->data=e; //将结点*s数据域置为e s->prior=p->prior; //将结点*s插入L中.此步对应图1① p->prior->next=s; //对应图1② s->next=p; //对应图1⑧ p->prior=s; //对应图1④ return OK; }
算法9 双向链表的删除
【算法描述】
Status ListDelete_DuL(DuLinkList6L, int i) { //删除带头结点的双向链表1中的第4个元素 if(!(p=GetElem_DuL(I,i))) //在L中确定第1个元素的位置指针p return ERROR; //p为NULL时,第i个元素不存在 p->prior->next=p->next; //修改被删结点的前驱结点的后继指针，对应图2① p->next->prior=p->prior; //修改被删结点的后继结点的前驱指针，对应图2② delete p; //释放被删结点的空间 return OK; }
原文地址：http://www.cnblogs.com/Santariki/p/16806001.html
