双向链表的三种实现

这篇文章，其实很像是“茴字的四种写法”。这让人不由的想起来孔乙己。在我印象中，大多数人对孔乙己是持嘲讽态度的。

但是从技术上讲，我觉得”茴字的四种写法”在满足需求的前提下，有助于我们简化实现。

在我的历史经验中，我一共写过三种双向链表。

在最开始实现时，就是按算法导论最朴素的实现。

    //算法1
    struct node {
        struct node *prev;
        struct node *next;
    }
    struct node *head = NULL;
    void insert(struct node *n) {
        n->prev = NULL;
        n->next = head;
        if (head != NULL)
            head->prev = n;
        head = n;
    }
    void remove(struct node *n) {
        if (n->prev != NULL)
            n->prev->next = n->next;
        else
            head = n;
        if (n->next != NULL)
            n-next->prev = n->prev;
    }

写了几次之后，我觉得每次修正head指针，心智负担有点重而且极易出错，于是浪费了一点点空间改进了一下。

    //算法2
    struct node {
        struct node *prev;
        struct node *next;
    }
    struct node head = {NULL, NULL}
    void insert(struct node *n) {
        n->next = head.next;
        if (n->next != NULL)
            n->next->prev = n;
        head.next = n;
        n->prev = &head;
    }
    void remove(struct node *n) {
        n->prev->next = n->next;
        if (n->next != NULL)
            n->next->prev = n->prev;
    }

虽然insert函数逻辑几乎没有减少，但是remove函数的逻辑大大减少，并且更容易理解了。

但是这样做有一个弊端，struct node是一个结构体而不是一个指针，在某些情况下不便于存储。

因此这些年，我几乎都是两种算法换着用。但是每次使用算法1时，总是要停下来仔细思考一下，才敢下手。

最近在Review几年前的代码时，发现之前使用算法1写的双向链表有bug.

这再次使我想对双向链表的算法2进行改进，我仔细思考了一下双向链表的特性。

双向链表主要有两个功能：

提供反向遍历
以O(1)的时间复杂度删除某个节点

但是到目前为止，我从来没有使用过双向链表的特性1.

我使用双向链表的惟一原因就是要快速删除某一个节点。

即然如此，根据“这个世界是平衡的”原则，如果我去掉某个特性，就一定能简化部分实现，只是简化多少的问题。

我仔细研究了算法2，想从中找到某种启发。

最终我发现，在整个逻辑中，prev指针的惟一用处就是用来访问或修改前置节点的next变量。

而head的prev变量同样是多余的。

那么，如果将prev的含义修改为指向前置节点的next变量，关于prev的循环不变式同样成立。

优化后的代码如下：

    //算法3
    struct node {
        struct node **prev;
        struct node *next;
    }
    struct node *head = NULL;
    void insert(struct node *n) {
        n->prev = &head;
        n->next = head;
        if (head != NULL)
            head->prev = &n->next;
        head = n;
    }
    void remove(struct node *n) {
        *n->prev = n->next;
        if (n->next != NULL)
            n->next->prev = n->prev;
    }

由此，终于可以在享有算法2逻辑复杂度的同时，而不必要承担一个head结构体。

BTW，在写本文的前一天，我无意间发现Lua源码中也是这样做的 😀

推荐订阅源

重归混沌的BLOG