Rusty Russell关于双向链表C语言实现的精彩总结 ? 开源小厨

Rusty Russell关于双向链表C语言实现的精彩总结

油蚂蚱 发表于 2010-12-19 00:33 添加评论

十二 192010

链表是C语言里面最常用的数据结构，同时也是各大IT公司研发职位笔试面试必考内容之一，年关将至，各位心怀骚动，打算跳槽的同学不妨提前准备一下，以备不患。正好Linux kernel的大拿Rusty Russell最近在他的blog上，对C语言的双向链表实现做了一个精彩的总结。让我们一块来学习一下吧，下面是该文的全文翻译。

在C里面有两种类型的双向链表，我把它们分别叫做环类型(ring style)与线性类型(linear style)。

Linux kernel使用的是环类型，该链表的声明(kernel版本2.6.36)在include/linux/types.h中，实现在include/linux/list.h中，要想使用链表，声明一下struct list_head，然后将struct list_head嵌在你的结构里面。这样整个链表将会构成一个环形，正反两个方向你都可以遍历。

Samba则使用的是线性类型，该链表的实现(master branch)在lib/util/dlinklist.h里，你可以直接将你的结构指针(struct foo *)定义为你的链表指针，当然你需要在你的结构定义里面添加成员struct foo *prev, *next。这样就组成了一个正向以NULL结尾的链表(为了便于链表尾节点的访问，反方向在最近成为了环形)。Linux的hlist.h数据结构类似于此，只不过以list.h的方式实现的。

使用环形双向链表的好处在于：

1. 添加和删除节点不需要if-else判断，因为它们是同种类的(homogeneous)。[译注1]

head->next->prev = new;
new->next = head->next;
new->prev = head;
head->next = new;

vs

if (!head) {
new->prev = head = new;
new->next = NULL;
} else {
new->prev = head->prev;
head->prev = new;
new->next = head;
head = new;
}

2. list_add, list_del是inline函数，不是宏，因为他们的类型是已知的。

使用线性双向链表的好处是：

1. 类型安全，因为头指针和内部指针都是正确的类型。[译注2]
2. 正向遍历很简单，因为链表终止于NULL，而不是又指回了表头。理论上来说，这还可以节省一个寄存器[译注3]，不过更主要的区别是使用NULL作为循环结束的判断条件更实用。
3. 作为一个必然的结果，遍历，初始化与非空判断都不再需要使用极其容易出错的宏。

struct foo *head = NULL;
if (head == NULL) …
for (i = head; i; i = i->next) …

vs

LIST_HEAD(head);
if (list_empty(&head)) …
list_for_each(i, head, list) …

4. 表头指针占用空间少那么一丁点(一个指针 vs 两个)。[译注4]

在真正的项目中，添加和删除的效率有多重要呢？为了在这方面提供些数据，我修改了linux kernel以使每个list.h操作都增加一个计数，并在随后定期打印这些计数。然后在我的笔记本上正常运行了3天，下表是其中的统计数据。

操作	频率
非空测试	45%
删除	25%
添加	23%
遍历开始	3.5%
遍历下一个	2.5%
替换	0.76%
其它操作	0.0072

首先，我对添加和删除比查找更频繁有一点吃惊，不过仔细思考，这也合情合理，如果查找更平常的话，那么我们就不会使用链表了。还要注意的是非空检测是如此的频繁：看起来就像是’链表是一条慢路径’模式一样[译注5]，我怀疑Samba(或其它项目)的使用情况是否也如此。

其次，删除要比添加多一点，也许我们删除了一些已经初始化但还未添加的元素[译注6]，不过我没有就此追踪下去。

再者，遍历的过程是短暂的，链表要么是空的，要么在第一个节点就找到了(28%的几率，但我没有区分)。我在想针对其中的某些使用，采用单向链表将会是一个有趣的空间优化。

总结：我喜欢Samba线性双向链表的安全，但环形链表添加和删除操作不需要if-else的优点也是实实在在的。这是一个关于性能与易用性的取舍，也许他们都应该在CCAN中有一席之地[译注7]。

译注：理解Rusty的文章首先要读懂这两种类型链表的实现代码，从学习曲线上来说，Samba的例子更符合我们在课堂上所学的链表，理解起来也容易得多，kernel的链表如果之前没接触过的话，则要困难一点(这里有一篇文章详细解释了linux kernel的链表，下图是从网上找的一个示意图)。

即使两者都读懂了，Rusty这种微言大义似的写法也还是需要好好琢磨才能大体明白他的一些说法。下面是我的一些个人理解和疑惑:

1. 这里Rusty用了homogeneous这个词，我的理解是由于kernel链表使用前必须要初始化，而表头在初始化后是固定存在的，也就不存在表头是NULL的问题，即表头和待插入节点都是存在的结构。
2. 这里所指的类型安全，我的理解是因为Samba链表的节点和表头必须是相同的结构类型，否则无法编译通过，而kernel链表从理论上来说，节点表头都可以是不同的类型。
3. 这里所说的节省一个寄存器，我的理解是遍历的终止条件不同(即判断一个指针非空与判断两个指针不等)，前者对应的汇编指令所需要的寄存器比后者要少一个。
4. 这里指表头占用的空间，kernel链表至少需要一个struct list_head，即8个字节，而samba链表只需一个占位指针struct foo *，4个字节。
5. Rusty在这里使用了’list as a slow path’ pattern来解释为什么非空检测这么频繁，我的理解是可能链表操作在kernel中被认为是一个昂贵或费时的操作，并且相对来说不太经常被使用，故而slow path。
6. Rusty在这里使用了deleting initialized-but-unadded elements，个人理解在kernel链表里，如果一个元素没有加入链表，也是可以被删除(list_del)的，即如果它的prev和next被初始化指向自己的话，至于具体的应用场景就不清楚了。
7. CCAN是Rusty发起的，类似于Perl的CPAN项目的C语言版，里面包含了许多聪明而又短小精悍的代码，如各种常用的数据结构实现等等，CCAN包含的双向链表实现是由linux kernel的链表改造而来的，现在还没有包含一个类似Samba的链表实现。