分类： LINUX
2012-05-08 19:19:30
Linux 链表设计者（因为 list.h 没有署名，所以很可能就是 Linus Torvalds）认为双头（next、prev）的双链表对于 HASH 表来说 "过于浪费"，因而另行设计了一套用于 HASH 表应用的 hlist 数据结构--单指针表头双循环链表，从上图可以看出， hlist 的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的 HASH 表中存储的表头就能减少一半的空间消耗。
因为表头和节点的数据结构不同，插入操作如果发生在表头和首节点之间，以往的方法就行不通了：表头的 first 指针必须修改指向新插入的节点，却不能使用类似 list_add() 这样统一的描述。为此，hlist 节点的pprev 不再是指向前一个节点的指针，而是指向前一个节点（可能是表头）中的 next（对于表头则是 first）指针（struct list_head **pprev），从而在表头插入的操作可以通过一致的 "*(node->;pprev)" 访问和修改前驱节点的 next（或 first）指针。
struct hlist_head{
struct hlist_node *first;
}
struct hlist_node{
struct hlist_node *next,**pprev;
}