4. 线性表之双向链表与循环链表

说实话，单链表虽然好用，但有个问题一直让我头疼——你想找前一个节点，得从头开始遍历。我在做嵌入式项目时，有一次需要频繁地双向移动数据，单链表的效率实在让人抓狂。后来我换成了双向链表，问题迎刃而解。

今天我们就来聊聊双向链表和循环链表。这两个结构在实际开发中非常常见，尤其是循环链表，约瑟夫环问题就是它的经典应用。

4.1 双向链表的结构

双向链表，说白了就是每个节点多了一个指针——指向前一个节点。你看，单链表的节点只有一个 next 指针，指向后面。双向链表呢，多了一个 prev 指针，指向前面。

结构体定义是这样的：

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

嗯，这里要注意：头节点的 prev 指针通常指向 NULL，尾节点的 next 指针也指向 NULL。这样我们就能从两个方向遍历了。

我个人习惯用一张图来理解它的结构：

你看，每个节点都有一条向前的路和一条向后的路。这就是双向链表的核心思想。

4.2 双向链表的操作

双向链表的操作和单链表类似，但多了 prev 指针的处理。我重点讲插入和删除，因为这两个操作最容易出错。

4.2.1 插入操作

假设我们要在节点 p 后面插入一个新节点 s。步骤是这样的：

// 在节点 p 后面插入节点 s
s->next = p->next;      // 1. s 的后继指向 p 的后继
s->prev = p;            // 2. s 的前驱指向 p
if (p->next != NULL)    // 3. 如果 p 不是尾节点
    p->next->prev = s;  //    让 p 原来的后继的前驱指向 s
p->next = s;            // 4. p 的后继指向 s

我曾经在项目中犯过一个错误——忘了判断 p->next 是否为 NULL。结果在链表尾部插入时，程序直接崩溃了。你想想看，如果 p 是尾节点，p->next 是 NULL，你再去访问 p->next->prev，那不就是空指针解引用吗？

4.2.2 删除操作

删除节点 p 就简单一些：

// 删除节点 p
p->prev->next = p->next;  // 1. 前驱的后继指向 p 的后继
if (p->next != NULL)      // 2. 如果 p 不是尾节点
    p->next->prev = p->prev; // 让后继的前驱指向 p 的前驱
free(p);                  // 3. 释放 p

这里同样要注意边界条件。如果 p 是头节点，p->prev 是 NULL，那 p->prev->next 就会出错。所以实际代码中需要单独处理头节点的情况。

4.3 循环链表的概念

循环链表，就是把单链表的尾节点指向头节点，形成一个环。你想想看，这样有什么好处？

好处很明显——从任何一个节点出发，都能遍历整个链表。我在做嵌入式系统时，经常用循环链表来实现轮询调度。每个任务就是一个节点，CPU 轮流执行，永远不会走到尽头。

循环链表的结构定义和单链表一样：

typedef struct CNode {
    int data;
    struct CNode *next;
} CNode, *CLinkList;

区别在于：尾节点的 next 指针指向头节点，而不是 NULL。

判断循环链表是否遍历完，不能看 next 是否为 NULL，而要看 next 是否等于头节点。

4.4 约瑟夫环问题

约瑟夫环问题，是循环链表的经典应用。故事是这样的：

有 n 个人围成一圈，从第一个人开始报数，数到 m 的人出列，然后从下一个人重新报数，直到所有人都出列。问出列顺序是什么？

你看，这天然就是一个循环链表。每个人是一个节点，围成一圈就是循环链表。报数就是遍历节点，数到 m 就删除节点。

代码实现如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建循环链表，n 个人
Node* createList(int n) {
    Node *head = NULL, *prev = NULL;
    for (int i = 1; i <= n; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->data = i;
        if (head == NULL) {
            head = p;
        } else {
            prev->next = p;
        }
        prev = p;
    }
    prev->next = head;  // 尾节点指向头节点，形成环
    return head;
}

// 约瑟夫环求解
void josephus(int n, int m) {
    Node *head = createList(n);
    Node *p = head, *prev = NULL;

    // 找到最后一个节点（尾节点）
    while (p->next != head) {
        p = p->next;
    }
    prev = p;  // prev 指向尾节点
    p = head;  // p 指向头节点

    while (p->next != p) {  // 直到只剩一个节点
        // 报数 m-1 次
        for (int i = 1; i < m; i++) {
            prev = p;
            p = p->next;
        }
        // 删除 p 节点
        printf("%d 出列\n", p->data);
        prev->next = p->next;
        free(p);
        p = prev->next;  // 从下一个节点重新开始
    }
    printf("最后剩下: %d\n", p->data);
    free(p);
}

int main() {
    josephus(7, 3);  // 7个人，数到3出列
    return 0;
}

运行结果：

3 出列
6 出列
2 出列
7 出列
5 出列
1 出列
最后剩下: 4

我在面试中遇到过好几次约瑟夫环问题。说实话，第一次让我手写代码时，我还在循环边界上卡了一会儿。后来我总结了一个经验：画图！把节点画出来，指针指来指去，比干想代码清晰多了。

嗯，双向链表和循环链表就讲到这里。这两种结构在实际开发中非常实用，尤其是当你需要频繁双向遍历或者处理环形数据时。记住，代码写出来是一回事，能跑对是另一回事。多动手，多调试，慢慢就有感觉了。

---