- 这篇文章并不解释“链表是什么”；我们的重心是“链表如何用c++实现”；
- 由于我没有画图，所以在看这篇文章之前，我希望读者已经对链表的定义有了一个粗略的了解。可以谷歌 "singly-linked list visualization"。
单向链表是数据结构的第一课。虽然是无比简单的内容，但如果不能对链表有一个非常清晰的理解，后面的学习会变得十分痛苦。所以我想花点儿时间在链表的代码实现上。先人画了无数张图，摆事实讲道理，来帮我们理解链表的操作。然而对图的理解如果不能落实到代码上，再好也是空中楼阁。
先用c++写一个简单的链表实现：
struct Node{
int val;
Node *next;
};
在c++中，最简单的实现链表的方法就是结构体。著名的OJ，LeetCode，对链表的定义是这样的：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
作为一只小白，我没能理解最后一句"ListNode(int x) : val(x), next(NULL) {}"，不过我猜是构造函数什么的。等我学明白了再回来补坑~
当我们获得了一只结构体用来作为链表的数据类型，我们就可以开始创建这个链表啦：
Node *create(){ //返回值是Node类型的指针，也就是head
Node *head, *temp; int num, n;
//new运算符用以获得一片用来存放一个Node类型变量的存储空间，并且把这片存储空间的地址赋给head
head = new Node; temp = head;
cin>>num;
while(num != -1){
n++;
temp->val = num;
//c++中，如果我们需要动态地申请新的内存空间，记得一定要用new运算符
temp->next = new Node;
temp = temp->next;
cin>>num;
}
if (n==0) head = NULL; else temp->next = NULL;
return head;
}
因为自己曾经为Node *create()这条语句困惑过，所以这里想解释一下另一个知识点：指针作为函数返回值。
函数的返回值可以是多种类型：
- 返回int类型的函数：
int function (int x, int y);- 返回指针类型数据的函数：
int *function (int x, int y);
-- 函数名字前面表示函数的类型 “*”
所以Node *create()就代表这个函数会返回一个Node类型的指针，也就是head。
接下来，链表的遍历：
Node *pointer = create();
while(pointer->next != NULL){
cout<<pointer->val<<endl;
pointer = pointer->next;
}
链表的删除需要分两种情况讨论：
- 链表为空（极端情况，任何时候都要考虑到）；
- 待删除节点是链表的头结点；
- 带删除节点不是头结点。
所以我们需要两个指针，一个指向待删除节点，一个指向该节点前一个节点。当我们要删除当前节点时，直接把待删除节点的next赋给前一个节点的next。赋值之后，前一个节点的next就会指向待删除节点的next，也就是说待删除节点在这条链表中，已经不存在了。
（这个过程如果用语言来表述，会显得有点儿复杂。建议大家还是去找图看，然后再配合代码来理解。如果能自己动手敲一敲，相信会有更加深刻的体会。）
Node *dele(Node *head, int n){
Node *temp, *follow;
temp = head;
if (head == NULL) return head;
if (head->val == n){
head = head->next;
delete temp;
}
while (temp!= NULL && temp->val != n){
follow = temp;
temp = temp->next;
}
if (temp == NULL) cout<<"Not Found";
else{
follow->next = temp->next;
delete temp;
}
return head;
}
添加新节点的话，也同样需要分情况讨论：
- 链表为空，则把新节点unit赋给head就好；
- 新节点是链表的第一个节点；
- 新节点是链表最后一个节点；
- 新节点在链表中间。
小心哦，极端情况都有可能成为竞赛以及面试中的超级大坑_(:зゝ∠)。
代码如下：
Node *insert(Node *head, int n){
Node *temp, *follow, *unit;
temp = head;
unit = new Node; unit->val = n; unit->next = NULL;
if (head == NULL){ //情况1：空链表，则设新节点为head并返回
head = unit;
return head;
}
//这里我们自动默认链表是sorted了，如果有别的情况要自己写合法判断哦。
while((temp->next != NULL) && (temp->val < n)){ //找到需要添加新节点的位置
follow = temp;
temp = temp->next;
}
if(temp == head){ //情况2：要插入的节点会是新的头结点
unit->next = head;
head = unit;
}
else{
if(temp->next == NULL) temp->next = unit; // 情况3：新节点是尾节点
else { //情况4：新节点在链表的中间
unit->next=temp;
follow->next=unit;
}
}
return head;
}
就酱，我滚去继续敲doubly-linked list辣 ( _ )/~~
参考资料：
- LeetCode Online Judge
- 北京大学良心网课：C程序设计进阶 （稍微安利一发，个人很喜欢李戈老师老师的讲课风格。可谓“谈笑间，樯橹灰飞烟灭”：信手拈来，层层深入，妙趣横生又获益无穷。）
- UCSD良心网课：Data Structures
