C 语言中用二级指针优雅地操作链表

2024-09-26更新于 2026-10-02约 4 分钟0 阅读问问 AI

问题背景

链表操作中，删除一个节点通常需要维护前驱指针 prev，并且对"删除头节点"做特殊处理。C 语言中有一个更简洁的惯用写法：用二级指针（list_item **）直接操作"指向当前节点的指针"，从而把删除、插入等操作统一成同一种模式。

下面以单链表为例，逐步展示从传统写法到优雅写法的演进。所有代码均为教学示例，未包含空指针检查、内存释放和并发保护，直接用于生产环境前需自行补全。

传统写法：维护 prev 指针

cpp

void remove_cs101(list *l, list_item *target)
{
        list_item *cur = l->head, *prev = NULL;
        while (cur != target) {
                prev = cur;
                cur = cur->next;
        }
        if (prev)
                prev->next = cur->next;
        else
                l->head = cur->next;
}

逻辑很直白：遍历到目标节点，用 prev->next 跳过它；如果目标恰好是头节点（prev == NULL），则修改 l->head。问题在于头节点需要单独分支，且 prev 的维护在更复杂的操作中容易出错。

优雅写法：二级指针

cpp

void remove_elegant(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        *p = target->next;
}

核心变化只有一行：list_item **p = &l->head;。p 始终指向"存放当前节点地址的那个变量"，因此：

初始时 *p 就是 l->head，p 指向 l->head 本身。
每走一步，p = &(*p)->next，让 p 指向下一个节点的 next 字段。
找到目标后，*p = target->next 一行完成"摘除"，无论目标是头节点还是中间节点，逻辑完全一致。

这样就不需要 prev，也不需要 if (prev) 分支。

注意：这段代码假设 target 一定存在于链表中。如果 target 为 NULL 或不在链表中，while 循环会越界解引用，导致未定义行为。实际使用时应在调用前校验，或在循环中加 *p != NULL 的终止条件。

抽象为 find_indirect

把"找到指向目标节点的指针"这一步抽成独立函数，后续删除、插入都可以复用：

cpp

static inline list_item **find_indirect(list *l, list_item *target)
{
        list_item **p = &l->head;
        while (*p != target)
                p = &(*p)->next;
        return p;
}

find_indirect 返回的是 list_item **，即"指向目标节点的那个指针的地址"。调用者拿到它之后，只需对 *p 赋值就能修改链表结构。

同样地，这个函数没有处理 target 不存在的情况。如果链表为空（l->head 为 NULL）且 target 非空，或链表非空但 target 不在其中，循环最终会在 *p == NULL 时仍判定 *p != target 为真，随后执行 &(*p)->next 即对空指针取成员地址，触发未定义行为。生产代码中应增加边界检查。

用 find_indirect 实现插入

cpp

void insert_before(list *l, list_item *before, list_item *item)
{
        list_item **p = find_indirect(l, before);
        *p = item;
        item->next = before;
}

insert_before 在 before 节点之前插入 item：

用 find_indirect 拿到指向 before 的指针的指针 p。
*p = item：让前驱的 next（或 l->head）指向新节点。
item->next = before：新节点接上原来的 before。

时间复杂度为 O(n)，n 为链表长度，因为 find_indirect 需要线性遍历。如果 before 本身就是头节点，*p 修改的就是 l->head，无需特判。

辅助函数：求链表长度

cpp

size_t size(list *l)
{
        size_t k = 0;
        list_item *cur = l->head;
        while (cur) {
                cur = cur->next;
                k++;
        }
        return k;
}

简单的遍历计数。这里用 size_t 作为计数类型，它是 C 标准中用于表示对象大小和元素个数的无符号整数类型，在 64 位平台上为 64 位宽，可避免用 32 位 int 计数时理论上可能出现的溢出。

风险与边界提醒

目标不存在：remove_elegant 和 find_indirect 都假设目标节点在链表中。若传入 NULL 或不在链表中的指针，行为未定义。调用方应保证合法性，或在函数内部加 assert / 返回值检查。
内存释放：示例只修改了指针，没有 free(target)。调用者负责释放被摘除节点的内存，否则会产生内存泄漏。
并发：以上代码没有任何锁或原子操作，多线程环境下不可直接使用。
链接可见性：find_indirect 声明为 static inline，static 将其链接属性限定为内部链接，即只在当前翻译单元内可见。若需跨文件使用，可去掉 static 并在头文件中声明，或保持 static inline 并将定义放入头文件供各翻译单元各自内联。
未验证：以上代码为教学片段，未在实际硬件或特定编译器上编译验证，移植前请根据目标平台调整。

小结

二级指针（T **）是 C 语言中操作链表的经典技巧：它让"修改某个节点的 next 字段"和"修改 head 字段"变成同一种操作，消除了头节点特判，使删除、插入等操作的代码结构高度一致。理解这一模式后，再遇到需要"在某个位置修改指针"的场景（如红黑树旋转中修改父节点的孩子指针、双向链表解链），都可以用同样的思路简化逻辑。