这篇文章，其实很像是“茴字的四种写法”。这让人不由的想起来孔乙己。在我印象中，大多数人对孔乙己是持嘲讽态度的。
但是从技术上讲，我觉得”茴字的四种写法”在满足需求的前提下，有助于我们简化实现。
在我的历史经验中，我一共写过三种双向链表。
在最开始实现时，就是按算法导论最朴素的实现。
//算法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源码中也是这样做的 😀