用 c 源码实现链表：结构定义、节点操作与常见问题

链表是由多个节点串接而成的数据结构。与数组将元素连续存放不同，链表中的节点可以分散在内存各处，节点之间通过指针建立顺序关系。理解链表，重点不只是记住“节点里有一个指针”，还要处理好节点所有权、边界条件和动态内存的生命周期。

本文从单向链表开始，用标准 C 实现初始化、插入、读取、删除和销毁操作，并给出一份可以编译运行的完整示例。示例以整数为节点数据，适合学习链表的基本机制；如果要存放字符串、结构体或资源句柄，还需要进一步明确数据的复制和释放规则。

链表适合什么场景

链表的优势是：在已经找到插入或删除位置的情况下，修改相邻指针通常是常数时间，不需要像数组那样搬移后续元素。它也不要求预先分配一整块连续空间，适用于元素数量变化较大、且经常在已知位置插入或删除的场景。

不过，“链表插入是 O(1)”有一个重要前提：插入位置已经确定。若要在单向链表中按下标插入，通常得从头遍历到该位置，整体仍是 O(n)。按下标读取也需要遍历，不能像数组那样直接通过下标定位。链表节点还要额外存放指针，访问时的缓存局部性通常也不如连续数组。

适合：元素数量动态变化，且经常在已知节点附近插入或删除。
不一定适合：频繁随机访问、追求较低内存开销，或数据规模较小且数组搬移成本可接受。
需要审慎评估：实时性要求严格、内存碎片敏感，或需要多线程并发访问的程序。

链表不是数组的普遍替代品。实际选择时，应该结合访问模式和内存管理成本，而不是只比较某一种操作的渐进复杂度。

节点与链表的结构定义

单向链表的节点保存数据和下一个节点的地址。最后一个节点的 next 为 NULL。下面的实现额外保存头指针、尾指针和节点数量，这样在尾部追加时不必遍历整个链表。

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

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

typedef struct List {
    Node *head;
    Node *tail;
    size_t size;
} List;

这里有几个需要始终成立的约定：

空链表满足 head == NULL、tail == NULL、size == 0。
非空链表的 head 和 tail 都指向有效节点，且 tail->next == NULL。
size 等于从头节点沿 next 能访问到的节点数。
链表拥有其节点：节点由链表操作分配，并在删除或清空时释放。

size_t 是 C 标准库中适合表达对象大小和数量的无符号整数类型。它不能表示负数，所以按下标访问时，要先判断下标与链表大小的关系，不能通过“负数下标”表达错误位置。

初始化与清空

初始化函数把链表设为空状态。调用其他操作前，必须先初始化链表；不能把未初始化的局部变量直接当作空链表使用。

