一、什么是链表
链表是线性表的一种，同顺序表一样，都是最基础的线性表。与顺序表的区别在于使用了不同存储结构实现，顺序表使用顺序存储结构，而链表使用链式存储结构。
链表的实现是通过节点，通常节点包含两个区域，数据域和指针域。数据域用来存储我们的数据，而指针域用来存储下一个节点的指针，而节点之间的联系也是通过指针域来建立的。假如我们用链表存储下列有序数据：a1,a2,a3,...an。我们已知a1的地址，我们可以通过a1的地址获取a1，然后获取a1中的指针域，从而获取a2的数据，依次类推，遍历整个链表。
上图为链表的结构体，一整个方块就是一个节点，一个节点包含数据域（蓝色方块）和指针域（橙色方块），方块外的数字表示该节点所在的地址。我们可以看到相邻节点之间的地址并非连续的，节点与节点之间通过指针域建立连接。
二、链表的表示
我们可以构建一个节点的结构体：
typedef int ElemType; typedef struct NODE{ ElemType data; //数据域 struct NODE *next; //指针域 }LNode, *LinkList; 复制代码
其中data表示数据域，next表示指针域。因为我们只需要链表的首地址就可以遍历整个链表，所以我们可以用该结构体的指针表示链表。
通常情况下，我们会创建一个节点，该节点的数据域不存放数据，指针域存放第一个节点的地址，我们把这个节点称为头结点。头结点不是必须的，为了方便，本文实现的链表是带头结点的。
三、链表的实现
我们可以通过逐个输入的方式创建链表，每输入一个数据就创建一个新节点。根据新节点插入的位置，我们又分为头插法和尾插法。我们先看看头插法。
（1）头插法
头插法就是将新节点插入在第一个位置，因为我们讨论的是带头结点的链表，所以头插法的步骤如下：
- 创建新节点
- 将第一个元素的地址赋值给新节点的指针域
- 让头结点的指针域指向新节点
头插法的图示如下：
我们可以看到，原本的第一个节点在插入新节点之后成为了第二个节点。这也就使得头插法创建的链表中数据元素的顺序（逻辑顺序）同输入顺序是相反的。我们假设链表的头节点指针为为L，新节点指针为p，我们将上图三个步骤转换成代码如下：
//1、创建新节点 p = malloc(sizeof(ElemType)); p->data = 10; //将第一个元素的地址赋值给新节点的指针域 p->next = L->next; //让头结点的指针域指向新节点 L->next = p; 复制代码
下面我们看看头插法创建链表的全部代码：
#include <stdio.h> #include <malloc.h> /** * 用于创建链表 * 返回头结点的指针，如果创建失败返回NULL */ LinkList CreateList_Head(){ ElemType e; //元素的值 LNode *p; //新节点指针 LinkList L; //头结点指针 //创建头结点并初始化头节点的指针域 L = malloc(sizeof(LinkList)); //如果内存溢出，返回NULL if(!L) return NULL; L->next = NULL; //循环输入元素，当输入的不为0时循环输入 scanf("%d", &e); while(e!=0){ //头插法三步骤 //1、创建新节点 p = malloc(sizeof(LNode)); if(!L) return L; //如果内存溢出，则返回已创建的链表 p->data = e; //给新节点的数据域赋值 //2、将第一个元素的地址赋值给新节点的指针域 p->next = L->next; //3、让头结点的指针域指向新节点 L->next = p; //继续输入 scanf("%d", &e); } //最后返回链表头结点指针 return L; } 复制代码
上述就是链表的头插法创建。
（2）尾插法
尾插法就是将元素从链表的尾部插入，因为链表不能根据下标定位元素，所以我们需要遍历链表获取链表的尾节点，因此使用尾插法需要耗费的时间比较长，但是使用尾插法链表中元素和元素的输入顺序一致。
尾插发的关键步骤就是找到链表尾部元素，我们可以用一个rear节点，让它先指向链表的头结点，然后寻找链表的尾部元素：
//创建节点直线链表头节点 LNode *rear; rear = L; //遍历到尾部 while(rear->next){ rear = rear->next; } 复制代码
我们找到尾部节点后就可以直接插入新的节点了，图示效果如下：
图中最上面的节点就是尾节点，实际上指向尾节点就是直线链表的尾部。下面我们看看尾插法如何实现链表的创建：
/** * 尾插法创建链表 * 返回链表头结点的指针，如果创建失败返回NULL */ LinkList CreateLinkList_Rear(){ int e; LNode *p, *rear; LinkList L; //创建并初始化头结点 L = malloc(sizeof(LinkList)); if(!L) return NULL; L->next = NULL; //让rear节点指向头结点 rear = L; //循环输入创建链表 scanf("%d", &e); while (e != 0){ //创建新节点并赋值 p = malloc(sizeof(LNode)); if(!p) return L; p->data = e; p->next = NULL; //遍历到尾部节点 while (rear->next){ rear = rear->next; } //将新节点插入到尾部节点后 rear-> next = p; scanf("%d", &e); } return L; } 复制代码
创建好链表后，我们就可以看一看链表中的一些操作。
四、链表的操作
我们选取几个常用的方法一一实现，我们要测试链表是否有数据首先就需要一个方法，用于输入链表中的数据。
（1）遍历链表的数据
在尾插法中，我们已经写过遍历链表的方法，只是在遍历过程中没有取数据，而我们链表的遍历实际上主体还是那几句代码：
void DisplayList(LinkList L){ LNode *p; //创建一个节点用于遍历 p = L; //将上述节点指向头节点 //循环遍历，当遍历到尾节点后一个元素时，跳出循环 while (p=p->next){ printf("%d\t", p->data); } } 复制代码
上述代码和我们尾插法有些许不同，这是因为在此我们要遍历完整个链表，在遍历完后，p的值是NULL。而尾插法中我们是要找到最后一个元素，遍历完后rear的值是尾节点的指针。
（2）求链表长度
求表长我们也需要遍历链表，我们只需要将遍历链表的代码稍作修改即可：
int LengthList(LinkList L){ LNode *p; int i = 0; p = L; while (p=p->next){ i++; } return i; } 复制代码
我们只是将while循环中的语句该成了计数，其它大体没有改变。
（3）销毁链表
销毁链表同样需要遍历操作，我们需要逐个节点调用free函数：
void DestroyList(LinkList L){ LNode *p; p = L; while (L=p->next){ free(p); p = L; } free(p); } 复制代码
有一点需要注意，在我们执行完循环之后，我们的头结点L是指向了NULL，而p则是指向了最后一个节点，所以我们还需要在循环外释放最后一个节点。
（4）通过位置获取链表元素
获取节点同样是一个遍历的操作：
LNode *GetNode(LinkList L, int i){ LNode *p = L; //当位置超出表长返回NULL if(i > LengthList(L)){ return NULL; } //寻找第i个节点 while (i--){ p=p->next; } return p; } 复制代码
我们调用这个函数就可以获取指定位置的节点，这个位置是从1开始，而非0开始，当我们传入位置为0时，则返回的节点为头结点。
（5）指定位置插入元素
指定位置插入元素的操作就是找到指定位置前一个元素，也就是第i-1个元素，然后再插入元素。插入元素的操作同头插法相似。大致步骤如下：
- 获取第i-1个元素
- 创建新节点
- 让新节点的指针域指向第i个元素
- 让第i-1个元素指针域指向新节点
代码实现如下：
int InsertLinkList(LinkList L, int i, ElemType e){ LNode *p, *n_node; //获取第i-1个元素 p = GetNode(L, i-1); if(!p){ return 0; } //创建新节点 n_node = malloc(sizeof(LNode)); n_node->data = e; //让新节点的指针域指向第i个节点 n_node->next = p->next; //让第i-1个元素指针域指向新节点 p->next = n_node; return 1; } 复制代码
五、双向链表和循环链表
双线链表和循环链表是两种特殊的链表，双向链表的节点中提供了两个指针域，分别指向前一个节点和后一个节点。而循环链表则是最后一个节点的指针域并不为空，而是指向第一个节点。下面我们分别看看两种链表如何实现：
（1）循环链表
循环链表将最后一个元素指向了第一个元素，从而形成了闭合的环。循环链表和普通链表占用同样的空间，但是循环链表的操作要更加丰富。我们可以用循环链表实现普通链表的所有操作，而且方法大致一样，我们只需要注意链表判断是否到尾部不再是：
if(p = p->next){} 复制代码
而应该是判断尾节点的指针域是否等于第一个节点：
if(p->next == L->next){} 复制代码
（2）双向链表
在操作双向链表时，我们可以使用普通链表的操作方法，我们只需要在原有的方法上加一个修改前一个节点的指针的步骤即可。我们可以用一下结构表示双向链表的节点：
typedef int ElemType; typedef struct NODE{ ElemType data; //数据域 struct NODE *next, *pre; //指针域 }LNode, *LinkList; 复制代码
因为非常相似，所以就不写完整的实现，下面以insert函数为例：
int InsertLinkList(LinkList L, int i, ElemType e){ LNode *p, *n_node; //获取第i-1个元素 p = GetNode(L, i-1); if(!p){ return 0; } //创建新节点 n_node = malloc(sizeof(LNode)); n_node->data = e; //让新节点的指针域指向第i个节点 n_node->pre = p; n_node->next = p->next; //让第i-1个元素指针域指向新节点 p->next = n_node; return 1; } 复制代码
在上面我们只比原先的代码增加了一句：
n_node->pre = p; 复制代码
双向链表比普通链表耗费更多的空间，但是查找起来也更加方便。
