一、双链表：让链表学会“倒车”

单链表有个很烦人的问题——你只能从头往后走。想找前一个节点？没门。我当年刚学链表时，写了个约瑟夫环问题，用单链表实现，结果每次删除节点都得从头遍历找前驱，效率低得让人抓狂。后来我才知道，双链表就是来解决这个问题的。

1.1 双链表的定义

说白了，双链表就是在每个节点里多存一个指针，指向前一个节点。这样你就能双向跑了。

typedef struct DNode {
    int data;               // 数据域
    struct DNode *prior;    // 前驱指针
    struct DNode *next;     // 后继指针
} DNode, *DLinkList;

你看，比单链表就多了一个 prior 指针。但就是这个指针，让很多操作变得简单了。

1.2 双链表的插入操作

双链表插入节点，比单链表多了一步——要处理前驱指针。我习惯先画个图再写代码，不然很容易漏掉某个指针的赋值。

// 在 p 节点之后插入 s 节点
bool InsertNextNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    
    s->next = p->next;      // 1. s 的后继指向 p 的后继
    if (p->next != NULL)    // 2. 如果 p 有后继
        p->next->prior = s; //    让 p 的后继的前驱指向 s
    s->prior = p;           // 3. s 的前驱指向 p
    p->next = s;            // 4. p 的后继指向 s
    return true;
}

1.3 双链表的删除操作

删除操作比插入简单一点，但同样要注意边界情况。

// 删除 p 节点的后继节点
bool DeleteNextNode(DNode *p) {
    if (p == NULL || p->next == NULL) return false;
    
    DNode *q = p->next;          // q 是要删除的节点
    p->next = q->next;           // 1. p 跳过 q 指向 q 的后继
    if (q->next != NULL)         // 2. 如果 q 不是尾节点
        q->next->prior = p;     //    让 q 的后继的前驱指向 p
    free(q);                     // 3. 释放 q 的内存
    return true;
}

嗯，这里同样要判断 q->next != NULL。你想想看，如果 q 是最后一个节点，那 q->next 就是 NULL，访问 prior 就出事了。

二、循环链表：让链表首尾相连

2.1 循环单链表

循环单链表就是把尾节点的 next 指向头节点。这样做的好处是——从任意节点出发都能遍历整个链表。

// 初始化循环单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL) return false;
    L->next = L;    // 头节点的 next 指向自己
    return true;
}

判断循环单链表是否为空，就看 L->next == L。判断 p 是否为尾节点，就看 p->next == L。

2.2 循环双链表

把双链表和循环结合起来，就是循环双链表。头节点的 prior 指向尾节点，尾节点的 next 指向头节点。

// 初始化循环双链表
bool InitDList(DLinkList &L) {
    L = (DNode *)malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = L;   // 头节点的 prior 指向自己
    L->next = L;    // 头节点的 next 指向自己
    return true;
}

循环双链表的判断条件很统一：p->next == L 表示 p 是尾节点，p->prior == L 表示 p 是头节点后的第一个节点。

三、静态链表：用数组模拟链表

静态链表这个概念，说实话，我工作这么多年用的不多。但在一些不支持动态内存分配的场景下（比如嵌入式系统），它还是很有用的。

静态链表用数组来存储节点，每个节点包含数据域和游标（cur）。游标代替了指针，指向下一个节点的数组下标。

#define MaxSize 100

typedef struct {
    int data;   // 数据域
    int cur;    // 游标，指向下一个节点的下标
} SLinkList[MaxSize];

静态链表的插入和删除操作，本质上和动态链表一样，只是把指针换成了数组下标。我当年在单片机项目里用过一次，因为那个芯片的内存只有 2KB，malloc 根本不敢用。

四、知识体系总览

下面这张图总结了本章的核心内容，我建议你把它记在脑子里。

五、总结与避坑

这一章的内容，说白了就是三种链表变种。双链表让你能倒着走，循环链表让你能绕圈走，静态链表让你在没 malloc 的地方也能用链表。

我最后给你几个实战建议：

• 写双链表代码时，先画图。我每次写指针操作前都会在纸上画一下，画清楚了再写代码，能省一半调试时间。
• 循环链表的判空和判尾条件要记牢。面试时经常考这个，我面过的人里十个有八个会搞混。
• 静态链表在实际项目中用得少，但考研和面试常考。理解它的思想就好，不用死记硬背代码。

好了，这一章就到这里。链表这东西，多写几遍就熟了。你动手试试，把代码敲一遍，比看十遍都管用。

---