链表是一种极其重要的数据结构，因为对指针和抽象思维的要求较高，一度成为身边同学最痛恨的对象。
我在将这里演示如何使用链表制作一个可以按位储存数字的容器。鉴于本人亦初学者，有错误请各位在评论区指正。
这里还是以介绍链表为主，算法部分苦于我表达力不足，只能尽量多写注释，望海涵。
链结是链表最基本的结构。
//链结的结构其实非常简单
//typedef 的声明方式可以避免之后重复写struct。
//C++选手可以无视这种方法。
typedef struct _Node
{
//Data field
int num;
//Pointer, points to the next node.
_Node* next;
}Node;
num用来存储一位数字，每一个Node代表一位数。
严格按照如下概念图来构造链表：
链表的头和尾是确定的（Head和NULL）。
//如果忽略head存储的值，这就是一个简单的空链表。
Node* Head={val,NULL};
//不过更常见的是下面这种方式：
//我们需要的不过是一个可以指向链结的东西
Node* Head=NULL;
我们要做的就是实现一个可以向里面添加链结的函数，来扩充我们的链表。
添加链结最主要的方法有3：头插法、尾插法、中插法。中插法更适合因地制宜地去使用，这里主要演示前两种。
·
//头插法
//返回的是指向新加入的链结的指针
Node* add(Node** phead,int val)//要改变指针本身，就传入指针的地址。
{
//构建一个待插入的链结
Node* node=(Node*)malloc(sizeof(Node));
/*一定要使用malloc把node存储在堆区（heap），
直接在函数内声明的变量会在函数调用结束的时候灰飞烟灭
这样返回的指针指向的地址没有意义。*/
node->num=val;
node->next=NULL;//养成好习惯
//把链结node加入链表中去
Node* temp=*phead;
*phead=node;
node->next=temp;
return node;
}
·
如果暂时感觉到难以理解，不妨拿起纸笔画一下上面的概念图，理清思路，体会一下C语言的招牌特色：面向过程。
`
//由add可以实现一个链表构造函数
Node* struct_list(int num)//输入需要的节点数量
{
Node* head = NULL;
for(int ix = 0; ix < num; ix++)
add(&head, val);//val值随意
return head;
}
`
尾插法比头插法复杂一些，需要用一个静态变量static Node* tail来记录链表尾的位置。static变量存在于静态区，在整个文件中有效，不用担心会被刷新。
因为其文件作用域特性，static有时候也会被用来声明一个只在这个源代码文件中有效的变量。而不加static会变为全局变量(global variable)。
//尾插法
Node* add(Node** phead,int val)
//构建一个待插入的链结
Node* node=(Node*)malloc(sizeof(Node));
node->val=val;
node->next=NULL;
//把链结node加入链表中去
static Node* tail=NULL;//避免野指针
if(!phead)//在这里，需要判断链表是否非空
{
*phead=node;
tail=node;
}
else
{
tail->next=node;
tail=tail->next;
}
return node;
}
也可以基于这个原理写一个构造链表函数。你依然可以根据自己的想法去实现更有特色的构造链表函数。
其实要实现主题功能，学习到这里就已经够了。不过我这里还是会介绍一下链表其他的操作以及其对应的函数。
哦，别忘了删除链表，及时释放内存：
void release_list(Node** phead)
{
Node* tail,*ptr;
if(!*phead)//空链表，无需释放，退出
return;
for(tail=*phead,ptr=tail->next; ptr; tail=ptr,ptr=ptr->next)
free(tail);
//链表的for遍历
free(tail);
*phead=NULL;
}
我们注意到在如上代码里面有两种常见的代码写法：
Node* ix;
for(ix = head; ix; ix = ix->next)
用指针迭代链表是非常重要的操作，ix=ix->next是指针移动的方式。
条件 ix 可用是因为NULL有如下宏定义：
#define NULL 0
//限定Visual Studio 2019
//C++是nullptr
//相应的，一般对指针操作时要保证指针非空，可以采取如下形式：
if(ptr&&(Condition))
...
掌握了如上原理，以下的操作可以自己实现
void print_list(const Node* head)//不希望改变值，使用const
{
for (; head ;head = head->next)
printf("%-4d", head->num);//%-4d表示用4格空间，左对齐打印一个int。
}
可能有一点难度，不妨对照概念图多试几次
void delete_node(Node** phead,int key)
{
Node *tail = *phead, *ptr = NULL;
if(!tail)//空链表，异常
return;
ptr = tail->next;
while(ptr)//从第二个开始搜索目标，如果只有一个链结，循环就不会执行
{
if(ptr->num==key)
{
tail->next = ptr->next;
free(ptr);
ptr = tail->next;
}
else
{
tail = ptr, ptr = ptr->next;
}
}
if((*phead)->num==key)//检查第一个是不是目标
{
*phead = ptr;
free(*phead);
if(ptr)
{
tail = ptr;
ptr = ptr->next;
}
}
}
*：搜索链结不妨自己试一下。
这是leetcode里面的一道题，同前面两数之和难度形成对比。。
原题：
对于用链表倒序表示的两个数，要求实现两数相加
考虑情况：
1，进位
2，链表不等长（相加的数的位数不一）
3，和的位数高于两链表位数，需要添加。
//我们可以在刚才的基础下，构建这样一个算法。
//假定两个链表l1，l2已经给出。
Node* addNumbers(Node* l1, Node* l2)
{
Node *head = NULL;//新链表
Node *tail = NULL;
int carry = 0;//进位值
int n1, n2;//两数
int sum = 0;//两数相加
while (l1||l2)//解决问题2，取l1,l2最长长度
{
n1 = l1 ? l1->num : 0;
n2 = l2 ? l2->num : 0;//不够长的部分视作0
sum = n1 + n2 + carry;
carry = sum / 10;//利用窄化，抛弃小数部分
if(!head)//第一次执行，tail未曾初始化
{
head = (Node *)malloc(sizeof(Node));
*head = Node{sum % 10, NULL};//结构体字面量，也叫做无名结构体
tail = head;
}
else//tail 已经初始化
{
tail->next=(Node*)malloc(sizeof(Node));
tail=tail->next;
tail->num=sum%10;
tail->next=NULL;
}
if(l1)//向后推
l1 = l1->next;
if(l2)
l2 = l2->next;
}
if(carry>0)//注意最后一位可能还需要进位
{
tail->next = (Node *)malloc(sizeof(Node));
*tail->next = Node{carry, NULL};
}
return head;
}