链表

链表是一种离散的存储结构，它并不要求所保存的数据必须在一个连续的地址空间下。我们称链上的每个元素都是一个节点，该节点至少有两个部分构成， 一个是线性表所要保存的数据，称为key。另外一个是指向其后继节点的一个指针，称为next。如下图1所示，这样的链表称为单向链表， 我们可以定义如下的数据结构。各个节点依次串接下去，最后一个节点的next指向空，表示它没有后继。

struct singly_list_node { T key; struct singly_list_node *next; };
	图 1. 单向链表示意图

我们还可以在单向链表的基础上，为每个节点添加一个指向它的前驱的指针prev，如此形成的链表就是所谓的双向链表。如下图2所示，第一个节点因为没有前驱， 所以它的prev指向空，最后一个节点没有后继，其next指向空。

struct doubly_list_node { T key; struct singly_list_node *prev; struct singly_list_node *next; };
	图 2. 双向链表示意图

对于单向链表，我们可以通过简单的将最后一个节点的后继指针指向首节点，就得到了一个单向循环链表，如下图3所示。其实此时这个链表就像一条咬着尾巴的蛇，分不清头和尾了。 类似的，在双向链表的基础上，令第一个节点的前驱为最后一个节点，最后一个节点的后继为第一个节点，就得到了下图4所示的双向循环链表。

图 3. 单向循环链表示意图	图 4. 双向循环链表示意图

在本文中，我们介绍在Linux内核中为了统一数据结构而提供的链表实现，它和常规套路的实现思想有很大的不同。最后提供一个用C++模板实现的链表。

1. Linux内核中的链表

一般教科书中提到的链表实现都像我们在文初的介绍内容中那样， 定义一个链表节点struct singly_list_node或者struct doubly_list_node，在节点定义中描述key的各个字段， 并定义自身类型的指针prev和next来指引其前驱和后继。如果需要多个不同的链表，它们的Key有细微的差异，我们都需要重新定义和实现一个链表节点类型，扩展起来极不方便。 如果项目比较庞大，会看到大量的重复代码。Linux内核开发的早期，就深受这一问题的困扰。

为了简化和提高代码的复用率，Linux内核在2.1版之后就提供了一种统一的链表实现，本质上就是一种双向循环链表。传统教科书的实现，是把结构体变成一个链表， 而Linux的独特思路，则是将链表嵌入结构体中(embed a linked list node in the structure)。 如下面左侧代码所示，Linux内核定义了精简的数据结构:

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

        void init_list_head(struct list_head* list) {
            list->prev = list;
            list->next = list;
        }

1.1 增删改

针对这一结构体，Linux定义了一系列的接口函数，来添加、删除节点。下面的函数list_add和list_add_tail分别在节点的后面或者前面添加新的节点。它们调用了同一个函数__list_add，只是传递的参数不同。

        // 在节点后添加新节点
        void list_add(struct list_head* new, struct list_head* head) {
            __list_add(new, head, head->next);
        }
        // 在节点前添加新节点
        void list_add_tail(struct list_head* new, struct list_head* head) {
            __list_add(new, head->prev, head);
        }

__list_add的参数列表中，new是新节点的对象，prev和next则分别是new指针的前驱和后继。在head节点之后插入新节点，就是将new放在head和head->next之间，所以传参时将head赋予prev，head->next赋予next。 list_add_tail也是相同的道理。

        void __list_add(struct list_head* new, struct list_head* prev, struct list_head* next) {
            next->prev = new;
            new->next = next;
            new->prev = prev;
            prev->next = new;
        }

在后面的章节中，我们会看到这两个函数再配合上删除操作的函数就可以实现后进先出特性的栈， 或者先进先出的队列。出栈和出队都需要用到删除操作，把栈顶或者队首的数据从链表中移除。 下面的两个函数用于删除一个节点。显然对链表的插入和删除操作只需要在\(O(1)\)的时间中完成，这得益于它离散的存储方式。

        void list_del(struct list_head *entry) {
            __list_del(entry->prev, entry->next);
            entry->next = NULL;
            entry->prev = NULL;
        }
        void __list_del(struct list_head * prev, struct list_head * next) {
            next->prev = prev;
            prev->next = next;
        }

我们也可以方便的用一个新的节点来替换旧节点，只需要向下面的函数这样处理好新旧数据的指针就好了，其复杂度也是\(O(1)\)的。

        void list_replace(struct list_head *old, struct list_head *new) {
            new->next = old->next;
            new->next->prev = new;
            new->prev = old->prev;
            new->prev->next = new;
        }

