List是工程师的基本功，这里并不描述list增删这些细节的内容，仅仅根据我的理解写一下工程中List库的设计和实践考量。

看过几个不同的list库的实现，基本上涉及到如下的设计考量：

1.List数据结构上的差异

有没有头结点，是否循环，是否双向。这样就有多种组合，不罗嗦。

2.list的读写的保护。

3.List直接指针遍历还是仿照STL的Iterator方式遍历。

4.List同实际用户数据是采取一体式还是干湿分离式。

5.系统对于数据结构和算法的影响

1.从数据结构上将，Linux Kernel之中的List是双向无头节点链表。

空链表如下：

非空链表如下：

我觉得维护头结点的理由之一就是可以存放list size，而无需用户在应用部分进行维护。如果没有list size，用户需要在List删减的结束的时候维护list size，如果不愿意如此麻烦，只能悲催的在需要读取链表长度的时候for 循环并“++”一遍。实际上glist库提供get length之类的函数就是遍历list“++”

guint
g_list_length (GList *list)
{
  guint length;
  length = 0;
  while (list)
    {
      length++;
      list = list->next;
    }
  return length;
}

同样的Linux的kernel list需要的时候也只能如此这般。

2.List的读写保护

我这里提到的读写保护是在多线程之间的访问保护，如果需要在遍历和增删之间要有读写锁，list库不会内部维护锁，因为锁是OS相关的。

linux的list库提供了名为list_for_each_safe的宏也是用于读写访问，起保护范围仅仅在for循环内部，其实现如下：

#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

使用n缓存post->next，这样在遍历过程中如果删除pos，不会影响遍历。

3.List直接指针遍历还是仿照STL的Iterator方式遍历。

GList和Linux List都是直接指针进行遍历，我觉得使用迭代子的get next方法间接访问next node可以引入灵活性。

4.有关干湿分离或者一体化

linux的list head定义如下：

struct list_head {
    struct list_head *next, *prev;
};

在list库里面没有提供data指针，因此比较适合一体化的方式。

其实干湿分离的优点是可以将任何对象link进来而不用在用户对象内部必须填充list head，不影响用户数据结构，数据的独立性更好，GList就是干湿分离式。

struct _GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

5.系统对于数据结构和算法的影响

我在“有关Cache -(1) linux list之中的Prefetch”提到过：

“linux的list实现之中有如下东东：

#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

在遍历过程中使用了prefetch，其功能是数据的预先读取。当你确认后继续要读取某内存的信息的时候，可以采用prefetch将这一块数据读取到cache之中，以便后继快速访问。我的理解是条件不止这些，如果后继读取的内容仅仅被访问一次，那么是否prefetch也就没有意义了。后继访问的内存单元多次被读写才有意义。对于上述的list操作，在循环内部往往还会访问next指向的structure的内容，因此访问多次是可以期待的。”

6.其他

Linux List之中有很多类似“list_for_each”，“list_for_each_entry_safe_reverse”之类的宏。这类的宏在C语言编程中常见，最大的好处就是减少了重复代码书写可能带来的错误。

Linux 2.4 List之中list_for_each定义如下：

#define list_for_each(pos, head) \
    for (pos = (head)->next, prefetch(pos->next); pos != (head); \
            pos = pos->next, prefetch(pos->next))

建议继续学习：

1. 浅谈MySQL索引背后的数据结构及算法    (阅读：9962)
2. 浅析linux kernel network之socket创建    (阅读：5766)
3. 爱喝啤酒的程序员是如何学习数据结构的    (阅读：5185)
4. 分布式系统的数据结构    (阅读：5021)
5. stream.js ：一个新的JavaScript数据结构    (阅读：4101)
6. 浅析Linux Kernel 哈希路由表实现(一)    (阅读：3246)
7. 浅析Linux Kernel中的那些链表    (阅读：2891)
8. Linux kernel 性能压力下的优化实践(V0.1)    (阅读：2807)
9. 开源世界中的算法与数据结构 2 -- Linux Skbuff实现    (阅读：2780)
10. 数据结构之treap    (阅读：2747)