双向链表的三种实现

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

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

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

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

1. //算法1
2. struct node {
3. struct node *prev;
4. struct node *next;
5. }
6. struct node *head = NULL;
7. void insert(struct node *n) {
8. n->prev = NULL;
9. n->next = head;
10. if (head != NULL)
11. head->prev = n;
12. head = n;
13. }
14. void remove(struct node *n) {
15. if (n->prev != NULL)
16. n->prev->next = n->next;
17. else
18. head = n;
19. if (n->next != NULL)
20. n-next->prev = n->prev;
21. }

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

1. //算法2
2. struct node {
3. struct node *prev;
4. struct node *next;
5. }
6. struct node head = {NULL, NULL}
7. void insert(struct node *n) {
8. n->next = head.next;
9. if (n->next != NULL)
10. n->next->prev = n;
11. head.next = n;
12. n->prev = &head;
13. }
14. void remove(struct node *n) {
15. n->prev->next = n->next;
16. if (n->next != NULL)
17. n->next->prev = n->prev;
18. }

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

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

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

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

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

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

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

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

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

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

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

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

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

优化后的代码如下：

1. //算法3
2. struct node {
3. struct node **prev;
4. struct node *next;
5. }
6. struct node *head = NULL;
7. void insert(struct node *n) {
8. n->prev = &head;
9. n->next = head;
10. if (head != NULL)
11. head->prev = &n->next;
12. head = n;
13. }
14. void remove(struct node *n) {
15. *n->prev = n->next;
16. if (n->next != NULL)
17. n->next->prev = n->prev;
18. }

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

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