本文想说的是单向非循环链表的头插。单向非循环链表，可以是带头节点的，也可以是不带头节点的。
对于前者，代码比较简单，后文会说。对于后者，不带头节点的单向链表的头插，我发现即使有多年工作经验的老鸟，也可能写出错误的代码。
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}node_t;
node_t *create_list(void)
{
node_t *head = malloc(sizeof(node_t));
if(head == NULL){
printf("create list failed\n");
return NULL;
}
head->next = NULL;
return head;
}
int insert_head(node_t *head, int num)
{
assert(head != NULL);
node_t *node = malloc(sizeof(node_t));
if(node == NULL)
return -1;
node->data = num;
node->next = head->next;
head->next = node;
return 0;
}
void printf_list(node_t *head)
{
assert(head != NULL);
if(head->next == NULL){
printf("the list is empty\n");
return;
}
node_t *temp = head->next;
while(temp){
printf("%d\n",temp->data);
temp = temp->next;
}
}
int main(void)
{
int a[]={1,2,3,4,5,6};
node_t *head = create_list();
if(head == NULL)
return -1;
for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
{
insert_head(head, a[i]);
}
printf_list(head);
return 0;
}
运行结果是：
6
5
4
3
2
1
把上面的代码改动一下，就可以得到一份错误的代码！
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}node_t;
node_t *head = NULL; // 全局变量，链表的头指针
int insert_head(node_t *head, int num)
{
node_t *node = malloc(sizeof(node_t));
if(node == NULL)
return -1;
node->data = num;
node->next = head;
head = node; // !!!!!! 这里是有问题的
return 0;
}
void printf_list(node_t *head)
{
if(head == NULL){
printf("the list is empty\n");
return;
}
node_t *temp = head;
while(temp){
printf("%d\n",temp->data);
temp = temp->next;
}
}
int main(void)
{
int a[]={1,2,3,4,5,6};
for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
{
insert_head(head, a[i]);
}
printf_list(head);
return 0;
}
你猜运行结果是什么？
结果是：
the list is empty
插入操作失败了。罪魁祸首就是这个函数
int insert_head(node_t *head, int num)
{
node_t *node = malloc(sizeof(node_t));
if(node == NULL)
return -1;
node->data = num;
node->next = head;
head = node; // !!!!!! 这里是有问题的
return 0;
}
为什么不对呢？画图说明。
假设有一个单向链表，头指针 head 的值是 0x200，也就是第一个节点的地址。
调用 insert_head 函数，假设调用者传递的参数是头指针 head 和数字 3（实参），用蓝色表示。
在调用函数时，系统会把实参的值传递给被调用函数的形参（单向拷贝）；
int insert_head(node_t *head, int num) 中的 head 和 num 就是形参；
这里的 head 和全局变量 head 同名，但不是一回事：全局变量 head 是实参，这里的 head 是形参，当然也可以取别的名字；
形参属于函数内的局部变量，在函数被调用的时候，形参的内存在栈上分配，函数执行完毕后，分配的内存被释放，即栈帧被销毁。
假设已经完成了值的拷贝，咱们继续分析：
代码中有三行我标成红色。
首先分配节点的内存，在堆上分配（假设地址是 0x300），用深蓝色表示；然后用 num 和 head 给节点的成员赋值，这都没有问题。继续执行。
注意这句话： head = node;
这导致栈上的 head = 0x300；似乎达到了目的，让 head 指向新插入的节点，但是，函数返回后，栈上的变量都会消失。
最后剩下什么？
链表还是原来的链表，头指针 head 依然指向 0x200；
唯一剩下的就是分配了一个新节点，且这个新节点指向旧的第一个节点。
如果要修改错误的代码，我提供两个思路，第一个就是根据上面的图，返回新的头指针，第二个是用二级指针。
node_t *insert_head_2(node_t *head, int num)
{
node_t *node = malloc(sizeof(node_t));
if(node == NULL)
{
printf("malloc failed\n");
return head;
}
node->data = num;
node->next = head;
return node; // 返回新的头指针
}
主函数修改为：
int main(void)
{
int a[]={1,2,3,4,5,6};
for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
{
head = insert_head_2(head, a[i]);
}
printf_list(head);
return 0;
}
也就是说每次插入都要刷新头指针。
再看第二个方法。
咱们深挖一下这张图，我们的目的不是修改 head 的值，因为他只是头指针的一份拷贝，无论怎么修改，都无法修改函数外面的那个头指针。
那怎么办？我们可以传进来头指针的地址，跑得了和尚跑不了庙，既然拿到了你的内存地址，还怕修改不了你的值？这就是 C 语言的威力，给我一根指针，我能戳动地球！
代码可以这样写：
int insert_head_3(node_t **head, int num)
{
node_t *node = malloc(sizeof(node_t));
if(node == NULL)
{
printf("malloc failed\n");
return -1;
}
node->data = num;
node->next = *head;
*head = node; // 修改头指针的值
return 0;
}
主函数修改为
int main(void)
{
int a[]={1,2,3,4,5,6};
for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
{
insert_head_3(&head, a[i]);
}
printf_list(head);
return 0;
}
再用图解释一下：
假设头指针 head 的地址是 0x800
传参完成后（下图中的黄色部分），分配新节点的内存，在堆上分配（假设地址是 0x300），用深蓝色表示；然后用 num 和 *head 给节点的成员赋值；
注意，*head 表示地址 0x800 中的内容，即 0x200
还有，栈上的变量 head 指向了全局变量——头指针 head
最后一步：修改头指针的值，*head = node;
也就是说，不是把新节点的地址 0x300 赋值给栈上的变量 head，而是赋值给 head 指向的内存。
可以看到，修改成功，头指针确实指向了新节点。
【end】