剑指offer面试题13扩展------Linus：利用二级指针删除单向链表

Torvalds大婶：很多人不了解如何写核心底层代码 Torvalds大婶在slashdot上回答一些编程爱好者的提问，其中一个人问他什么样的代码是他所喜好的，大婶表述了自己一些观点之后，举了一个指针的例子，让我们见识了什么才是core low-level kind of coding。 At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I've seen too many people who delete a singly-linked list entry by keeping track of the "prev" entry, and then to delete the entry, doing something like 在这段话的最后，我实际上希望更多的人了解什么是真正的核心底层代码。这并不像无锁文件名查询（注：可能是git源码里的设计）那样庞大、复杂，只是仅仅像诸如使用二级指针那样简单的技术。例如，我见过很多人在删除一个单项链表的时候，维护了一个"prev"表项，然后删除当前表项，就像这样 if (prev) prev->next = entry->next; else list_head = entry->next; 复制代码 and whenever I see code like that, I just go "This person doesn't understand pointers". And it's sadly quite common. 当我看到这样的代码时，我就会想“这个人不了解指针”。令人难过的是这太普遍了。 People who understand pointers just use a "pointer to the entry pointer", and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a "*pp = entry->next". 了解指针的人会使用链表头的地址来初始化一个“指向表项指针的指针”。当遍历链表的时候，可以不用任何条件判断（注：指prev是否为链表头）就能移除某个表项，只要写"*pp = entry->next"。 So there's lots of pride in doing the small details right. It may not be big and important code, but I do like seeing code where people really thought about the details, and clearly also were thinking about the compiler being able to generate efficient code (rather than hoping that the compiler is so smart that it can make efficient code *despite* the state of the original source code). 纠正细节是令人自豪的事。也许这段代码并非庞大而且重要，但我喜欢注重代码细节的人，以及那些清楚地了解如何编译出有效代码的人（而不是寄望于聪明的编译器来产生有效代码，即使是那些原始的汇编代码）。 收藏分享
Talk is cheap, show me the code——空谈误国，实干兴邦！

GentileHP 金牌会员	2# 发表于 2013-2-1 08:35|只看该作者 Torvalds举了一个单向链表的例子，但给出的代码太短了，有个爱好者阅读了这段话，并给出了一个比较完整的代码。他的话我就不翻译了，下面给出代码说明。 一个深中教科书的毒的人会这样写，这种写法也是大公司的面试题标准模板： typedef struct node { struct node * next; .... } node; typedef bool (* remove_fn)(node const * v); // Remove all nodes from the supplied list for which the // supplied remove function returns true. // Returns the new head of the list. 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; } 复制代码 这里remove_fn是判断删除条件的函数指针。这段代码维护了两个节点指针prev和curr，标准的教科书写法，这里还需要额外判断curr是否为链表头。 在Torvalds看来什么是core low-level kind of coding呢？那就是有效地利用二级指针，并且将其作为变动一个链表的首要选项。 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; } } 复制代码 同上一段代码有何改进呢？我们看到不需要再去判断是否为链表头了，所有的删除节点的动作都是通过第8行的语句实现的。下面用我自己的话来说明一下为何要用二级指针，以及怎样做到的。
Talk is cheap, show me the code——空谈误国，实干兴邦！
	TOP

