引用于原文
（1）单链表
在每个结点中除了包含数据域外，还包含一个指针域，用以指向其后继结点。图2-2所示为带头结点的单链表。这里要区分一下带头结点的单链表和不带头结点的单链表.
① 带头结点的单链表中头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储信息。头指针head始终不等于NULL，head->next等于NULL的时候链表为空。
② 不带头结点的单链表中的头指针head直接指向开始结点，即图2-2中的结点A1，当head等于NULL的时候链表为空。
总之，两者最明显的区别是，带头结点的单链表有一个结点不存数据信息（仅存一些描述链表属性的信息，如表长），只是作为标志，而不带头结点的单链表的所有结点都存数据信息。
注意：在题目中要区分头结点和头指针，不论是带头结点的链表还是不带头结点的链表，头指针都指向链表中第一个结点，即图2-2中的head指针。而头结点是带头结点的链表中的第一个结点，只作为链表存在的标志。
（2）双链表
单链表只能由开始结点走到终端结点，而不能由终端结点反向走到开始结点。如果要求输出从终端结点到开始结点的数据序列，则对于单链表来说操作就非常麻烦。为了解决这类问题，构造了双链表。图2-3所示为带头结点的双链表。双链表就是在单链表结点上增添了一个指针域，指向当前结点的前驱。这样就可以方便地由其后继来找到其前驱，从而实现输出终端结点到开始结点的数据序列。
同样，双链表也分为带头结点的双链表和不带头结点的双链表，情况类似于单链表。带头结点的双链表当head->next为NULL时链表为空，不带头结点的双链表当head为NULL时链表为空。
（3）循环单链表
知道了单链表的结构之后，循环单链表就显得比较简单了，只要将单链表的最后一个指针域（空指针）指向链表中第一个结点即可（这里之所以说第一个结点而不说是头结点是因为，如果循环单链表是带头结点的，则最后一个结点的指针域要指向头结点；如果循环单链表不带头结点，则最后一个指针域要指向开始结点）。图2-4所示为带头结点的循环单链表。循环单链表可以实现从任一个结点出发访问链表中的任何结点，而单链表从任一结点出发后只能访问这个结点本身及其后边的所有结点。带头结点的循环单链表当head等于head->next时链表为空，不带头结点的循环单链表当head等于NULL时链表为空。
（4）循环双链表
和循环单链表类似，循环双链表的构造源自双链表，即将终端结点的next指针指向链表中第一个结点，将链表中第一个结点的prior指针指向终端结点，如图2-5所示。循环双链表同样有带头结点和不带头结点之分。带头结点的循环双链表当head->next和head->prior两个指针都等于head时链表为空，不带头结点的循环双链表当head等于NULL时链表为空。
说明：在考研中经常要考到顺序表和链表的比较，这里给出一个较为全面的答案。
（1）基于空间的比较
1）存储分配的方式：
顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。
2）存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储总量）：
顺序表的存储密度=1，链表的存储密度<1 br="">（2）基于时间的比较
1）存取方式：
顺序表可以随机存取，也可以顺序存取（对于顺序表一般只答随机存取即可）；链表是顺序存取的。
2）插入/删除时移动元素的个数：
顺序表平均需要移动近一半元素；链表不需要移动元素，只需要修改指针。
对顺序表进行插入和删除算法时间复杂度分析：
具有n个元素的顺序表（见图2-8），插入一个元素所进行的平均移动个数为多少（这里假设新元素仅插入在表中每个元素之后）？
因为题目要计算平均移动个数，这就是告诉我们要计算移动个数的期望。对于本题要计算期望，就要知道在所有可能的位置插入元素时所对应的元素移动个数以及在每个位置发生插入操作的概率。
① 求概率。
因为插入位置的选择是随机的，所以所有位置被插入的可能性都是相同的，有n个可插入位置，所以任何一个位置被插入元素的概率都为p=1/n。
② 求对应于每个插入位置需要移动的元素个数。
假设要把新元素插入在表中第i个元素之后，则需要将第i个元素之后的所有元素往后移动一个位置，因此移动元素个数为n-i。
由①和②可知，移动元素个数的期望E为
E=(n-1)/2
删除操作时元素平均移动的次数的计算方法与插入操作类似，这里不再讲解。
即要移动近一半元素，由此可以知道，插入和删除算法的平均时间复杂度为O(n)。
2．单链表结点定义
typedef struct LNode
{
//1:
int data;
//2:
struct LNode *next;
}LNode;//3
注释:
//1:data中存放结点数据域（默认是int型）。
//2:指向后继结点的指针。
//3:定义单链表结点类型。
3．双链表结点定义
typedef struct DLNode
{
//1:
int data;
//2:
struct DLNode *prior;
//3:
struct DLNode *next;
}DLNode;//4
注释:
//1:data中存放结点数据域（默认是int型）。
//2:指向前驱结点的指针。
//3:指向后继结点的指针。
//4:定义双链表结点类型。
2.2.5 双链表的算法操作
1．采用尾插法建立双链表
void CreateDlistR(DLNode *&L,int a[ ],int n)
{
DLNode *s,*r;
int i;
L=(DLNode*)malloc(sizeof(DLNode));
L->next=NULL;
//1:
r=L;
for(i=1;i<=n;++i)
{
//创建新结点:
s=(DLNode*)malloc(sizeof(DLNode));
s->data=a[i];
//2:
r->next=s;
s->prior=r;
r=s;
}
r->next=NULL;
}
注释:
//1:和单链表一样，r始终指向终端结点，开始头结点也是尾结点。
//2:下边3句将s插入到L的尾部并且r指向s，s->prior=r;这一句是和建立单链表不同的地方。
2．查找结点的算法
在双链表中查找第一个结点值为x的结点，从第一个结点开始，边扫描边比较，若找到这样的结点，则返回结点指针，否则返回NULL。算法代码如下
DLNode* searchNode(DLNode *C,int x)
{
DLNode *p=C->next;
while(p!=NULL)
{
if(p->data==x)
break;
p=p->next;
}
return p;
//1:
}
注释:
//1:如果找到，则p中内容是结点地址（循环因break结束）；如果没找到，则p中内容是NULL（循环因p等于NULL而结束）。因此这一句可以将题干中要求的两种返回值的情况统一起来。
3．插入结点的算法
假设在双链表中p所指的结点之后插入一个结点s，其操作语句如下：
s->next=p->next;
s->prior=p;
p->next=s;
//假如p指向最后一个结点，则本行可去掉:
s->next->prior=s;
说明：按照图2-16所示的顺序来插入，可以看成是一个万能的插入方式。其特点是，先将要插入的结点两边链接好，这样就可以保证不会发生链断之后找不到结点的情况。考生们一定要记住这种万能插入结点的方式。
4．删除结点的算法
设要删除双链表中p结点的后继结点，其操作语句如下：
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);
