数据结构（2）—链表
与顺序表相同，链表也是一种线性表，它的数据的逻辑组织形式是一维的。而与顺序表不同的是，链表的物理存储结构是一组地址任意的存储单元存储数据的。也就是说，它不像顺序表那样占据一段连续的内存空间，而是将存储单元分散在内存的任意地址上。
在链表结构中，存储的每个数据元素记录都存放到链表的一个结点（node）中，而每个结点之间由指针将其连接在一起，这样形成一条如同“链”的结构。
在链表的每个结点中，都必须有一个专门用来存放指针（地址）的域，用这个指针域来存放后继结点的地址，这样就达到连接后继结点的目的。一条链表通常有一个“表头”，它是一个指针变量，用来存放第一个结点地址。此外，一条链表的最后一个结点的指针域要置为空，因为它没有后继结点。
链表的结构如下图：
可以看出，链表存在以下特征：
（1）每个结点包括两部分：数据域和指针域。其中，数据域用来存放数据元素本身的信息，指针域用来存放后继结点的地址。
（2）链表逻辑上连续，物理上并不一定连续存储结点。
（3）只要获得链表的头结点，就可以通过指针遍历整条链表。
一个链表结点可用C语言描述如下：
typedef int elemType_t; ///< 以int为例
// 定义参数
typedef struct node_t
{
elemType_t value; ///< 数据域
struct node_t *next; ///< 指针域
} node;链表在很多情况下比数组更有优势，特别是在执行插入或删除操作时链表拥有更高的效率。链表需要动态开辟空间，也就是存储空间是在程序运行时进行分配的。几种链表结构如下：
（1）单链表
单链表由各个元素之间通过一个指针彼此链接起来而组成。每个元素包含两个部分：数据成员和一个 next 指针。通过采用这种两成员结构，将每个元素的 next 指针设置为指向其后面的元素，最后一个元素的 next 指针设置为 NULL。
链表开始处元素是“头”，链表末尾的元素称为“尾”。要访问链表中的某个元素，从链表头开始，通过 next 指针从一个元素到另一个元素连续地遍历直到找到所需要的那个元素为止。以单链表来说，只能从一个方向进行遍历，从头到尾，因为每个元素并没有维护指向其前一个元素的链接；因此，如果从链表头开始移动到某个元素，然后我们又希望访问当前位置之前的某个元素，那么必须再次从头开始。
（2）双向链表
链表元素之间由两个指针链接。双向链表中的每一个元素都由三部分组成：除了数据成员和next 指针之外，还有一个指向其前驱元素的指针，称为 prev 指针。
双向链表的组成是这样的：将一些元素链接在一起使得每个元素的 next 指针指向其后继元素，而每个元素的 prev 指针都指向其前驱元素。为了标识链表的头和尾，将第一个元素的prev 指针和最后一个元素的 next 指针设置为 NULL。
要反向遍历整个双向链表，使用 prev 指针以从尾到头的顺序连续访问各个元素；因此为每个元素增加了一个指针的代价，换来的是双向链表比单向链表提供更为灵活的访问方式。
（3）循环链表
循环链表可以是单向的或双向的，但区分一个链表是不是循环链表只要看它有没有尾部元素。
在循环单向链表中，最后一个元素的 next 指针又指向头元素，而不是NULL；在双向循环链表中，头元素的 prev 指针则指向最后一个元素，这使得循环链表中的每个元素既可以看作头元素也可以看作为尾元素。
1. 创建
创建一个链表的过程，可以用以下代码描述：
/**
* @brief 创建一个链表，包含num个结点
*
* @param *link_list: 所要操作的链表
* @param num: 链表包含的结点数
* @return 无
*
*/
void create_link_list(node** link_list, int num)
{
int i;
node *p_current = NULL;
for(i = 0; i < num; i++)
{
// 创建一个新结点
node *p_tmp = NULL;
p_tmp = (node*)malloc(sizeof(node));
p_tmp->value = 10 + i;
p_tmp->next = NULL;
// 若为空，指向第一个链表结点
if(*link_list == NULL)
{
*link_list = p_tmp;
}
else
{
// 指向p_tmp
p_current->next = p_tmp;
}
// 指向最后的结点，以便生成下一个结点
p_current = p_tmp;
}
}上面这段代码描述了一个建立一条长度为 num 的链表过程，分为以下几个步骤：
（1）用 malloc() 在内存的动态存储区开辟一块大小为 sizeof(node) 的空间，并将地址赋值给 node* 类型变量 p_tmp ；然后将数据 10 + i 存入该结点的数据域 value，指针域存放NULL。
（2）如果指针变量 *link_list 为空，说明本次生成的结点为第一个结点，所以将 p_tmp 赋值给 *link_list 类型变量，只用来指向第一个链表结点，因此它是该链表的头指针。
（3）如果指针变量 *link_list 不为空，则说明本次生成的结点不是第一个结点，因此将 p_tmp 赋值给 p_current->next 。p_current 为一个 node* 类型变量，它永远指向原先链表的最后一个结点，也就是要插入结点的前一个结点。
（4）再将 p_tmp 赋值给 p_current ，目的是使 p_current 再次指向最后的结点，以便生成链表的下一个结点，即保证 p_current 永远指向原先链表的最后一个结点。
2. 插入结点
在指针 q 指向的结点后面插入试点，该过程步骤如下：
（1）先创建一个新结点，并用指针 p 指向该结点。
（2）将 q 指向的结点的 next 域的值（即 q 的后继结点的指针）赋值给 p 指向结点 next 域。
（3）将 p 的值赋值给 q 的 next 域。
以上步骤展示如下：
代码描述如下：
/**
* @brief 向链表中第N个点位置插入结点
*
* @param *link_list: 所要操作的链表
* @param i_pos:插入结点的位置
* @param value:插入结点的值
* @return 返回值：0-失败；1-成功；
*
*/
int insert_list_node(node** link_list, int i_pos, elemType_t value)
{
node *p = NULL, *q = NULL;
// 创建一个新结点
p = (node*)malloc(sizeof(node));
p->value = value;
// 插入位置为起始结点
if(i_pos == 0)
{
p->next = *link_list;
*link_list = p;
return 1;
}
// 得到位置ipos的结点q
q = *link_list;
while((q) && (--i_pos))
{
q = q->next;
}
// 插入位置超过有效范围
if(q == NULL)
{
printf("错误：插入结点位置，超过有效范围%d!\n",i_pos);
return 0;
}
// 若结点为第一个结点
if(*link_list == NULL)
{
*link_list = p;
p->next = NULL;
}
else
{
// p_tmp的link域指向当前的p_current的link域值
p->next = q->next;
// 当前p_current的link指向p_tmp
q->next = p;
}
return 1;
}上面这段代码描述如何在指针 q 指向的结点后面插入结点的过程，包括以下步骤：
（1）首先生成一个新结点，大小为 sizeof(node) ，并将该结点的数据域赋值为 value 。
（2）接下来，根据插入位置 i_pos ，得到 q 结点。
（3） 判断链表是否为空。如果链表为空，则将 p 赋值给 *link_list ，p 的 next 域的值置为空；否则，将 q 指向的结点的 next 域的值赋值给 p 指向结点的 next 域，这样 p 指向的结点就是与 q 指向结点的下一个结点连接在一起。
（4）最后，将 p 的值赋值给 q 所指结点的 next 域，这样就将 p 指向的结点插入到指针 q 指向结点的后面。
3. 删除结点
从非空链表中删除 q 所指的结点，需要考虑以下三种情形。如下：
q 所指向的是链表的第一个结点。
当 q 所指向的结点是链表的第一个结点时，只需要将 q 所指结点的指针域 next 的值赋值给头指针 list，让 list 指向第二个结点，再释放掉 q 所指结点即可。
q 所指向的结点的前驱结点的指针已知。
当 q 所指向的结点的前驱结点的指针已知时（假设为 r），只需要将 q 所指结点的指针域
next的值赋值给 r 的指针域next，再释放掉 q 所指结点即可。
q 所指向的结点的前驱结点的指针未知。
当 q 所指向的结点的前驱结点的指针未知时，需要先通过链表头指针 list 遍历链表，找到 q 的前驱结点的指针，并将该指针赋值给指针变量 r，再按照第二种情形处理即可。
代码描述（已知结点位置，进行删除操作为例），如下：
/**
* @brief 删除链表中的某个结点
*
* @param *link_list: 所要操作的链表
* @param i_pos:删除结点的位置
* @return 返回值：0-失败；1-成功；
*
*/
int delete_list_node(node **link_list, int i_pos)
{
node *q = NULL;
node *r = NULL;
// 删除第一个结点
if(i_pos == 0)
{
q = *link_list;
*link_list = (*link_list)->next;
free(q);
return 1;
}
// 得到ipos位置的结点
q = *link_list;
while((i_pos--) && (q))
{
r = q;
q = q->next;
}
// 删除位置无效
if(q == NULL)
{
printf("ERROR：异常退出，删除结点指针为空！！\n");
return 0;
}
// 删除一个结点
r->next = q->next;
free(q);
return 1;
}4. 销毁链表
链表在使用完毕后，建议销毁它，因为链表本身会占用内存空间。如果一个系统中使用很多链表，而使用完毕后又不及时销毁，那么这些垃圾空间积累过多，最终会导致内存的泄露甚至程序奔溃。
销毁一个链表，代码描述如下：
/**
* @brief 销毁一个链表
*
* @param *link_list: 所要操作的链表
* @return 无
*
*/
void destroy_link_list(node** link_list)
{
node *q, *p;
p = *link_list;
int i = 0;
while(p)
{
printf("释放结点%d，对应数据 %d，下一个结点地址 0x%04x\n", i, p->value, p->next);
q = p->next;
free(p);
p = q;
i++;
}
*link_list = NULL; // 释放内存空间后，指向链表的指针值需要置空
}（1）首先将 *link_list 的内容赋值给 p ，这样 p 也指向链表的第一个结点，成为了链表的表头。
（2）然后判断 p 不为空，就将 p 指向的下一个结点的指针赋值给 q，并应用 free() 释放掉 p 所指向的结点，p 再指向下一个结点。如此循环，直到链表为空。
（3）最后将 *link_list 的内容置为 NULL，这样主函数中的链表就为空了，防止 *link_list 变为野指针，而且链表在内存中也被完全地释放掉了。
5. 示例
#include <stdio.h>
#include <stdlib.h>
typedef int elemType_t; ///< 以int为例
// 定义参数
typedef struct node_t
{
elemType_t value; ///< 数据域
struct node_t *next; ///< 指针域
} node; ///< 定义链表类型
/**
* @brief 输出结点内容
*
* @param *link_list: 所要操作的链表
* @return 无
*
*/
void dump_link_list(node** link_list)
{
int i = 0;
while(*link_list)
{
printf("结点：%d，对应数据：%d，本结点地址：0x%04x，下一个结点地址：0x%04x\n", i, (*link_list)->value, (*link_list), (*link_list)->next);
*link_list = (*link_list)->next;
i++;
}
}
/**
* @brief 创建一个链表，包含num个结点
*
* @param *link_list: 所要操作的链表
* @param num: 链表包含的结点数
* @return 无
*
*/
void create_link_list(node** link_list, int num)
{
int i;
node *p_current = NULL;
for(i = 0; i < num; i++)
{
// 创建一个新结点
node *p_tmp = NULL;
p_tmp = (node*)malloc(sizeof(node));
p_tmp->value = 10 + i;
p_tmp->next = NULL;
// 若为空，指向第一个链表结点
if(*link_list == NULL)
{
*link_list = p_tmp;
}
else
{
// 指向p_tmp
p_current->next = p_tmp;
}
// 指向最后的结点，以便生成下一个结点
p_current = p_tmp;
}
}
/**
* @brief 向链表中第N个点位置插入结点
*
* @param *link_list: 所要操作的链表
* @param i_pos:插入结点的位置
* @param value:插入结点的值
* @return 返回值：0-失败；1-成功；
*
*/
int insert_list_node(node** link_list, int i_pos, elemType_t value)
{
node *p = NULL, *q = NULL;
// 创建一个新结点
p = (node*)malloc(sizeof(node));
p->value = value;
// 插入位置为起始结点
if(i_pos == 0)
{
p->next = *link_list;
*link_list = p;
return 1;
}
// 得到ipos位置的结点
q = *link_list;
while((q) && (--i_pos))
{
q = q->next;
}
// 插入位置有效
if(q == NULL)
{
printf("错误：插入结点位置，超过有效范围%d!\n",i_pos);
return 0;
}
// 若结点为第一个结点
if(*link_list == NULL)
{
*link_list = p;
p->next = NULL;
}
else
{
// p_tmp的link域指向当前的p_current的link域值
p->next = q->next;
// 当前p_current的link指向p_tmp
q->next = p;
}
return 1;
}
/**
* @brief 删除链表中的某个结点
*
* @param *link_list: 所要操作的链表
* @param i_pos:删除结点的位置
* @return 返回值：0-失败；1-成功；
*
*/
int delete_list_node(node **link_list, int i_pos)
{
node *q = NULL;
node *r = NULL;
// 删除第一个结点
if(i_pos == 0)
{
q = *link_list;
*link_list = (*link_list)->next;
free(q);
return 1;
}
// 得到ipos位置的结点
q = *link_list;
while((i_pos--) && (q))
{
r = q;
q = q->next;
}
// 删除位置无效
if(q == NULL)
{
printf("ERROR：异常退出，删除结点指针为空！！\n");
return 0;
}
// 删除一个结点
r->next = q->next;
free(q);
return 1;
}
/**
* @brief 销毁一个链表
*
* @param *link_list: 所要操作的链表
* @return 无
*
*/
void destroy_link_list(node** link_list)
{
node *q, *p;
p = *link_list;
int i = 0;
while(p)
{
printf("释放结点%d，对应数据 %d，下一个结点地址 0x%04x\n", i, p->value, p->next);
q = p->next;
free(p);
p = q;
i++;
}
*link_list = NULL; // 释放内存空间后，指向链表的指针值需要置空
}
int main()
{
// 全局链表
node *link_list = NULL;
node *p_tmp = NULL;
int i = 0, link_list_len = 6;
// 1.创建链表
printf("\n测试创建列表：\n");
create_link_list(&link_list, link_list_len);
p_tmp = link_list;
dump_link_list(&p_tmp);
// 2.插入结点
printf("\n测试插入结点：\n");
insert_list_node(&link_list, 0, 20);
insert_list_node(&link_list, 7, 30);
p_tmp = link_list;
dump_link_list(&p_tmp);
// 3.删除结点
printf("\n测试删除结点：\n");
delete_list_node(&link_list, 0);
delete_list_node(&link_list, 6);
p_tmp = link_list;
dump_link_list(&p_tmp);
// 4.释放链表
printf("\n测试释放结点：\n");
destroy_link_list(&link_list);
if(link_list == NULL)
printf("释放链表成功%d\n", link_list);
return 0;
}示例运行结果如下：
参考来源：
1.《妙趣横生的算法（C语言实现）》 杨峰 编著
2.《算法精解：C语言描述》 Kyle Loudon 著 肖翔 陈舸 译