GentileHP 金牌会员	3# 发表于 2013-2-1 09:22|只看该作者 本帖最后由 GentileHP 于 2013-2-3 14:03 编辑 我们将链表用内存映像的方式图解说明（画得不好，呵呵），假设有三个节点，它们的地址分别是0x0000，0x0010，0x0020，第一个是表头，每个节点16个字节，第一个字节是next，它是个节点指针，指向下一个节点地址。 ------------- 此处乃节点A地址，类型为struct node*<- 0x0000 | 0x0010 |-> 这里是next值，指向下一个节点，也是个struct node* ------------- | | ------------- | | ------------- | | ------------- 节点B <- 0x0010 | 0x0020 | ------------- | | ------------- | | ------------- | | ------------- 节点C <- 0x0020 | 0x0030 | ------------- | | ------------- | | ------------- | | ... 实现代码如下 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; } } 复制代码 我们知道，要删除一个节点（不是表头），只要将前一个节点的next指向当前节点的next指向的对象，即下一个节点，然后释放当前节点。我们看到这个语句是第8行，那么*curr是什么呢？ 我们先分析删除节点不是表头的情况，curr是个二级指针，从第12行看到，它指向的是当前节点的next。举个例子，如果循环中entry是节点A的话，在不删除这个节点的情况下，就会执行else中的语句，*curr的内容就是0x0010即节点B的地址。假设第二遍循环要删除节点B，那么第8行的作用就是讲节点A的next内容变为0x0020，即节点C的地址，然后就可以释放第二个节点了。 再分析删除节点是表头的情况，输入参数中传入head的二级指针，在for循环里将其初始化curr，然后entry就是*head(*curr)，我们马上删除它，那么第8行就等效于*head = (*head)->next，就是删除表头的实现，是不是很巧妙？ 我们来看看为何大婶的改进方法省略了表头判断这一步，这是数据结构功劳，还记得当初struct node是怎样定义的吗？ typedef struct node { struct node * next; .... } node; 复制代码 看到没？链接定义在第一个成员变量的位置！也就是说，当我们用一个二级指针curr去指向当前节点地址的时候，对其引用*curr就是上一个节点next值。在不删除表头的情况下，比如entry是节点B，第8行语句中的*curr就是节点A的next引用，然后将其改写为节点B的next的值，也即节点C地址。在删除表头的情况下，即entry是节点A(*head)，第8行的语句等价于*head = (*head)->next，它改边了(*head)指向，使节点B成为新的表头。 为何很多内核代码中将链表结构体的next链接设为第一个成员变量呢？我想到两点，一是程序运行时变量行为的一致性，用一个二级指针curr来同时引用next和head，那么最好将两者置于内存中同一个位置，也就是基址，这样每次访问就不用区分是head还是next了。不然在for循环里，*curr会引用到不同偏移地址处。二是遍历链表时CPU会少做一次寻址操作，每次只要在节点对象的基址中找next链接，而不需要再访问一次偏移地址找链接。可见为了提高了程序性能，为了节省一个CPU指令级别操作，内核编程是多么需要绞尽脑汁（提示：内核开发过程中需要接触大量汇编源代码）！ ------------- 此处乃节点A地址，类型为struct node*<- 0x0000 |0x0020|-> 这里是next值，指向下一个节点，也是个struct node* ------------- | | ------------- | | ------------- | | ------------- *head = *curr =节点B <- 0x0010 | 0x0020 | ------------- | | ------------- | | ------------- | | ------------- 节点C <- 0x0020 | 0x0030 | ------------- | | ------------- | | ------------- | | ... 最后总结三点： 1.二级指针的使用原则是，如果要变更一个链表的链接方式，二级指针是首选。这样想，如果指针是为了变更一个对象内容的话，那么二级指针就是为了变更对象指针的内容。 2.数据结构设计很重要，特别是成员变量在内存映像中的排列顺序。 3.在设计/分析数据结构链接以及指针编程的时候，内存映像图解比一般的链表矢量图解更加有效和直观。
Talk is cheap, show me the code——空谈误国，实干兴邦！

让我们来人肉跑一下这个代码，对于——

• 删除节点是表头的情况，输入参数中传入head的二级指针，在for循环里将其初始化curr，然后entry就是*head(*curr)，我们马上删除它，那么第8行就等效于*head = (*head)->next，就是删除表头的实现。

• 删除节点不是表头的情况，对于上面的代码，我们可以看到——

1）（第12行）如果不删除当前结点 —— curr保存的是当前结点next指针的地址。

2）（第5行）entry 保存了 *curr——这意味着在下一次循环：entry就是prev->next指针所指向的内存。

3）（第8行）删除结点：*curr = entry->next; —— 于是：prev->next 指向了 entry -> next;

是不是很巧妙？我们可以只用一个二级指针来操作链表，对所有节点都一样。

如果你对上面的代码和描述理解上有困难的话，你可以看看下图的示意：

（全文完）

利用二级指针进行单链表节点操作的完整代码（重点是单链表的节点的删除）

#include<iostream>
#include<cstdlib>
using namespace std;

typedef struct node
{
	int data;
	struct node *next;
}Node;

void insert_node(Node **pphead,int v)
{
	if(*pphead==NULL)
	{
		*pphead=(Node *)malloc(sizeof(Node));
		(*pphead)->data=v;
		(*pphead)->next=NULL;
	}
	else
	{
		Node *t=*pphead;
		*pphead=(Node *)malloc(sizeof(Node));
		(*pphead)->data=v;
		(*pphead)->next=t;
	}
}
void delete_node(Node **pphead,int v)
{
	Node **cur=pphead;
	for(cur=pphead;*cur;)
	{
		Node *en=*cur;
		if(en->data==v)
		{
			*cur=en->next;
			free(en);
			break;
		}
		else
		{
			cur=&en->next;
		}
	}
}
void print_node(Node **pphead)
{
	for(Node **cur=pphead;*cur;cur=&(*cur)->next)
	{
		cout<<(*cur)->data<<" ";
	}
	cout<<endl;
}
int main(void)
{
	Node *pfrist=NULL;
	for(int i=1;i<=5;i++)
		insert_node(&pfrist,i);
	print_node(&pfrist);
	delete_node(&pfrist,1);
	print_node(&pfrist);
	delete_node(&pfrist,5);
	print_node(&pfrist);
	delete_node(&pfrist,3);
	print_node(&pfrist);
	delete_node(&pfrist,6);
	print_node(&pfrist);
	free(pfrist);
	pfrist=NULL;
	return 0;
}