第34章链表进阶

课程目录第34章链表进阶

第34章：链表进阶——双向链表与循环链表

单向链表，咱们已经聊透了。但说实话，在实际项目中，单向链表有时候真不够用。我记得有一次做嵌入式GUI的菜单系统，用单向链表做页面导航，结果想回退到上一页时，得从头遍历——那叫一个痛苦。后来我果断换成了双向链表，问题迎刃而解。

这一章，咱们就把双向链表和循环链表彻底讲明白。你想想看，这两种结构其实就是在单向链表的基础上，做了点“小手术”，但能力却翻倍了。

34.1 双向链表：能往前走，也能往后走

单向链表的每个节点，只知道自己下一个兄弟是谁。双向链表呢？每个节点还知道自己上一个兄弟是谁。说白了，就是多了一个指针域。

核心区别：

单向链表：一个数据域 + 一个next指针
双向链表：一个数据域 + 一个prev指针 + 一个next指针

34.1.1 节点定义

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

嗯，这里要注意：prev指向的是前一个节点，next指向的是后一个节点。头节点的prev一般是NULL，尾节点的next也是NULL。

34.1.2 双向链表的插入操作

插入操作比单向链表稍微麻烦一点，因为你要维护两个方向的指针。我个人的习惯是：先搞定新节点和它的前后邻居，再调整邻居的指针。顺序搞反了，链表就断了。

// 在p节点之后插入新节点s
int InsertAfter(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return -1;

    s->next = p->next;   // ① s的后继指向p的后继
    s->prev = p;          // ② s的前驱指向p

    if (p->next != NULL)  // ③ 如果p有后继，调整其后继的前驱
        p->next->prev = s;

    p->next = s;          // ④ p的后继指向s
    return 0;
}

我曾经在调试一个双向链表插入时，忘了第③步，结果链表后半截直接“失联”了。排查了半天才发现，p的后继节点还傻傻地指向原来的前驱，根本没更新。避坑指南：双向链表操作，一定要把四个指针都照顾到。

34.1.3 双向链表的删除操作

// 删除节点p
int DeleteNode(DNode *p) {
    if (p == NULL) return -1;

    if (p->prev != NULL)
        p->prev->next = p->next;   // 前驱的后继指向p的后继

    if (p->next != NULL)
        p->next->prev = p->prev;   // 后继的前驱指向p的前驱

    free(p);  // 释放节点内存
    return 0;
}

删除操作相对简单，核心就是让p的前后节点“手拉手”，然后释放p。注意：如果p是头节点或尾节点，要单独处理边界情况。

34.2 循环链表：首尾相连，闭环运行

循环链表，就是把单向或双向链表的尾节点指向头节点，形成一个环。为什么要这么做？我举个例子：在操作系统的任务调度中，时间片轮转算法就用到了循环链表。每个任务执行完，就轮到下一个，周而复始，没有终点。

循环链表的两种形态：

单向循环链表：尾节点的next指向头节点
双向循环链表：尾节点的next指向头节点，头节点的prev指向尾节点

34.2.1 单向循环链表的创建

// 创建单向循环链表（尾插法）
DNode* CreateCircularList(int arr[], int n) {
    if (n <= 0) return NULL;

    DNode *head = (DNode*)malloc(sizeof(DNode));
    head->data = arr[0];
    head->next = head;  // 先指向自己，形成环
    DNode *tail = head;

    for (int i = 1; i < n; i++) {
        DNode *newNode = (DNode*)malloc(sizeof(DNode));
        newNode->data = arr[i];
        newNode->next = head;  // 新节点的next指向头节点
        tail->next = newNode;  // 尾节点指向新节点
        tail = newNode;        // 更新尾节点
    }
    return head;
}

注意看：创建第一个节点时，它的next指向自己。之后每个新节点，next都指向头节点。这样遍历时，只要判断当前节点的next是否等于头节点，就知道是不是转完一圈了。

34.2.2 循环链表的遍历

void TraverseCircularList(DNode *head) {
    if (head == NULL) return;

    DNode *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);  // 回到头节点时停止
    printf("\n");
}

这里用do-while而不是while，是因为一开始p就指向head，如果用while，循环体一次都不会执行。嗯，这个小细节，面试经常考。

34.3 双向循环链表：最强形态

把双向链表和循环链表结合起来，就是双向循环链表。头节点的prev指向尾节点，尾节点的next指向头节点。这种结构在Linux内核的双向链表实现中广泛使用。

双向循环链表的优势：

从头节点出发，可以O(1)时间访问尾节点（head->prev）
从任意节点出发，可以向前或向后遍历整个链表
插入和删除操作，不需要单独处理头尾边界

34.3.1 双向循环链表的插入

// 在p节点之后插入s（双向循环链表）
void InsertInCircular(DNode *p, DNode *s) {
    s->next = p->next;
    s->prev = p;
    p->next->prev = s;
    p->next = s;
}

你看，因为链表是循环的，p->next永远不为NULL（最坏情况指向头节点自己），所以不需要像普通双向链表那样判断p->next是否为NULL。代码简洁了不少。

34.4 三种链表的对比

特性	单向链表	双向链表	循环链表
内存占用	小（1个指针）	中（2个指针）	取决于实现
向前遍历	不支持	支持	支持（双向循环）
尾节点访问	O(n)	O(n)	O(1)（有尾指针）
插入/删除效率	高（已知前驱）	高	高
典型应用	栈、队列	LRU缓存、编辑器	时间片轮转、约瑟夫环

34.5 知识体系图

34.6 避坑指南与实战建议

我曾经踩过的坑：

忘记初始化prev指针：创建新节点时，prev一定要赋值为NULL，否则野指针会让你崩溃。
循环链表死循环：遍历时判断条件写错，导致无限循环。建议用do-while配合p != head判断。
内存泄漏：删除节点后，记得free。尤其是循环链表，要先把环断开再逐个释放。

我的个人习惯：

写链表操作前，先在纸上画图。指针怎么指，画清楚了再写代码。
插入和删除操作，统一用“先连后断”原则：先建立新连接，再断开旧连接。
调试时，打印每个节点的地址和data，配合prev和next的值，一眼就能看出链表结构对不对。

好了，双向链表和循环链表的核心概念和基本操作，咱们就聊到这儿。这两种结构在实际项目中非常实用，尤其是双向循环链表，堪称链表界的“瑞士军刀”。你写代码时多练练，很快就能上手。

📚 课程目录