基本数据结构 -- 链表概述
一、线性表
通俗的讲，表就是按顺序排好的元素集合。形如：A1,A2,A3,...,An 这样的有限元素序列，就是一个线性表，这个线性表的大小是 n。称大小为 0 的表为空表。
对于除空表外的任何表，除表头元素和表尾元素外，其他元素都有一个前驱元（排在该元素前面）和一个后继元（排在该元素后面），如： Ai 的前驱是 A(i-1)，Ai 的后继是 A(i+1)。表头元素没有前驱，表尾元素没有后继。线性表有两种表示形式：顺序结构和链式结构。线性表的顺序结构其实就是数组，链式结构就是链表。二者各有优缺点，简单来说，对顺序表进行查找操作效率很高，但是插入和删除操作效率很低；而对链表进行插入和删除操作效率很高，查找操作则效率较低。本文先简单介绍一下链表。
二、链表
链表是一种物理存储单元上非连续、非顺序的存储结构，表中的各对象按线性顺序排列。
2.1 链表的构成
链表由一系列不必在内存中相连的结构（结点）组成。每个结点均含有一个表元素 key 和一个指向包含该元素后继元的结点的指针，称之为 Next 指针。表中最后一个结点的 Next 指针指向 NULL，ANSI C 规定 NULL 为零。与数组下标的方式不同，链表的顺序是由结点里的指针决定的，因此链表可以在物理内存上非连续存储。对于双向链表，每个结点除了包含一个元素 key 和一个 next 指针外，还包含一个指向该元素前驱元的结点的指针，称为 prev 指针。结点中还可以包含其他的辅助数据（或称为卫星数据）。
设 p 为链表的一个结点，则 p->next 指向它在链表中的后继，p->prev 指向它的前驱。如果 p->prev = NIL，则表明结点 p 没有前驱，因此结点 p 是链表的第一个结点，即链表的头（head）。如果 p->next = NIL，则表明结点 p 没有后继，此时结点 p 是链表的最后一个元素，即链表的尾（tail）。
上图是一个有五个结点的单链表，每个结点由表元素和一个 next 指针组成。 链表的尾结点的 next 指针指向 NIL，表明这个结点没有后继，是链表的尾。
2.2 表头结点（哑结点）
通常，我们在创建一个链表时，会创建一个表头（header）或哑结点，我们约定，这个结点在位置 0 处，指向表头元素。表头结点本身是不存放数据的，只含有一个 next 指针。使用表头结点可以使得链表的删除操作变得更加简单而有条理。带有表头结点的链表示意图如下：
链表由表头结点唯一确定，单链表可以用表头结点的名字来命名。
注：笔者总是表头结点和表头傻傻分不清，其实这两个是不一样的，表头是链表的头结点，也就是链表的第一个结点；而表头结点是我们人为创建的，并不真的属于链表，只是我们为了方便使用链表才创建的一个结点，它不存放数据，且其 next 指针指向表头，因此，笔者觉得称其为表头指针似乎更好懂一些。
2.3 链表的分类
链表可以有多种形式。它可以是单链接的（单链表）或双链接的（双链表），可以是已排序的或未排序的，可以是循环的（循环链表）或非循环的。如果一个链表是单链接的，则省略每个元素中的 prev 指针。如果链表是已排序的，则链表的线性顺序与链表元素中关键字的线性顺序一致，此时，最小的元素就是表头元素，而最大的元素则是表尾元素。如果链表是未排序的，则各元素可以以任何顺序出现。一般而言，分这几种：
1）单链表
单链表的每个结点由一个元素（数据）加上一个指向后继元的 next 指针组成，链表的表尾结点没有后继，表头（第一个结点）没有前驱。若创建一个带有表头结点（header）的单链表的话，则 header 的指针将指向表头。单链表可以用表头结点的名字来命名。用一个例子来说明一下，以帮助理解：
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "windows.h"
struct list_node{
int key; // 结点数据
struct list_node *next; // next 指针，指向下一个结点
};
typedef struct list_node *PtrToNode;
typedef PtrToNode SingleList;
typedef PtrToNode Position;
/* 创建单链表 */
SingleList creat_single_list(int listlen)
{
int list_len = listlen;
int i;
/* 创建一个头结点 */
PtrToNode head_node = NULL;
head_node = (PtrToNode)malloc(sizeof(struct list_node)); // 为头结点分配内存空间
if (head_node == NULL) {
printf("malloc fair\n");
}
/* 创建一个末尾结点 */
PtrToNode tail_node = head_node;
tail_node->next = NULL;
/* 添加其他结点 */
for (i = 0;i < list_len;i++) {
PtrToNode new_node = (PtrToNode)malloc(sizeof(struct list_node));
if (new_node == NULL) {
printf("malloc fair\n");
}
new_node->key = i;
tail_node->next = new_node;
new_node->next = NULL;
tail_node = new_node;
}
printf("链表创建成功\n");
return head_node; // 返回头结点
}
这段代码可以用于创建一个单链表，可以看到，函数 creat_single_list 的返回值是一个头结点，我们可以使用这个头结点来表示这个单链表，对链表进行遍历、删除、插入等操作。
2）双链表
双链表的每个结点中有两个指针，一个指向后继（next 指针），一个指向前驱（prev 指针）。因此，从双链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，如图：
双链表在单链表的基础上增加了一个域，相当于增加了一个附加的链（反向的），它增加了空间的需求，同时也使得插入和删除的开销增加一倍，因为有更多的指针需要定位。但是，在需要倒序扫描链表的时候，使用双链表是个很好的选择，而单链表则对此无能为力。
3）循环链表
循环链表的表尾结点的 next 指针指向表头（第一个结点）。这种结构可以由表头结点（哑结点），也可以没有表头结点，若有，则表尾结点的 next 指针指向它，也可以是双链表（第一个结点的 prev 指针指向最后一个结点）。通常，循环链表与双链表结合起来使用，也就是双向循环链表，这在许多场合都有重要的应用。举个例子，Linux 内核中的进程描述符 task_struct 就是存放在一个双向循环链表中的。
如图，为一个无表头结点的双向循环链表。
三、链表与数组
链表和数组都是由一组元素以一种特定的顺序组合在一起形成的一个集合，对链表的所有操作（遍历、查找、插入、删除）都可以通过使用数组来实现，二者也各有优缺点。
1）数组虽然可以动态指定大小，但是还是需要对表的大小的最大值进行估计，通常需要估计得大一些，这样会浪费大量的空间，特别是在许多表的大小未知的情况下；而链表的存储空间是在程序运行时进行分配的，这相对数组来说是一个优势，用则申请，不用则释放，可以大大提高内存利用率；
2）链表中的元素在内存中不是顺序存储的，而是通过结点之间的指针联系到一起，因此，要对链表进行查找的话，需要从第一个元素开始，一个结点一个结点地往下找，而数组进行查找操作的话则相当简单，使用数组下标即可；但是相对的，对链表进行删除和插入操作则很简单，而数组的话则需要花费大量时间将所有元素后移或前移一位；