list_replace中没有调整旧节点的前驱和后继指针，这样通过它我们仍然能够访问原来链表中的数据。有时为了安全，我们需要下面的这个函数，对替换下来的旧节点再次进行初始化，让其前驱和后继指针指向自己。

        void list_replace_init(struct list_head *old, struct list_head *new) {
            list_replace(old, new);
            init_list_head(old);
        }

1.2 访问元素

那么现在的问题就是，我们该如何把链表中实际需要保存的数据key与链表节点关联起来。 比如说我们在XiaoTuOS中定义的任务管理器，就是使用的这种链表来管理不同优先级和挂起任务的。我们在任务描述符中塞入了一个list_head结构体， 定义如下:

        typedef struct xtos_task_descriptor {
            uint32 *pTopOfStack;        /* 栈顶地址,该位段不可以更改 */
            uint32 *pBottomOfStack;     /* 栈底地址 */
            uint16 pid;                 /* 进程ID */
            // 省略……
            struct list_head list;      /* 链表节点 */
        } xtos_task_desp_t;

其它字段中的内容这里不展开讲了。在XiaoTuOS中，我们把所有相同优先级的任务串接在同一个链表中。比如说对于优先级为0的任务链表，我们定义一个哨兵节点 struct list_head L0_tasks;哨兵节点是用来处理链表的边界问题的，如果我们把文前介绍中的双向链表的表首和表尾所指的null，替换为哨兵节点就是一个双向循环链表。 哨兵的后继指向双向链表的表首，前驱则指向表尾。所以，我们说Linux提供的通用链表结构是一种双向循环链表。

哨兵节点可以为我们指引不同优先级的任务链表，但是通过它我们只能得到任务描述符中的链表节点。它不能为任务调度提供任何有用的数据。我们还需要想办法获得包含该链表节点的任务描述符。 为此，Linux专门定义了一个宏list_entry用于获取包含链表节点的数据结构地址。

        #define list_entry(ptr, type, member) container_of(ptr, type, member)

它有三个输入参数，其中ptr为链表节点的指针；type是目标数据结构的类型，对于我们的任务描述符就是xtos_task_desp_t，member则是链表节点在结构体定义中的成员名称，这里就是list。

在该宏中调用了一个container_of的宏，这个宏就是根据C语言的ABI设计的，下面是简化之后的实现方式。其基本思想就是，C语言中的结构体各个字段相对于对象的起始地址的偏移量都是一样的。 所以只需要将成员对象地址ptr减去它在结构体中的偏移量，就可以得到目标结构体的地址了。在这个宏中，我们先后进行了两次类型转换。首先将ptr转换成为一个uint8类型的指针，当然uint8也不是标准C中定义的原生类型， 这里只是要强调，该减法运算一定是以字节为单位进行的，才能得到正确的目标结构体地址，然后将该地址转换为目标类型的指针(type *)。

        #define container_of(ptr, type, member) ((type *)((uint8 *)(ptr) - offsetof(type, member)))

同样的，我们也通过一个宏offset来求取成员变量在结构体中的偏移量。在该宏中，我们假定在地址0处有一个目标结构体，那么该结构体的成员地址就是所需的偏移量。所以这里对成员变量取址之后， 将指针类型强制转换称为一个整型数据。

        #define offsetof(type, member) ((unsigned long) &((type *)0)->member)

1.3 遍历方法

由于链表中的数据存储方式是离散的，所以我们不能向数组那样通过角标的方式索引元素。如果我们需要访问链表中的第\(i\)个元素，那么我们需要从表首开始依次通过后继指针遍历i个链表节点才行。 这样的效率很低，最坏的情况下索引复杂度是\(O(n)\)，在使用链表时应当尽量避免使用这种索引的操作。

实际上，大多时候我们使用链表就是一个容器，我们不太关注链表中数据的先后顺序，却往往需要对链表中的所有对象进行相同的操作。此时我们可以从表首开始，依次处理直到表尾。 Linux也为这一需求提供了一些宏定义用于遍历链表。

list_for_each本质上就是一个for循环语句，它有两个参数，其中pos是我们在遍历链表过程中的光标，它是当前的链表节点。head则是链表的哨兵节点指针，它标志着遍历的起点和终点。

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

