双链表与循环链表：从结构到实战

说实话，单链表用久了，你总会遇到一些让人抓狂的场景。比如你想删除某个节点，却发现自己还得从头遍历去找它的前驱节点。我当时在一个嵌入式项目里就吃过这个亏——一个数据采集模块，频繁删除中间节点，每次都要 O(n) 的查找时间，整个系统的实时性直接被拖垮。

嗯，这时候双链表就该登场了。

双链表的节点结构

双链表比单链表多了一个指针——指向前一个节点。说白了，就是每个节点都长了前后眼。

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

我个人习惯把双链表的头节点也做成一个完整的节点，prior 和 next 都指向自己，这样初始化的时候逻辑特别干净。

双链表的插入操作

插入操作比单链表麻烦一点，因为你要维护两个方向的指针。我在项目中见过不少新手在这里翻车——只更新了 next，忘了更新 prior。

// 在节点 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 有后继，更新其后继的 prior
        p->next->prior = s;
    s->prior = p;           // 3. s 的前驱指向 p
    p->next = s;            // 4. p 的后继指向 s
    return true;
}

你想想看，这四步的顺序其实有讲究。我建议先把 s 的指针都挂好，再去动 p 和 p->next 的指针。这样即使中间出问题，也不会破坏原有链表的结构。

双链表的删除操作

删除操作就优雅多了。因为双链表可以直接拿到前驱节点，不需要像单链表那样从头找。

// 删除节点 p
bool DeleteNode(DNode *p) {
    if (p == NULL) return false;
    
    p->prior->next = p->next;   // 前驱的 next 跳过 p
    if (p->next != NULL)        // 如果 p 有后继
        p->next->prior = p->prior; // 后继的 prior 跳过 p
    free(p);
    return true;
}

我曾经在一个内存池管理模块里用双链表来管理空闲块，删除操作 O(1) 的复杂度让整个分配器的性能提升了一个档次。这就是双链表的魅力——空间换时间。

循环链表：让遍历不再有终点

循环链表就是把单链表的最后一个节点的 next 指向头节点（或者第一个节点）。这样一来，整个链表就变成了一个环。

为什么要这么做？我举个例子你就明白了。在一个任务调度系统里，我们需要轮询所有任务，每个任务执行一个时间片。如果用普通单链表，执行完最后一个任务后，还得手动把指针重置到头节点。用循环链表，你只管往后走，永远走不到头——走到尾自然就回到了头。

// 循环链表的节点结构（和单链表一样）
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

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

循环链表的遍历终止条件

这是循环链表最核心的问题。普通链表遍历用 p != NULL 作为终止条件，循环链表不行——它永远不会为 NULL。

正确的做法是：判断是否回到了头节点。

// 遍历循环链表
void TraverseList(LinkList L) {
    if (L == NULL) return;
    LNode *p = L->next;  // 从第一个数据节点开始
    while (p != L) {     // 回到头节点就停止
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

嗯，这里要注意：如果循环链表是空的，那么 L->next == L，while 条件直接不成立，不会执行任何操作。这个逻辑是自洽的。

约瑟夫环问题实战

约瑟夫环问题，说白了就是一群人围成一圈报数，数到 m 的人出列，然后从下一个人重新开始报数，直到所有人都出列。这个问题用循环链表来解决，简直是天造地设的一对。

我记得第一次在课堂上讲这个问题时，有个学生问：「为什么不用数组？」我说你试试用数组模拟删除，每次删除都要移动大量元素，时间复杂度 O(n²)。而循环链表删除一个节点只需要 O(1)，整体复杂度 O(n×m)。

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

typedef struct LNode {
    int number;          // 编号
    struct LNode *next;
} LNode, *LinkList;

// 创建约瑟夫环
LinkList CreateJosephus(int n) {
    LinkList L = NULL;
    LNode *r = NULL;  // 尾指针
    
    for (int i = 1; i <= n; i++) {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        p->number = i;
        p->next = NULL;
        
        if (L == NULL) {
            L = p;
            p->next = p;  // 第一个节点指向自己
            r = p;
        } else {
            r->next = p;
            p->next = L;   // 新节点指向头节点
            r = p;         // 更新尾指针
        }
    }
    return L;
}

// 解决约瑟夫环问题
void Josephus(LinkList L, int m) {
    if (L == NULL) return;
    
    LNode *p = L;
    LNode *prev = NULL;
    
    // 找到尾节点（用于删除头节点时更新）
    while (p->next != L) {
        p = p->next;
    }
    prev = p;  // prev 指向尾节点
    p = L;     // p 指向头节点
    
    while (p->next != p) {  // 只剩一个节点时停止
        // 报数 m-1 次，找到要删除节点的前驱
        for (int i = 1; i < m; i++) {
            prev = p;
            p = p->next;
        }
        
        // 删除 p 节点
        printf("出列: %d\n", p->number);
        prev->next = p->next;
        free(p);
        
        // 从下一个节点重新开始
        p = prev->next;
    }
    
    // 最后一个节点
    printf("最后留下: %d\n", p->number);
    free(p);
}

int main() {
    int n = 7, m = 3;
    LinkList L = CreateJosephus(n);
    Josephus(L, m);
    return 0;
}

这个代码里有一个关键点：我们需要一个 prev 指针来记录当前节点的前驱。因为循环链表删除节点时，虽然可以通过遍历找到前驱，但那样效率就低了。用 prev 指针实时跟踪，删除操作就是 O(1)。

知识体系总览

下面这张图把双链表和循环链表的要点都串起来了，你可以对照着复习。

双链表和循环链表，说白了就是单链表的两个变种。一个解决了反向遍历的问题，一个解决了循环遍历的问题。在实际项目中，我建议你根据场景来选择：需要频繁删除中间节点？用双链表。需要轮询调度？用循环链表。

最后送你一句话：数据结构没有银弹，只有最合适的。理解了每种结构的优缺点，你才能在项目中做出正确的选择。

---

公众号:蓝海资料掘金营，微信deep3321