手写单链表的 5 个细节

单链表是数据结构的基础，但手写时很容易踩坑。本文总结 5 个关键细节，帮助你写出健壮、无内存泄漏的链表代码。

细节 1：头指针 vs 头结点

头指针直接指向第一个节点，空表时为 NULL。头结点是额外分配的哑节点，不存储数据，空表时仍然存在。推荐使用头结点，可以统一插入删除逻辑。

/* 头指针版本：空表需要特殊处理 */
void insert_head(Node **head, int val) {
    Node *n = malloc(sizeof(Node));
    n->val = val;
    n->next = *head;
    *head = n;
}

/* 头结点版本：逻辑统一 */
void insert_head(Node *dummy, int val) {
    Node *n = malloc(sizeof(Node));
    n->val = val;
    n->next = dummy->next;
    dummy->next = n;
}

细节 2：插入时的前驱定位

在指定位置插入时，必须保存前驱指针。常见错误是只保存当前指针，导致无法链接前驱。

/* 在值为 target 的节点后插入 */
void insert_after(Node *head, int target, int val) {
    Node *cur = head->next;
    while (cur && cur->val != target)
        cur = cur->next;
    if (!cur) return;  /* 未找到 */
    Node *n = malloc(sizeof(Node));
    n->val = val;
    n->next = cur->next;
    cur->next = n;
}

细节 3：删除操作的内存释放

删除节点时，必须先保存 next 指针，再 free，最后链接。顺序错误会导致使用已释放内存。

/* 正确顺序：保存 -> 链接 -> 释放 */
void delete_node(Node *head, int target) {
    Node *prev = head, *cur = head->next;
    while (cur && cur->val != target) {
        prev = cur;
        cur = cur->next;
    }
    if (!cur) return;
    prev->next = cur->next;  /* 先链接 */
    free(cur);              /* 再释放 */
}

细节 4：空链表处理

所有操作前都应检查链表是否为空。特别是删除和遍历操作，空链表时直接返回即可。

/* 安全的遍历 */
void print_list(Node *head) {
    if (!head->next) {
        printf("empty\n");
        return;
    }
    for (Node *p = head->next; p; p = p->next)
        printf("%d ", p->val);
    printf("\n");
}

细节 5：边界测试清单

• 空链表插入 — 验证是否为第一个节点
• 空链表删除 — 验证不崩溃
• 单节点链表删除 — 验证正确置空
• 删除头节点 — 验证头指针更新
• 删除尾节点 — 验证前驱 next 为 NULL
• 删除不存在的值 — 验证链表不变

完整可编译源码

#include <stdio.h>
#include <stdlib.h>

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

Node* create_dummy(void) {
    Node *d = malloc(sizeof(Node));
    d->next = NULL;
    return d;
}

void insert_head(Node *d, int val) {
    Node *n = malloc(sizeof(Node));
    n->val = val; n->next = d->next; d->next = n;
}

void free_all(Node *d) {
    Node *p = d, *tmp;
    while (p) { tmp = p->next; free(p); p = tmp; }
}

int main(void) {
    Node *list = create_dummy();
    insert_head(list, 3);
    insert_head(list, 2);
    insert_head(list, 1);
    /* 1 -> 2 -> 3 */
    free_all(list);
    return 0;
}