第十九章：指针与双向链表——指针操作、插入与删除的指针修改

双向链表，说白了就是给每个节点多装了一根“回头箭”。

单向链表只能从头往后走，想找前一个节点？没门。双向链表就不一样了——每个节点里除了存数据的 data，还有两个指针：一个指向前驱（prev），一个指向后继（next）。这样你就能前后自由穿梭了。

我个人习惯把双向链表比作一条双向车道。单向链表是单行道，想掉头？你得从头再来。双向链表呢，随时可以调头，灵活得很。

19.1 双向链表的结构定义

先看结构体长什么样：

typedef struct DNode {
    int data;               // 数据域
    struct DNode *prev;     // 指向前驱节点
    struct DNode *next;     // 指向后继节点
} DNode, *DLinkList;

嗯，这里要注意：prev 和 next 都是指针，类型是 struct DNode *。你不能写成 DNode *，因为这时候 DNode 还没定义完呢。

19.2 双向链表的插入操作

插入操作比单向链表麻烦一点，因为你要维护两个方向的指针。但好处是——如果你知道要插在哪个节点后面，你不需要遍历找前驱。

来看一个经典场景：在节点 p 后面插入新节点 s。

// 在 p 节点之后插入 s 节点
s->prev = p;
s->next = p->next;
if (p->next != NULL) {
    p->next->prev = s;
}
p->next = s;

这里有个坑，我当年第一次写的时候踩过。你想想看，如果 p 是尾节点，p->next 是 NULL。这时候你直接写 p->next->prev = s，程序就崩了。所以一定要加个判断。

19.3 双向链表的删除操作

删除操作比插入更简单，因为你知道要删哪个节点，直接把它从链表中“摘”下来就行。

删除节点 p：

// 删除节点 p
if (p->prev != NULL) {
    p->prev->next = p->next;
}
if (p->next != NULL) {
    p->next->prev = p->prev;
}
free(p);

你看，代码很对称。前驱的后继指向 p 的后继，后继的前驱指向 p 的前驱。这样 p 就被孤立了，然后 free 掉。

但要注意：如果 p 是头节点，p->prev 是 NULL，这时候你不能写 p->prev->next。同理，如果 p 是尾节点，p->next 是 NULL。

19.4 双向链表的遍历

双向链表遍历有两种方式：正向和反向。

正向遍历：

DNode *p = head->next;
while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
}

反向遍历：

DNode *p = tail;  // 假设 tail 指向尾节点
while (p != NULL) {
    printf("%d ", p->data);
    p = p->prev;
}

我个人觉得，双向链表最爽的地方就在这里。你想怎么走就怎么走，不用像单向链表那样只能一条道走到黑。

19.5 双向链表 vs 单向链表

特性	单向链表	双向链表
指针数量	1 个（next）	2 个（prev, next）
内存占用	较小	较大（多一个指针）
插入/删除	需遍历找前驱	直接操作，效率更高
反向遍历	不支持	支持
代码复杂度	低	中等（需维护两个指针）

你看，双向链表虽然多占了一个指针的内存，但换来了更灵活的操作。在嵌入式系统里，如果内存够用，我一般优先用双向链表——调试起来也方便，能前后看。

19.6 双向链表的核心逻辑图

下面这张图展示了双向链表的基本结构，以及插入和删除时指针的变化：

19.7 总结

双向链表的核心就是两个指针：prev 和 next。插入和删除时，记住一句话：先连后断。先把新节点的两个指针连好，再修改前后节点的指针。这样就不会丢失节点。

我在实际项目中，双向链表用得比单向链表多。尤其是在需要频繁插入删除、或者需要双向遍历的场景下，双向链表真的省心不少。当然，代价就是多占一点内存——但现在的嵌入式设备，这点内存真不算什么。

嗯，这一章就到这。记住：画图、画图、画图。指针操作，画图比写代码更重要。