static void list_init(List *list)
{
    if (list == NULL) {
        return;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

销毁链表时，需要从头开始逐个释放节点。释放当前节点后，不能再读取它的 next，所以要先保存后继指针。

static void list_clear(List *list)
{
    if (list == NULL) {
        return;
    }

    Node *current = list->head;
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

list_clear 对空指针不做操作，因此可以用于清空已初始化的空链表。但这不意味着它能安全处理未初始化的链表对象：函数仍要读取 list->head。调用者必须先调用 list_init，并确保链表中的节点没有被其他代码提前释放。

创建节点与尾部追加

节点通过 malloc 动态分配。分配失败时，malloc 返回 NULL，调用者应收到失败结果，而不能继续写入节点字段。下面的接口返回 bool：true 表示追加成功，false 表示参数无效、数量达到上限或内存分配失败。

static bool list_push_back(List *list, int value)
{
    if (list == NULL || list->size == SIZE_MAX) {
        return false;
    }

    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->value = value;
    node->next = NULL;

    if (list->tail == NULL) {
        /* 空链表：新节点同时是头节点和尾节点。 */
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }

    list->size++;
    return true;
}

SIZE_MAX 是 size_t 能表示的最大值。若数量已经达到上限，再执行递增会发生无符号回绕，因此示例在递增前拒绝操作。正常程序通常不可能真的分配到这么多节点，但检查能明确接口的边界。

这里的节点只存一个 int，所以无需另外分配数据。若改成保存字符串指针，必须决定链表是“只保存外部指针”，还是“复制字符串并负责释放”。两种设计的所有权不同，不能在释放节点时想当然地对数据指针调用 free。

按下标插入

插入位置允许从 0 到 size，其中 0 表示插入头部，size 表示追加到尾部。大于 size 的位置无效。插入前先检查边界和数量上限，再分配节点；这样分配失败时，链表原状态不变。

static bool list_insert_at(List *list, size_t index, int value)
{
    if (list == NULL || index > list->size || list->size == SIZE_MAX) {
        return false;
    }

    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->value = value;
    node->next = NULL;

    if (index == 0) {
        node->next = list->head;
        list->head = node;

        if (list->tail == NULL) {
            list->tail = node;
        }
    } else {
        Node *previous = list->head;

        for (size_t i = 1; i < index; i++) {
            previous = previous->next;
        }

        node->next = previous->next;
        previous->next = node;

        if (index == list->size) {
            list->tail = node;
        }
    }

    list->size++;
    return true;
}

循环从头节点移动到新节点的前一个节点。边界检查保证了在 index > 0 时链表非空，并且前驱节点存在。若改动边界条件或循环范围，很容易出现空指针解引用，建议每次都用空链表、头部和尾部位置验证指针变化。

读取与按下标删除

读取操作要求下标严格小于 size。输出参数也要检查是否为空，避免把结果写入无效地址。遍历到目标节点后复制整数值，不把内部节点指针暴露给调用者，可以减少调用者意外改坏链表结构的机会。

static bool list_get(const List *list, size_t index, int *out_value)
{
    if (list == NULL || out_value == NULL || index >= list->size) {
        return false;
    }

    const Node *current = list->head;
    for (size_t i = 0; i < index; i++) {
        current = current->next;
    }

    *out_value = current->value;
    return true;
}

删除操作同样要求 index < size。输出参数在示例中允许为空：传入非空指针时返回被删除的值，传入 NULL 时只删除节点。删除头节点、删除尾节点和删除唯一节点需要分别更新链表状态。

static bool list_remove_at(List *list, size_t index, int *out_value)
{
    if (list == NULL || index >= list->size) {
        return false;
    }

    Node *removed;

    if (index == 0) {
        removed = list->head;
        list->head = removed->next;

        if (list->head == NULL) {
            list->tail = NULL;
        }
    } else {
        Node *previous = list->head;

        for (size_t i = 1; i < index; i++) {
            previous = previous->next;
        }

        removed = previous->next;
        previous->next = removed->next;

        if (removed == list->tail) {
            list->tail = previous;
        }
    }

    if (out_value != NULL) {
        *out_value = removed->value;
    }

    free(removed);
    list->size--;
    return true;
}

先保存被删除节点，再调整链接，最后释放节点。释放后，removed 就不能再解引用。调用者也不应保留指向该节点的指针；本实现没有对外提供节点指针，因此正常使用时不需要处理这种悬空引用。

可运行的完整示例

以下代码将前面的实现组合为一个完整程序。保存为 list.c，使用支持 C11 的编译器构建，例如 cc -std=c11 -Wall -Wextra -Wpedantic list.c -o list，然后运行生成的程序。若编译器不支持 C11，可尝试将标准选项改为其支持的版本；示例本身使用的语言特性较基础。

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

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

typedef struct List {
    Node *head;
    Node *tail;
    size_t size;
} List;

static void list_init(List *list)
{
    if (list == NULL) {
        return;
    }
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

static void list_clear(List *list)
{
    if (list == NULL) {
        return;
    }

    Node *current = list->head;
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

static bool list_push_back(List *list, int value)
{
    if (list == NULL || list->size == SIZE_MAX) {
        return false;
    }

    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->value = value;
    node->next = NULL;

    if (list->tail == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }

    list->size++;
    return true;
}

static bool list_insert_at(List *list, size_t index, int value)
{
    if (list == NULL || index > list->size || list->size == SIZE_MAX) {
        return false;
    }

    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->value = value;
    node->next = NULL;

    if (index == 0) {
        node->next = list->head;
        list->head = node;
        if (list->tail == NULL) {
            list->tail = node;
        }
    } else {
        Node *previous = list->head;
        for (size_t i = 1; i < index; i++) {
            previous = previous->next;
        }

        node->next = previous->next;
        previous->next = node;
        if (index == list->size) {
            list->tail = node;
        }
    }

    list->size++;
    return true;
}

static bool list_get(const List *list, size_t index, int *out_value)
{
    if (list == NULL || out_value == NULL || index >= list->size) {
        return false;
    }

    const Node *current = list->head;
    for (size_t i = 0; i < index; i++) {
        current = current->next;
    }

    *out_value = current->value;
    return true;
}

static bool list_remove_at(List *list, size_t index, int *out_value)
{
    if (list == NULL || index >= list->size) {
        return false;
    }

    Node *removed;

    if (index == 0) {
        removed = list->head;
        list->head = removed->next;
        if (list->head == NULL) {
            list->tail = NULL;
        }
    } else {
        Node *previous = list->head;
        for (size_t i = 1; i < index; i++) {
            previous = previous->next;
        }

        removed = previous->next;
        previous->next = removed->next;
        if (removed == list->tail) {
            list->tail = previous;
        }
    }

    if (out_value != NULL) {
        *out_value = removed->value;
    }

    free(removed);
    list->size--;
    return true;
}

static void list_print(const List *list)
{
    if (list == NULL) {
        puts("(null list)");
        return;
    }

    const Node *current = list->head;
    while (current != NULL) {
        printf("%d", current->value);
        current = current->next;
        if (current != NULL) {
            printf(" -> ");
        }
    }
    printf("  (size=%zu)\n", list->size);
}

int main(void)
{
    List list;
    list_init(&list);

    if (!list_push_back(&list, 10) ||
        !list_push_back(&list, 30) ||
        !list_insert_at(&list, 1, 20)) {
        fprintf(stderr, "创建或插入节点失败\n");
        list_clear(&list);
        return EXIT_FAILURE;
    }

    list_print(&list); /* 10 -> 20 -> 30 */

    int value;
    if (list_get(&list, 1, &value)) {
        printf("下标 1 的值：%d\n", value);
    }

    if (list_remove_at(&list, 1, &value)) {
        printf("删除的值：%d\n", value);
    }

    list_print(&list); /* 10 -> 30 */

    list_clear(&list);
    list_print(&list); /* 空链表 */

    return EXIT_SUCCESS;
}

这份示例用短路求值检查连续操作：任意一次插入失败都会进入错误处理分支，并清理此前已经创建的节点。实际项目中，若需要区分参数错误和内存不足，可把返回类型改为枚举状态码；单一的 bool 只说明成功或失败，不提供失败原因。

复杂度与接口边界

list_push_back：有尾指针时为 O(1)，不计内存分配器内部开销。
list_insert_at：最坏 O(n)，因为要找到插入位置的前驱。
list_get 和 list_remove_at：最坏 O(n)。
list_clear：O(n)，每个节点释放一次。
额外空间：每个节点保存一个后继指针；链表对象本身还保存头、尾指针和数量。

接口有明确的参数限制：所有操作要求传入已初始化且未被破坏的 List；下标必须使用 size_t 表示；读取必须提供非空输出指针；删除的输出指针可以为空。传入一个伪造的、已释放的或未初始化的链表对象，不属于这些函数能够安全识别并恢复的情况。

常见错误与排查方法

1. 忘记处理空链表和单节点链表

删除唯一节点后，头指针和尾指针都必须变成 NULL。如果只更新头指针，尾指针就会悬空；之后再尾部追加，可能写入已释放的内存。测试时至少覆盖空链表、一个节点、删除头节点、删除尾节点四种情况。

2. 先释放节点，再读取后继指针

free(current) 之后，访问 current->next 是未定义行为。遍历释放时先保存 next，是简单且关键的习惯。同样，删除节点后不要继续使用指向它的指针。

3. 边界比较写错

插入位置可以等于 size，因此检查条件是 index > size；读取和删除要求位置上确有节点，因此条件是 index >= size。混淆这两种规则，容易导致尾部插入失败，或在读取、删除时越过链表末尾。

4. 分配失败后仍然使用节点

malloc 可能返回 NULL。必须先检查结果，再写入字段。不要用“内存通常够用”代替错误处理，也不要在失败路径上丢失已有链表。

5. 复制链表结构体造成共享所有权

直接执行 List copy = original; 只会复制头指针、尾指针和数量，不会复制节点。两个链表对象随后指向同一批节点，若分别清理就可能重复释放；修改其中一个也可能影响另一个。若需要独立副本，应逐节点分配并复制数据，且正确处理复制过程中的分配失败。

6. 数据指针的生命周期没有约定

若节点保存的是 char * 或其他指针，必须明确节点是否拥有指向的数据。若只是借用指针，数据必须在节点使用期间保持有效，释放节点时不能擅自释放它；若由链表拥有，就要在插入时复制或转移所有权，并在删除时使用匹配的释放方式。

7. 把链表当作线程安全容器

上述实现没有锁，也没有并发安全保证。多个线程同时插入、删除或遍历同一链表，可能造成数据竞争、指针损坏或释放后访问。并发场景需要外部同步或专门设计的并发数据结构；仅仅把指针声明为 volatile 不能解决线程同步问题。

调试、验证与安全边界

链表错误常表现为崩溃、重复输出、节点丢失或程序退出时出现内存问题。开发时可以打开编译器警告，并使用 AddressSanitizer 等工具检查越界访问、释放后使用和内存泄漏。例如，在支持该工具的编译环境中，可尝试用 -fsanitize=address -fno-omit-frame-pointer 编译，再运行测试。具体选项是否可用，取决于编译器和运行环境。

单元测试应覆盖空表操作、头部和尾部插入、非法下标、连续删除、清空后再插入等情况。每次操作后，都可以遍历节点并核对实际数量与 size，同时检查空表时头尾指针均为空、非空表时尾节点的 next 为空。

这份实现展示的是基础数据结构，不是安全边界。它不会验证链表对象是否被恶意伪造，也没有防止并发竞争、限制节点总量或隔离内存的功能。处理不可信输入时，应先校验输入长度与索引，合理限制可分配资源，并确保所有失败路径都能正确清理；链表本身不能替代输入验证、访问控制或其他安全措施。

总结

实现链表时，真正容易出错的部分通常不是结构定义，而是每次操作后是否维护了头指针、尾指针和节点数量之间的一致性。先明确节点所有权和接口边界，再逐一处理空表、头尾位置与分配失败，代码就更容易检查和测试。掌握这些原则后，可以在此基础上扩展查找、按值删除、反转、合并，或实现双向链表；扩展时仍应保持清晰的所有权规则与可验证的不变量。

AI资讯 # c 源码

文章版权归作者所有，未经允许请勿转载。

用 c 源码实现链表：结构定义、节点操作与常见问题

用 c 源码实现链表：结构定义、节点操作与常见问题

链表适合什么场景

节点与链表的结构定义

初始化与清空

创建节点与尾部追加

按下标插入

读取与按下标删除

可运行的完整示例

复杂度与接口边界

常见错误与排查方法

1. 忘记处理空链表和单节点链表

2. 先释放节点，再读取后继指针

3. 边界比较写错

4. 分配失败后仍然使用节点

5. 复制链表结构体造成共享所有权

6. 数据指针的生命周期没有约定

7. 把链表当作线程安全容器

调试、验证与安全边界

总结

js文字特效怎么做：从动态打字到逐字渐显

.php怎么用：从准备到完成的实操步骤

相关文章

天蝎座：解讀幸運數字的秘密，掌控命運之輪 (天蝎座解读女)

揭开十二星座爱情的神秘面纱：各个星座在爱情中表现出的独特特征与相处之道 (揭开十二星座的秘密)

从新手到专业：全面解析Runway技巧，助你在时尚界大放异彩！ (从新手到专业玩家)

掌握亿图脑图的高效用法，让你的思维导图更具创意与条理 (亿图脑图mindmaster官网)

热门网址

网址

最新资讯

用 c 源码实现链表：结构定义、节点操作与常见问题

用 c 源码实现链表：结构定义、节点操作与常见问题

链表适合什么场景

节点与链表的结构定义

初始化与清空

创建节点与尾部追加

按下标插入

读取与按下标删除

可运行的完整示例

复杂度与接口边界

常见错误与排查方法

1. 忘记处理空链表和单节点链表

2. 先释放节点，再读取后继指针

3. 边界比较写错

4. 分配失败后仍然使用节点

5. 复制链表结构体造成共享所有权

6. 数据指针的生命周期没有约定

7. 把链表当作线程安全容器

调试、验证与安全边界

总结

js文字特效怎么做：从动态打字到逐字渐显

.php怎么用：从准备到完成的实操步骤

相关文章

天蝎座：解讀幸運數字的秘密，掌控命運之輪 (天蝎座解读女)

揭开十二星座爱情的神秘面纱：各个星座在爱情中表现出的独特特征与相处之道 (揭开十二星座的秘密)

从新手到专业：全面解析Runway技巧，助你在时尚界大放异彩！ (从新手到专业玩家)

掌握亿图脑图的高效用法，让你的思维导图更具创意与条理 (亿图脑图mindmaster官网)

热门网址

网址

最新资讯

标签云