C 语言里的“链表”一般指单向链表/双向链表这类用“节点 + 指针”串起来的动态数据结构。它的核心是：每个节点保存数据，并保存指向下一个（以及可选的上一个）节点的指针；节点通过 malloc/free 动态申请与释放。

下面以最常用的单向链表为主讲清楚实现方式与常见操作。

---

1) 数据结构：节点与链表头

方式 A：只有“头指针”

最简单的单链表只需要一个指向首节点的指针：

C

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

Node *head = NULL;   // 空链表

方式 B：封装成“链表对象”（推荐）

把头指针、长度等都封装起来，接口更清晰：

C

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

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

---

2) 基本内存管理：创建与销毁节点

C

#include <stdlib.h>

Node *node_create(int value) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return NULL;   // malloc 失败要处理
    n->data = value;
    n->next = NULL;
    return n;
}

void node_destroy(Node *n) {
    free(n);
}

链表是动态结构，必须保证每次 malloc 对应一次 free，不然就泄漏。

---

3) 常见操作实现（单向链表）

下面以 List 封装形式举例。

初始化 / 清空

C

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

void list_clear(List *list) {
    Node *cur = list->head;
    while (cur) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->size = 0;
}

头插（O(1)）

C

int list_push_front(List *list, int value) {
    Node *n = node_create(value);
    if (!n) return 0;
    n->next = list->head;
    list->head = n;
    list->size++;
    return 1;
}

尾插

• 如果只有 head，尾插需要遍历到末尾，O(n)
• 若维护 tail 指针可做到 O(1)（这里先给不带 tail 的版本）

C

int list_push_back(List *list, int value) {
    Node *n = node_create(value);
    if (!n) return 0;

    if (!list->head) {
        list->head = n;
    } else {
        Node *cur = list->head;
        while (cur->next) cur = cur->next;
        cur->next = n;
    }
    list->size++;
    return 1;
}

删除指定值的第一个节点（O(n)）

需要维护前驱指针 prev：

C

int list_remove_first(List *list, int value) {
    Node *cur = list->head;
    Node *prev = NULL;

    while (cur) {
        if (cur->data == value) {
            if (prev) prev->next = cur->next;
            else      list->head = cur->next; // 删除头结点
            free(cur);
            list->size--;
            return 1;
        }
        prev = cur;
        cur = cur->next;
    }
    return 0; // 没找到
}

查找（O(n)）

C

Node *list_find(List *list, int value) {
    for (Node *cur = list->head; cur; cur = cur->next) {
        if (cur->data == value) return cur;
    }
    return NULL;
}

遍历打印

C

#include <stdio.h>

void list_print(const List *list) {
    const Node *cur = list->head;
    while (cur) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

---

4) “带头结点”(哨兵) 的写法（工程里很常见）

很多实现会放一个不存有效数据的头结点（sentinel），好处是：插入/删除时少写很多 “如果是头结点怎么办” 的分支。

结构示意：

• head 永远存在
• 真正第一个元素是 head->next

---

5) 双向链表与循环链表（概念要点）

双向链表节点

C

typedef struct DNode {
    int data;
    struct DNode *prev, *next;
} DNode;

优点：已知某个节点时，删除它是 O(1)（不用找前驱）；缺点：多一个指针，插入删除要维护 prev/next，更容易写错。

循环链表

尾节点 next 指回头节点（或哨兵），常用于队列、约瑟夫环等。实现要点是处理“终止条件”（不再是 NULL）。

---

6) C 链表实现最容易出错的点

1. 删除节点时忘了保存 next：比如 free(cur) 后再访问 cur->next 就是 UAF（Use-After-Free）。
2. 头结点删除没处理好（所以哨兵头结点很有价值）。
3. malloc 失败不处理（嵌入式或压力测试会踩）。
4. 内存泄漏：函数提前 return ���忘了释放已申请资源。
5. 指针断链：插入/删除次序写错（应该先连新节点，再改头指针等）。