假设我们要遍历任务链表L0_tasks中的各个任务，可以像下面的代码一样，先定义一个list_head的指针。然后通过该指针和L0_tasks遍历链表。在循环体中，先通过刚刚提到的list_entry来获取任务描述符， 再进行必要的操作。

        struct list_head *pos;
        list_for_each(pos, &L0_tasks) {
            xtos_task_desp_t *task = list_entry(pos, xtos_task_desp_t, list);
            // todo
        }

Linux还额外提供了一个使用起来比较方便的遍历方式，可以直接对目标结构体进行遍历。虽然宏定义写的很长，但它也就是在for语句中使用list_entry获取了目标结构体的指针。 其参数pos则是要遍历的目标结构体指针，head还是哨兵节点的指针，而member是链表节点在结构体中的成员名称。

        #define list_for_each_entry(pos, head, member)                  \
            for (pos = list_entry((head)->next, typeof(*pos), member);  \
                 &pos->member != (head);                                \
                 pos = list_entry(pos->member.next, typeof(*pos), member))

类似的，Linux还提供了反向遍历的宏，这里不再赘述。

2. C++模板实现的DataListNode

我们还是按照传统教科书的方式用C++模板的形式实现一个链表。首先定义一个模板类DataListNode，作为链表中的节点定义，它有两个指针prev和next分别指向前驱和后继。 另外还定义了一个T类型的公开成员key用于保存数据。

        template <class T>
        class DataListNode {
            public:
                DataListNode() : prev(this), next(this) { }
                DataListNode(T const & data) : prev(this), next(this), key(data) { }
            public:
                T key;
            private:
                DataListNode * prev;
                DataListNode * next;
        };

我们定义了两个构造函数，在构造函数中我们为prev和next两个链表节点指针赋予了初值this，让它们指向节点本身。这里我们将成员变量key定义成公开的，主要是考虑到链表就是用来装载数据的， 获得了链表节点就应该意味着获得了实际的数据。

由于链表节点通过prev和next来维护数据的前后关系，对链表节点进行拷贝是没有意义的。因为即使我们有两个完全一样的链表节点，即他们保存的数据key、前后链接指针prev和next都相等， 它们的地址也是不一样的，通过前驱的next指针，或者后继的prev指针，只能访问到其中一个节点上。因此链表上的每个节点都应该是唯一的，我们要避免拷贝操作，所以下面将拷贝构造函数和拷贝赋值运算符定义为私有的， 并不做任何运算，这样就无法调用这两个函数了，编译器也不会为我们添加拷贝构造函数和拷贝赋值运算符。

        private:
            DataListNode(DataListNode const &node) {}
            DataListNode & operator = (DataListNode const &node) {}

2.1 增删改

下面的两个函数分别是在链表节点对象之前或者之后插入一个节点，我们没有像Linux那样，用一个辅助的函数来实现。

        void add(DataListNode * n) {
            this->next->prev = n;
            n->next = this->next;
            n->prev = this;
            this->next = n;
        }

        void add_prev(DataListNode * p) {
            this->prev->next = p;
            p->prev = this->prev;
            p->next = this;
            this->prev = p;
        }

下面左边的函数remove用于节点将自己从链表中移除。释放节点对象内存时，需要先通过该函数把自己移除，维护链表的前后关系，之后才可以释放对象的内存。

        void remove() {
            next->prev = prev;
            prev->next = next;
            next = this;
            prev = this;
        }

参照Linux中替换函数的实现，我们定义了两个友元函数replace和swap分别用于替换节点和交换两个节点的位置。需要注意的是，在replace函数中我们没有调整被替换的节点o的前驱和后继指针。

        friend void replace(DataListNode * o, DataListNode * n) {
            n->next = o->next;
            n->next->prev = n;
            n->prev = o->prev;
            n->prev->next = n;
        }

        friend void swap(DataListNode * u, DataListNode * v) {
            DataListNode tmp;
            replace(u, &tmp);
            replace(v, u);
            replace(&tmp, v);
        }

3. DataListNode的封装

到目前为止，我们对链表的操作都是直接操作的链表中的各个节点，而且还需要自己管理链表节点的内存。很多时候，我只是希望有一个链表来存储数据而已，并不想花费太多的精力来维护链表的前后关系。 所以，有必要用DataList来对链表节点进一步进行封装。为了能够访问DataListNode的私有成员，我们还需要在DataListNode的类定义中把DataList声明为友元。

