单个指针就能看到前、当前、后三个节点#

1
temp 指向某节点（值为 600）
2
temp->next 是 800
3
temp->prev 是 400

对比单链表：仅凭一个指针无法查看前一个节点，必须额外用另一个指针来跟踪前一个。

删除容易得多#

删除一个节点，单链表需要两个指针（待删节点 + 前驱），双向链表只要一个（指向待删的那个节点）。

能在链表中进行反向查找，就能沿两个方向遍历链表。

prev 指针要额外内存#

典型架构（int 4 字节、指针 4 字节）：

1
单链表    4 数据 + 4 链接 = 8 字节
2
双向链表  4 数据 + 8 链接 = 12 字节

对于整数列表，用于链接的空间将是数据所用空间的两倍。

插入或删除时要重置更多链接#

比起单向链表，需要重置更多几个链接，因此更容易出错。

局部变量和全局变量#

1
定义位置  局部变量在函数内，全局变量在函数外
2
生存期    局部变量只管函数调用的期间，全局变量管应用程序的整个生命周期
3
函数结束  局部变量从内存中清除，全局变量仍然存在
4
可访问性  局部变量除非通过指针访问否则并非到处可访问；全局变量所有函数的任何地方都能访问

前面的实现中，大多时候都把 head 声明为全局变量。

要写的函数#

• insert_at_head(x)：在链表起始位置插入，参数是一个整数
• insert_at_tail：在链表尾端插入（最终没写）
• 正向打印：从链表头至尾遍历打印
• 反向打印：从链表尾到头遍历，按逆序打印

反向打印还有个额外作用：反向打印函数能验证每个节点的反向链接（prev）是否正确创建。它是 prev 指针的验证手段，不只是个演示。

错误做法#

如果像声明普通变量那样写：

1
struct node newnode;        /* ← 错！这是栈上的局部变量 */

它是作为局部变量创建的，函数调用结束时就会从内存中被清除。

局部变量存于应用程序内存的栈区，生存期不受我们控制。要求是：除非明确地移除一个节点，否则它应当一直在内存中。

正确做法#

必须在动态内存（堆区）创建节点：C 用 malloc，C++ 用 new。

堆里的任何东西，除非我们显式释放，否则不会被清除。

一个真实的 bug#

1
/* 错误版本 */
2
struct node *get_new_node(int x) {
3
    struct node newnode;        /* 栈上 */
4
    newnode.data = x;
5
    return &newnode;            /* 返回栈上变量的地址 */
6
}

会发生什么：

1
假设返回地址 50
2
→ 一旦该函数结束，用于 get_new_node 的栈帧就会被回收
3
  所以现在即便你有地址 50，但那里已经没有节点了

而且类型也不同：newnode 是结构体节点类型；接收方要的是指向结构体节点的指针类型。

正确的 get_new_node#

1
struct node *get_new_node(int x) {
2
    struct node *new_node = malloc(sizeof(struct node));   /* 堆上创建 */
3
    new_node->data = x;
4
    new_node->next = NULL;
5
    new_node->prev = NULL;
6
    return new_node;
7
}

我们没法直接命名堆中的一段内存，访问堆中某物的唯一方式是通过指针；倘若丢失了这个指针，就会失去这个节点。

为什么单独写一个函数：为了避免重复代码——既要在 insert_at_head 中创建节点，过段时间也要在 insert_at_tail 中创建节点。

变量命名建议：用 new_node / new_node_pointer 之类，temp 并不是一个非常有意义的名字。

链表为空#

1
head = new_node;
2
return;

示例：插入数字 2，get_new_node 在地址 400 创建新节点；head = new_node 把地址 400 存入 head。

函数执行完毕后变量 new_node 从内存中被清除，但节点本身不会被清除。

链表不为空#

示例再插入数字 4，节点在地址 600：

1
head->prev    = new_node;   /* ① 把现有头节点的 prev 域设为新节点地址 */
2
new_node->next = head;      /* ② 把新节点的 next 域设为当前头节点地址 */
3
head          = new_node;   /* ③ 头指针指向新节点 */

顺序的解释：首先把现有头节点的前一域设置为这个新节点的地址，也就是建立这条链接；然后把新节点的下一域设为当前头节点的地址；现在可以断开这条链路并构建这条链路，因此把头节点设置为新节点的地址。

和单链表的区别：多了一行 head->prev = new_node。