链表是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的方式实现的。
使用环形双向链表的好处在于:
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;
}
使用线性双向链表的好处是:
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) …
在真正的项目中,添加和删除的效率有多重要呢?为了在这方面提供些数据,我修改了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这种微言大义似的写法也还是需要好好琢磨才能大体明白他的一些说法。下面是我的一些个人理解和疑惑:
联系客服