链表（二）：单向链表的插入与删除操作、链表的反转、双向链表简介

好，咱们接着聊链表。上一章我们把链表的基本概念和创建、遍历讲完了。这一章，我带你手把手把链表的增、删、反转这几个核心操作啃下来。最后再简单看看双向链表——说白了就是给单向链表加了个“倒车镜”。

单向链表的插入操作

插入节点，听起来简单，但坑不少。我当年刚入行时，在一个嵌入式项目里写链表插入，结果因为指针顺序搞反了，导致整个链表断链，调试了一整个下午。嗯，从那以后，我对插入操作的指针顺序就特别敏感。

插入操作分三种情况：

  • 头插法：新节点成为新的头节点
  • 尾插法：新节点追加到链表末尾
  • 中间插入：在指定位置插入新节点

头插法

头插法其实最常用，尤其是在构建链表时。你想想看，每次新来的节点都往头上怼，代码写起来也最简洁。

// 头插法：在链表头部插入新节点
struct Node* insertAtHead(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    newNode->next = head;  // 新节点指向原来的头节点
    return newNode;         // 新节点成为新的头节点
}
我的小技巧：头插法返回新头节点，调用时记得用 head = insertAtHead(head, 42); 这种写法。我见过不少新手直接传 head 进去，结果 head 没更新，链表就丢了。

尾插法

尾插法需要先找到链表末尾。这里有个细节——如果链表为空，尾插法其实就退化成了头插法。

// 尾插法：在链表尾部插入新节点
struct Node* insertAtTail(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    newNode->next = NULL;
    
    // 如果链表为空，新节点就是头节点
    if (head == NULL) {
        return newNode;
    }
    
    // 遍历找到最后一个节点
    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;  // 最后一个节点指向新节点
    return head;
}

中间插入

中间插入稍微麻烦点。你需要找到插入位置的前一个节点，然后调整指针。我个人习惯先画图再写代码，这样不容易出错。

// 在指定位置之后插入新节点（position从0开始）
struct Node* insertAtPosition(struct Node* head, int data, int position) {
    if (position < 0) {
        printf("位置无效\n");
        return head;
    }
    
    // 头插法的情况
    if (position == 0) {
        return insertAtHead(head, data);
    }
    
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return head;
    }
    newNode->data = data;
    
    // 找到位置的前一个节点
    struct Node* temp = head;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    
    if (temp == NULL) {
        printf("位置超出链表范围\n");
        free(newNode);
        return head;
    }
    
    // 关键步骤：先连后断
    newNode->next = temp->next;
    temp->next = newNode;
    
    return head;
}
我曾经踩过的坑：中间插入时，newNode->next = temp->next; 和 temp->next = newNode; 这两句顺序绝对不能反。如果先写 temp->next = newNode，那原来的后续节点就找不到了——链表直接断掉。

单向链表的删除操作

删除操作比插入稍微简单点，但内存释放是个大问题。我见过太多人只删节点不 free，结果内存泄漏到程序崩溃。

删除也分三种：

  • 删除头节点
  • 删除尾节点
  • 删除指定节点

删除头节点

// 删除头节点
struct Node* deleteHead(struct Node* head) {
    if (head == NULL) {
        printf("链表为空，无法删除\n");
        return NULL;
    }
    
    struct Node* temp = head;
    head = head->next;  // 头指针后移
    free(temp);          // 释放原头节点
    return head;
}

删除尾节点

// 删除尾节点
struct Node* deleteTail(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    
    // 只有一个节点的情况
    if (head->next == NULL) {
        free(head);
        return NULL;
    }
    
    // 找到倒数第二个节点
    struct Node* temp = head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    
    free(temp->next);     // 释放最后一个节点
    temp->next = NULL;    // 倒数第二个节点指向NULL
    return head;
}

删除指定值的节点

// 删除第一个匹配指定数据的节点
struct Node* deleteByValue(struct Node* head, int value) {
    if (head == NULL) {
        return NULL;
    }
    
    // 如果要删除的是头节点
    if (head->data == value) {
        return deleteHead(head);
    }
    
    struct Node* temp = head;
    // 找到要删除节点的前一个节点
    while (temp->next != NULL && temp->next->data != value) {
        temp = temp->next;
    }
    
    if (temp->next == NULL) {
        printf("未找到值为 %d 的节点\n", value);
        return head;
    }
    
    struct Node* toDelete = temp->next;
    temp->next = toDelete->next;
    free(toDelete);
    
    return head;
}
核心要点：删除操作一定要记住三步走——找到目标、调整指针、释放内存。少一步都不行。尤其是 free 这一步，嵌入式系统内存本来就紧张，不释放就是给自己挖坑。

链表的反转

链表反转是个经典面试题，也是实际项目中经常用到的操作。我记得有一次做数据包处理，收到的数据顺序是反的，用链表反转一下就搞定了。

反转的核心思路：遍历链表，把每个节点的 next 指针指向前一个节点。需要三个指针：prev、current、next。

// 反转单向链表
struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;   // 保存下一个节点
        current->next = prev;   // 反转指针
        prev = current;         // prev 前移
        current = next;         // current 前移
    }
    
    return prev;  // prev 成为新的头节点
}

为什么会这样？你想想看，如果不先保存 next，current->next 被改成 prev 之后，原来的下一个节点就找不到了。所以 next 这个临时变量是必须的。

我建议：刚开始学反转时，拿几张纸片写上节点编号，在桌上摆一摆，手动模拟指针变化。我当年就是这么干的，比盯着代码看有效十倍。

双向链表简介

单向链表有个硬伤——只能从头往后走，不能回头。双向链表就是来解决这个问题的。每个节点多了一个 prev 指针，指向前一个节点。

双向链表的节点结构：

// 双向链表节点结构
struct DNode {
    int data;
    struct DNode* prev;  // 指向前一个节点
    struct DNode* next;  // 指向后一个节点
};

双向链表的优势很明显：

  • 可以从两个方向遍历，灵活性高
  • 删除操作不需要找前驱节点，直接通过 prev 就能拿到
  • 某些场景下（比如 LRU 缓存）必须用双向链表

但代价也摆在那：每个节点多占一个指针的内存，插入和删除时多维护一个 prev 指针，代码复杂度上去了。

双向链表的插入（以头插为例）：

// 双向链表头插法
struct DNode* dllInsertAtHead(struct DNode* head, int data) {
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    if (newNode == NULL) {
        return head;
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = head;
    
    if (head != NULL) {
        head->prev = newNode;  // 原头节点的 prev 指向新节点
    }
    
    return newNode;
}
注意：双向链表操作时，prev 和 next 两个指针都要更新。我见过有人只改了 next 忘了改 prev，结果遍历时往回走就出问题了。调试这种 bug 特别痛苦，因为正向遍历完全正常，反向遍历就崩。

好了，这一章的内容就到这。链表操作说到底就是指针的舞蹈，多练几次就熟了。下一章我们聊聊循环链表和双向循环链表，到时候你会发现，其实都是套路。

单向链表核心操作知识体系 数据 next 数据 next NULL 三大核心操作 插入操作 头插法 尾插法 中间插入 ⚠ 注意指针顺序 删除操作 删除头节点 删除尾节点 删除指定值 ⚠ 记得 free 内存 反转操作 三指针法 prev / current / next 返回新头节点 ⚠ 先保存 next

链表操作的核心就这些。插入要小心指针顺序，删除别忘了释放内存，反转记住三指针法。双向链表就是多了个 prev 指针，操作时多维护一个方向而已。把这些练熟了，链表这块你就拿下了。

← 上一章 📖 返回目录 下一章 →