链表和指针的理解##
看到CoolShell上关于Linus利用二阶指针删除单链表节点的文章，文章提到Linus大叔感叹“这个人不了解指针”，那我们又理解指针了吗？
以下分别是文中用一阶指针和二阶指针删除单链表节点的代码：
-
一阶指针版###
typedef struct node {
struct node *next;
...
}node;
node *remove_if(node *head, remove_fn rm)
{
for (node *prev = NULL, *curr = head; curr != NULL) {
node *const next = curr->next;
if(rm(curr)) {
if (prev)
prev->next = next;
else
head = next;
free(curr);
} else {
prev = curr;
}
curr = next;
}
return head;
}
-
二阶指针版###
void remove_if(node ** head, remove_fn rm)
{
for (node **curr = head; *curr; ) {
node *entry = *curr;
if (rm(entry)) {
*curr = entry->next;
free(entry);
} else {
curr = &entry->next;
}
}
}
同样是删除单向链表的节点，采用二阶指针使得代码更加简练：
- 对头结点不再需要特殊的判断
- 不需要将链表头作为返回值
为什么呢？！CoolShell该文中提到了core low-level coding。那我们不妨从low-level来思考这个问题。
维基百科对指针的实质是这样解释的：指针其实是一个整数
计算机中的内存都是编址的，每个地址都有一个符号，就像家庭地址或者IP地址一样。在C语言的多数实现中，指针值等同于一个无符号整数（unsigned int，因不致歧义，下简称“整数”），它是一个以当前系统寻址范围为取值范围的整数。声明一个无符号整数并使它的值等于对象的地址值，实质上也能使之有指针的作用。
上面的描述说明，指针提供给我们一个更贴近机器的角度，从机器的视角来看待链表：
计算机中的内存都是编址的，每个地址都有一个符号，我们把这个符号（指针）保存下来（指针变量），组成一个序列，我们无需改变内存中的值，只需要调整这些指针变量的排列顺序，就能得到一个不同的序列；
从这个角度看，链表不是内存单元的序列，而是内存单元指针变量的序列；也就是说，对链表的操作，本质是对指针变量的操作。
理解了以上的文字，不妨做个小练习：用二阶指针的方法实现链表的插入（前向插入），照虎画猫，是不是很容易！下面是我的实现：
一阶指针版本###
typedef struct node {
struct node *next;
...
}node;
typedef node *position;
typedef node *element;
node *insert(node *head, position p, element e)
{
for (node prev = NULL, *curr = head; curr; ) {
if (curr == p) {
if (prev) {
e->next = curr;
prev->next = e;
return head;
} else {
e->next = curr;
return e;
}
} else {
prev = curr;
}
cur = cur->next;
}
}
二阶指针版本###
void insert(node **head, position p, element e)
{
for (node **curr = head; *curr; ) {
if (*curr == p) {
e->next = p;
*curr = e;
} else {
curr = &((*curr)->next);
}
}
}