链表基础
复习：数组
链表和数组的作用相同。都是用来存储数据。因此，使用数组和链表进行类比是一个不错的选择。
数组是很常用的数据结构。在多数语言中，我们都可以很容易的声明一个数组类型，并使用 [] 符号取出其中的元素。 C 语言的示例如下：
void ArrayTest(void) {
int fuc[100]; // 定义数组
// 数组操作
fuc[0] = 1;
printf("%d\n",fuc[0]);
}在此不再赘述。
数组存在如下缺点：
- 数组的大小总是固定的。尽管在 C99 中提供了 VLA ，以及可以使用 reaclloc() 进行动态内存分配。但是那样需要很强的技术。
真的猛士，敢于直面惨淡的手动管理内存，敢于正视淋漓的 errors。 —— 鲁迅
-
因为 1 的问题，大多数普通程序员在新建数组时候总是会偷懒选择一个足够大的数量，保证数据都能被存进去。但是这样就会造成两个问题，其一就是空间的严重浪费，再就是当数据规模真的超过我们预先定义的数据规模时整个程序就会出现问题，轻则某个模块停止运行，重则当场死给你看。
-
在数组的头部插入数据的代价过大。
和数组一样，链表也有自己的优点和缺点。但是链表在数组具有缺陷的地方却恰好很强大。两种数据结构的特征来自于他们的存储策略：数组是一次分配完全部内存，而链表则是在需要时再分配内存。
链表的概念
创建数组时，我们会直接分配出所有我们需要的内存。但是对于链表，我们每次只分配出一个节点（node） 的内存。链表使用指针将各个节点组合到一起，这样就形成了一个连一个的链式的结构，这就是链表（Linked List）这个名称的由来。
链表的每个节点都有两个部分：数据区和指针区。前者用来存储数据，后者用来存储指向下一个节点的指针。我们使用 malloc() 函数来为每个节点分配内存。节点的头部只含有指向第一个节点的指针。如下是一个数据为{1,2}的链表。
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | --------- ---------
|
|
|其中，存储在栈区的 head 指向了存储在堆区的节点。堆区的节点又互相连接，形成链状的结构。最后一个节点的指针区被赋值为 NULL，标明了链表的结束。因为上图的链表存储了两个节点，所以该链表的长度为 2。长度为 0 的链表，或者说叫空链表，通常以 NULL 指针表示。空链表是链表操作的最常见的一个边界条件，本文所述代码肯定是能完美处理这种条件的。当读者在自己实践时，考虑这种状况是一种很有益处的思维训练。
链表结构
在我们开始讨论代码实现时，我们需要定义一些结构。
本文中的定义如下：
struct node {
int data;
struct node* next;
}
typedef struct node node_t;
typedef struct node* nodeptr_t;这里使用到了 C 语言的结构体的自引用（Self reference），就是在结构体内部，包含指向自身类型结构体的指针。
注意：
本文中代码并未处理 malloc() 函数执行失败时的错误处理，在实际使用时是需要进行处理的。
示例
下面是生成上文提到的链表的具体函数：
nodeptr_t BuildOneTwo() {
nodeptr_t head = NULL;
nodeptr_t second = NULL;
head = malloc(sizeof(node_t));
second = malloc(sizeof(node_t));
head->data = 1;
head->next = second;
second->data = 2;
second->next = NULL;
return head;
}练习
使用最少的等于号生成上文那样的数据结构。我们需要两个等于号调用 malloc()，两个用来存储数据，还有三个用来设置连接关系。但是使用一点小技巧，我们能将等于号的数量降到 5 个。
nodeptr_t BuildOneTwo() {
nodeptr_t head = malloc(sizeof(node_t));
head->data = 1;
head->next = malloc(sizeof(node_t));
head->next = 2;
head->next->next = NULL;
return head;
}建立链表
上一部分提到的 BuildOneTwo() 函数就是很好的建立链表的示例。根据那个函数，我们可以抽象出建立链表的几个基本操作：
-
分配内存
-
存储数据
-
处理指针
基于此，不难写出建立一个只有一个节点的链表的函数，示例如下：
nodeptr_t NewLinkedList(int val) {
// 建立第一个节点
nodeptr_t head = NULL
head = malloc(sizeof(node_t));
head->data = val;
head->next = NULL;
return head;
}链表的基本操作
本节介绍的是链表的基本操作。
1. 遍历链表
对于链表，最常见的操作就是遍历链表。比较常见的实现方法是使用 while 语句实现：首先将头指针 (head) 复制到临时变量 current 里。使用 while 测试 current 是否为空指针，最后在循环体里移动指针。示例如下：
// 输入：链表的头节点
// 输出：链表的长度（节点个数）
int Length(nodeptr_t head) {
int count = 0;
nodeptr_t current = head;
while (current != NULL) {
count++;
current = current->next
}
return(count);
}也有很多人使用一个 for 循环来简化步骤（比如懒人如我）…
for (current = head; current != NULL; current = current->next) {2. 在链表结尾添加数据
除了遍历链表之外，最常用的操作就是添加和删除数据了。下面的几个操作都是添加/删除数据。
首先我们来看在链表的结尾添加数据。要想在链表的结尾添加数据，我们要做的事情有如下几件：
-
找到链表末尾的节点
-
新建节点，存储数据，处理指针
-
在将链表的结尾指向刚刚新建的节点
以下是代码示例：
void AppendNode(nodeptr_t head,int val) {
// 获取最后一个指针的地址
for (current = head; current->next != NULL; current = current->next);
// 建立新节点，处理指针
nodeptr_t newNode = malloc(sizeof(node_t));
newNode->next = NULL;
// 进行链接
current->next = newNode;
}使用 current 而不是直接改变 head 的原因：
笔者不习惯直接修改（滑稽）
下面以向链表 {1,2} 的结尾添加数据 3，为例演示全过程。
首先是最初的链表：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | --------- ---------
|
|
|第一步完成之后：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | --------- ---------
| /|\
| |
--------- | |
current| * + ----------------------------
--------- |
|第二步：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | --------- ---------
| /|\
| |
--------- | |
current| * + ----------------------------
--------- |
| newNode
| ---------
| | 3 | / |
| ---------第三步：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | * +---
--------- | --------- --------- |
| /|\ |
| | |
--------- | | |
current| * + ---------------------------- |
--------- | |
| newNode |
| --------- |
| --->| 3 | / | |
| | --------- |
| ------------------在函数调用者的视角里，链表变成了这样：
Stack | Heap
|
|
--------- | --------- --------- ---------
head | * + -------> | 1 | * +----->| 2 | * +----->| 3 | / |
--------- | --------- --------- ---------
|
|
|就这样，一个全新的链表就诞生了！
3. 在链表结尾删除数据
删除数据和添加数据有着一定的共性，因此笔者将删除数据和添加数据放在一起说明。
与添加操作类似，删除操作要做的又如下几步：
-
找到链表倒数第二个节点（因为需要修改这个节点的next为 NULL）
-
删除其下一个节点
-
修改 next 为 NULL
根据步骤我们可以写出 C 代码,需要注意的是这次我们需要处理链表长度为 1 的特殊情况：
void RemoveLast(nodeptr_t head) {
int retval = 0;
// 特殊情况处理
if (head->next == NULL) {
retval = head->val;
free(head);
return;
}
// 找出倒数第二个节点
nodeptr_t current = head;
while (current->next->next != NULL) {
current = current->next;
}
// 删除最后一个节点
free(current->next);
current->next = NULL;
return;
}下面演示删除链表 {1,2} 中的最后一个节点：
第一步：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | --------- ---------
| /|\
| |
--------- | |
current| * + --------------
--------- |
|第二步：
Stack | Heap
|
|
--------- | --------- ----------
head | * + -------> | 1 | * +----->|被free辣 |
--------- | --------- ----------
| /|\
| |
--------- | |
current| * + --------------
--------- |
|第三步：
Stack | Heap
|
|
--------- | --------- ----------
head | * + -------> | 1 | / | |被free辣 |
--------- | --------- ----------
| /|\
| |
--------- | |
current| * + --------------
--------- |
|就这样我们删除了链表的一个节点。
基于这个函数，我们可以写出删除整个列表的函数，如下：
void RemoveLinkedList(nodeptr_t* head) {
// 删除到只剩一个节点
while(*(head->next) != NULL)
RemoveLast(*head);
// 删除头节点
RemoveLast(*head);
// 最后将链表置空
*head = NULL;
return;
}需要注意的是我们在这里传递的是链表头结点指针的指针，因为我们需要修改头指针的数值为 NULL。
4. 在链表头部添加数据
在头部添加数据不是很难，步骤如下：
-
新建节点，存储数据
-
让新建节点的 next 指向之前的头节点
-
将头节点指针指向刚刚新建的节点。
代码如下：
void Push(nodeptr_t* head, int val) {
// 新建节点，存储数据
nodeptr_t newNode;
newNode = malloc(sizeof(node_t));
newNode->val = val;
// 让新建节点的 next 指向之前的头节点
newNode->next = *head;
// 将头节点指针指向刚刚新建的节点。
*head = newNode;
}下面演示在链表 {1,2} 的前面插入数据 0：
第一步：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | --------- ---------
|
|
|
|
|
|newNode
|---------
|| 0 | / |
|---------第二步：
Stack | Heap
|
|
--------- | --------- ---------
head | * + -------> | 1 | * +----->| 2 | / |
--------- | | --------- ---------
| |
| |
| -----------
| |
| |
|newNode |
|--------- |
|| 0 | * +----
|---------练习
根据上文提到的知识和方法，写出删除链表第一个节点的函数，函数声明已给出。
void RemoveFirst(nodeptr_t* head);5. 在任意节点添加删除数据
在任意节点（不考虑头节点和尾节点）添加数据的步骤：
-
新建节点，存储数据
-
找出要添到的节点的上一个节点的位置（记为 P）
-
将新建节点的 next 修改为 P 的 next 值
-
将 P 的 next 修改为新建节点的位置
在任意节点（不考虑头节点和尾节点）删除数据的步骤：
-
找出要删除的节点的上一个节点的位置（记为 P）
-
记录下要删除的节点的位置
-
将 P 的 next 值修改为要删除的节点的 next 指针的值
-
释放内存
这两个操作的实现请读者自己尝试实现。
链表的其他几种实现方式
除了上面所述的最基础的链表之外，还有很多种进行过改动的链表实现方式。每种方式都有各自的优点。不过，在关心魔改版实现之前，最好好好理解基础的链表知识，确保你能理解之后再继续前进。
-
空头列表 为了防止再链表为空时出现头指针为 NULL 的情况。这种链表采用了一个没有数据只有指向 NULL 的指针的节点标志链表为空。这种的好处就是对于 Push 那种操作，我们不需要传递指针的指针进去。而且一些迭代操作的进行会比较简单。缺点就是会浪费内存空间。再就是有些算法的实现不怎么优雅。
-
环状链表 将尾指针的.next字段设为头指针的链表。指向任何一个节点的指针都可以被视为头指针。
-
双向链表 在链表的结构里添加一个 prev 字段，指向上一个节点。这种链表插入/删除元素需要的操作比较多。但是其他操作都被大大地简化了。
-
块链表 在一个链表节点内存储多个数据。