6. 单链表操作：读取、插入、删除与整表管理

单链表，说白了就是一条用指针串起来的数据链。每个节点只管两件事：存自己的数据，记下一个兄弟的地址。我刚开始学链表时，总觉得它不如数组直观——数组多好，下标一敲就定位了。但后来在项目中处理大量动态数据时，我才发现链表的灵活是真的香。

这一章，咱们就把单链表的几个核心操作掰开揉碎讲清楚。你想想看，链表操作无非就是：找节点、插节点、删节点、建链表、清链表。掌握了这五板斧，大部分链表场景你都能应付。

6.1 单链表的读取

读取操作，说白了就是“顺着链子找”。数组用下标直接定位，链表不行——你得从头节点开始，一个一个往后跳。

// 获取单链表中第 i 个元素的值
Status GetElem(LinkList L, int i, ElemType *e) {
    int j = 1;          // 计数器，从1开始
    LinkList p = L->next; // p指向第一个节点
    
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    
    if (!p || j > i) {
        return ERROR;   // 第i个节点不存在
    }
    
    *e = p->data;
    return OK;
}

这里有个细节：头节点不算数据。L->next 才是第一个数据节点。我在项目中见过有人把头节点当第一个数据用，结果遍历时总是多出一个空数据——嗯，这种坑踩过一次就记住了。

6.2 单链表的插入

插入操作，说白了就是“拆链子，接新节点”。你想想看，要在第 i 个位置插一个新节点，你得先找到第 i-1 个节点，然后让新节点指向第 i 个，再让第 i-1 个指向新节点。

// 在单链表第 i 个位置插入新元素 e
Status ListInsert(LinkList L, int i, ElemType e) {
    int j = 0;
    LinkList p = L;      // p指向头节点
    
    while (p && j < i-1) {
        p = p->next;
        ++j;
    }
    
    if (!p || j > i-1) {
        return ERROR;    // 插入位置不合法
    }
    
    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    
    // 核心：先连后断
    s->next = p->next;
    p->next = s;
    
    return OK;
}

我曾经在项目中犯过一个低级错误：先写了 p->next = s，再写 s->next = p->next。结果呢？新节点指向了自己，后面的节点全丢了。调试了半天才发现是顺序搞反了——从那以后，我每次写插入都会默念一遍“先连后断”。

6.3 单链表的删除

删除操作，说白了就是“跳过要删的节点”。找到第 i-1 个节点，让它直接指向第 i+1 个节点，然后释放第 i 个节点的内存。

// 删除单链表第 i 个节点，并用 e 返回其数据
Status ListDelete(LinkList L, int i, ElemType *e) {
    int j = 0;
    LinkList p = L;
    
    while (p->next && j < i-1) {
        p = p->next;
        ++j;
    }
    
    if (!(p->next) || j > i-1) {
        return ERROR;    // 删除位置不合法
    }
    
    LinkList q = p->next;   // q指向要删除的节点
    p->next = q->next;      // 跳过q
    
    *e = q->data;
    free(q);                // 释放内存
    
    return OK;
}

删除操作的时间复杂度也是 O(n)，因为你要先找到第 i-1 个节点。但如果你已经有了目标节点的前驱指针，删除就是 O(1) 的操作——这个特性在后续的循环链表和双向链表中会更有用。

6.4 整表创建

创建链表有两种方式：头插法和尾插法。我个人习惯用尾插法，因为它能保持数据的原始顺序。

头插法

每次新节点都插在头节点后面。说白了就是“后来者居上”——先插入的节点反而在后面。

// 头插法创建单链表
void CreateListHead(LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    for (int i = 0; i < n; i++) {
        LinkList p = (LinkList)malloc(sizeof(Node));
        scanf("%d", &p->data);
        
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

尾插法

每次新节点都加在链表末尾。需要一个尾指针 r 始终指向最后一个节点。

// 尾插法创建单链表
void CreateListTail(LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(Node));
    LinkList r = *L;        // r指向尾节点
    
    for (int i = 0; i < n; i++) {
        LinkList p = (LinkList)malloc(sizeof(Node));
        scanf("%d", &p->data);
        
        r->next = p;        // 尾节点指向新节点
        r = p;              // 更新尾节点
    }
    
    r->next = NULL;         // 尾节点指针置空
}

6.5 整表删除

删除整个链表，说白了就是“一个节点一个节点地释放”。不能直接 free(L) 了事——那样只会释放头节点，后面的节点全成了内存泄漏。

// 删除整个单链表
Status ClearList(LinkList *L) {
    LinkList p = (*L)->next;  // p指向第一个数据节点
    LinkList q;
    
    while (p) {
        q = p->next;    // 先保存下一个节点
        free(p);        // 释放当前节点
        p = q;          // 移动到下一个
    }
    
    (*L)->next = NULL;  // 头节点指针置空
    return OK;
}

6.6 知识体系总览

下面这张图把单链表的核心操作串起来了。你仔细看看，其实所有操作都围绕着“指针的指向变化”展开。

6.7 避坑总结

最后，我把这些年写链表踩过的坑整理一下：

• 指针未初始化：malloc 出来的节点一定要记得赋值 next 指针，否则就是野指针。
• 插入顺序搞反：先连后断，这个我强调过很多次了。
• 删除后未 free：C语言不会自动回收内存，不 free 就是内存泄漏。
• 头节点混淆：头节点不存数据，L->next 才是第一个数据节点。
• 边界条件遗漏：空链表、只有一个节点、操作第一个或最后一个节点——这些边界情况最容易出 bug。

---

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