下面是DataList最初的定义，它用一个私有的链表节点mHead来作为循环双向链表的哨兵，这样可以方便的处理边界问题。同时用一个变量mSize来记录链表中的节点数量， 并在默认构造函数中将之赋值为0。此外，我们还定义了一个函数empty用于判定链表是否为空。

        template <class T>
        class DataList {
            public:
                DataList() : mSize(0) {}
            public:
                bool empty() const { return mHead.prev == &mHead; }
            private:
                DataListNode<T> mHead;
                int mSize;
        };

3.1 链表的初始化

有时我们已经有了一组初始的值，希望把他们装到一个链表中。为此，定义了如下的构造函数，该函数有两个参数。其中buf是保存有初值的缓存，len则是缓存大小。 在构造函数中我们先检查一下缓存大小，如果不大于0就没必要继续了。在接下来的循环中，用缓存中的数据构建链表节点对象，并将他们依次添加到哨兵节点之前， 也就是链表表尾。

        DataList(T const *buf, int len) {
            if (len <= 0)
                return;

            for (int i = 0; i < len; i++) {
                mHead.add_prev(new DataListNode<T>(buf[i]));
                mSize++;
            }
        }

因为我们希望该链表封装能够自动的维护其节点的内存，所以我们还需要定义一个析构函数，用于在释放链表的时候能够自动的回收它的链表节点的内存。 在析构函数中我们只是简单的调用了成员函数clear()。在clear函数中我们用两个指针分别记录下当前的节点以及它的后继。在循环过程中，依次删除当前节点。 一直到遍历过程回到了我们的哨兵节点上。

        ~DataList() {
            clear();
        }
        void clear() {
            DataListNode<T> *end = &mHead;
            DataListNode<T> *cur = mHead.next;
            DataListNode<T> *next = cur->next;

            while (cur != end) {
                delete cur;
                cur = next;
                next = cur->next;
            }
            mHead.init();
        }

在clear函数中我们实际上是直接释放了节点的内存，并没有维护链表的前后关系，这与在DataListNode中的介绍有些不一致。clear函数的职责就是清空链表， 对它而言链表中的数据关系已经不再重要了，所以这样做无所谓。但是清空了链表中的数据之后，我们应当调用节点的init函数，维护哨兵节点，让其形成一个双向循环链表。

3.2 元素的访问

其实，按照C++标准库的套路，为了访问链表中的数据，我们应该定义一个迭代器。我在这里偷些懒，只是在这个封装类中添加了两个函数begin和end。 end实际上是哨兵节点的地址，一般用作链表的遍历结束的标识。begin返回的则是哨兵节点的后继，它是遍历链表的起点。

        DataListNode<T> * begin() { return mHead.next; }
        DataListNode<T> * end() { return &mHead; }

此外，我们还需要为DataListNode类添加两个成员函数next_ptr和prev_ptr，它们分别返回了链表节点对象的前驱和后继指针。

        DataListNode * next_ptr() { return next; }
        DataListNode * prev_ptr() { return prev; }

这样，我们就可以按照类似如下的形式来遍历链表了。

        for (DataListNode<double> *ptr = list.begin(); ptr != list.end(); ptr = ptr->next_ptr()) {
            // Todo
        }

3.3 搜索、插入、删除

下面的函数依次遍历了整个链表，查找给定的数值e。和数组中一样使用的是线性查找方法， 其复杂度为\(O(n)\)。

        DataListNode<T> * find(T const & e) {
            DataListNode<T> *end = &mHead;
            for (DataListNode<T> *ptr = mHead.next; ptr != end; ptr = ptr->next) {
                if (e == ptr->data())
                    return ptr;
            }
            return 0;
        }

下面左边是插入函数，右边是删除函数，它们都是在调用链表节点的插入和删除函数，只是增加了对链表信息的维护，以及内存的申请和释放。

        DataListNode * insert(DataListNode * node, T const & v) {
            DataListNode *re = new DataListNode(v);
            node->add(re);
            mSize++;
            return re;
        }

        void remove(DataListNode *node) {
            node->remove();
            delete node;
            mSize--;
        }

4. 完

在本文中，我们介绍了单向链表、双向链表、单向循环链表以及双向循环链表的基本形式。重点关注了双向循环链表的实现。首先介绍了Linux中提供的独特的链表实现方式， 他定义了一个极简的链表节点的数据结构list_head，并为之实现了一系列的API来完成插入、删除、替换等基本功能，还通过宏定义描述了遍历链表的for循环框架， 使用起来非常方便。

我们还按照传统教科书的方式，定义了一个链表节点的C++模板类。同时，还通过类DataLlist对其进行了进一步的封装，使其可以自动的管理内存。 在后续的章节中， 我们把它扩展为栈和队列。