第22章线性表（三）

课程目录第22章线性表（三）

第22章线性表（三）：双向链表与循环链表、链表的应用（多项式相加）、静态链表的概念

各位同学，咱们继续聊链表。前面两章我们把单链表的基本操作讲透了，但实际项目中你会发现，单链表有个“硬伤”——只能从头往后走。你想往回找前一个节点？没门儿。这就引出了我们今天的主角：双向链表和循环链表。

22.1 双向链表：能进能退，才是真本事

双向链表，说白了就是在每个节点里多存一个指针，指向前一个节点。结构体长这样：

typedef struct DNode {
    int data;
    struct DNode *prev;  // 前驱指针
    struct DNode *next;  // 后继指针
} DNode, *DLinkList;

你想想看，单链表里删除一个节点，你得先找到它的前驱，否则没法删。双向链表就没这烦恼——我拿着当前节点，直接通过 prev 就能找到前一个。

核心优势：双向链表的插入和删除操作，时间复杂度从 O(n) 降到了 O(1)（前提是你已经定位到了目标节点）。

我在项目中做过一个内存缓存池，里面用双向链表管理空闲块。每次回收内存时，需要快速把相邻的空闲块合并。用双向链表，我直接通过 prev 和 next 检查前后邻居，代码写起来特别顺手。

22.1.1 双向链表的插入操作

插入操作分四种情况：头插、尾插、中间插、在指定节点前插。我重点讲一下在节点 p 之前插入新节点 s：

s->prev = p->prev;
s->next = p;
if (p->prev != NULL)
    p->prev->next = s;
p->prev = s;

我曾经踩过的坑：写双向链表插入时，最容易忘掉处理 p->prev->next = s 这一步。结果链表就断了，调试了半天才发现。记住：先接好新节点的两个指针，再断开旧连接。

22.1.2 双向链表的删除操作

删除节点 p 就简单多了：

if (p->prev != NULL)
    p->prev->next = p->next;
if (p->next != NULL)
    p->next->prev = p->prev;
free(p);

嗯，这里要注意：如果 p 是头节点，p->prev 是 NULL，直接跳过就行。

22.2 循环链表：首尾相连，循环往复

循环链表就是把单链表的尾节点指向头节点，形成一个环。为什么要这么做？我举个例子你就明白了。

在操作系统的进程调度中，时间片轮转算法就用到了循环链表。每个进程跑完一个时间片，调度器就移到下一个进程。如果到了末尾，自动回到开头继续。用循环链表实现，你根本不用判断“是不是最后一个节点”——直接 p = p->next 就行了。

22.2.1 循环链表的遍历

遍历循环链表时，终止条件不再是 p == NULL，而是 p == head：

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

小技巧：我习惯在循环链表里加一个“哨兵节点”（也叫头节点），不存数据，只用来标记起点和终点。这样空链表和非空链表的操作就能统一了。

22.3 链表的经典应用：多项式相加

多项式相加是链表应用的经典案例。每个多项式可以看作由若干“项”组成的链表，每项包含系数和指数。比如：

3x^5 + 2x^3 + x + 7

用链表表示就是：

typedef struct Term {
    float coef;  // 系数
    int expn;    // 指数
    struct Term *next;
} Term, *Polynomial;

两个多项式相加的算法，说白了就是合并两个有序链表——按指数降序排列，指数相同的系数相加，指数不同的直接插入。

22.3.1 多项式相加的核心逻辑

Polynomial AddPolynomial(Polynomial A, Polynomial B) {
    Polynomial C = (Polynomial)malloc(sizeof(Term));
    Term *pa = A->next, *pb = B->next, *pc = C;
    
    while (pa != NULL && pb != NULL) {
        if (pa->expn > pb->expn) {
            pc->next = pa; pa = pa->next;
        } else if (pa->expn < pb->expn) {
            pc->next = pb; pb = pb->next;
        } else {
            // 指数相等，系数相加
            float sum = pa->coef + pb->coef;
            if (sum != 0) {
                Term *t = (Term*)malloc(sizeof(Term));
                t->coef = sum;
                t->expn = pa->expn;
                pc->next = t;
                pc = t;
            }
            pa = pa->next;
            pb = pb->next;
            continue;
        }
        pc = pc->next;
    }
    pc->next = (pa != NULL) ? pa : pb;
    return C;
}

注意：系数相加为0时，这一项要直接丢弃，不能留在结果里。我在做数值计算项目时，就因为没处理这个细节，导致结果里多了一堆“0x^N”的项，被同事笑话了。

22.4 静态链表：用数组模拟链表

有些场景下，你不能用动态内存分配（比如嵌入式系统里没有堆），但又想用链表的灵活性。怎么办？静态链表就是答案。

静态链表用数组来存储节点，每个节点除了数据，还有一个“游标”（cur），指向下一个节点的数组下标。最后一个节点的游标为 -1 或 0，表示结束。

#define MAXSIZE 100
typedef struct {
    int data;
    int cur;  // 游标，相当于 next 指针
} StaticNode, StaticList[MAXSIZE];

静态链表的插入和删除，本质上是在数组里维护一个“空闲链表”。你删除一个节点，就把它的下标放回空闲链表；插入时，从空闲链表取一个下标。

我个人习惯：用数组下标 0 作为空闲链表的头节点，下标 1 作为数据链表的头节点。这样管理起来特别清晰。

22.4.1 静态链表的优缺点

优点	缺点
不需要动态内存分配，适合嵌入式环境	数组大小固定，不能动态扩展
插入删除不需要移动元素	访问元素仍需遍历，不支持随机访问
内存连续，缓存友好	实现比动态链表复杂

我在做单片机项目时用过静态链表管理传感器数据缓冲区。因为单片机内存只有 2KB，用 malloc 容易碎片化，静态链表正好解决了这个问题。

22.5 本章知识体系

下面这张图帮你理清本章的知识脉络：

好了，这一章的内容就到这里。双向链表和循环链表是单链表的自然延伸，多项式相加是链表应用的经典案例，静态链表则是在受限环境下的巧妙替代方案。把这些吃透了，你就能在合适的场景下选择合适的链表结构。

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

📚 课程目录