双向链表的三种实现

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

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

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

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

    //算法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进行改进,我仔细思考了一下双向链表的特性。

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

  1. 提供反向遍历
  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源码中也是这样做的 😀



发表评论