19、动态链表：单向链表的创建、插入、删除与销毁

动态链表，说白了就是一条用指针串起来的数据链子。每个节点里存着数据，还存着下一个节点的地址。跟数组不一样，链表不需要一整块连续内存，节点可以散落在内存各处，靠指针互相找到对方。

我刚开始学链表时，总觉得这东西不如数组好用。直到有一次做项目，需要频繁插入删除数据，数组搬来搬去效率太低了。嗯，从那以后我才真正体会到链表的威力。

19.1 链表节点的定义

先定义节点结构体。每个节点包含数据域和指针域：

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域，指向下一个节点
} Node;

这里有个细节：next 的类型是 struct Node *，而不是 Node *。因为在结构体定义还没结束时，Node 这个别名还没生效。我见过不少新手在这里栽跟头。

19.2 创建链表——头插法与尾插法

创建链表有两种常用方式：头插法和尾插法。我个人习惯用尾插法，因为插入顺序跟数据顺序一致，调试时更直观。

头插法

每次新节点都插在头部。新节点的 next 指向原来的头节点，然后更新头指针。

Node *createByHead(int arr[], int n) {
    Node *head = NULL;
    for (int i = 0; i < n; i++) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head;  // 新节点指向旧头
        head = newNode;        // 更新头指针
    }
    return head;
}

头插法有个特点：输入顺序和链表顺序是相反的。比如你输入 1、2、3，链表里存的是 3、2、1。为什么？你想想看，每次新节点都跑到最前面去了。

尾插法

尾插法需要维护一个尾指针，每次新节点加在末尾。

Node *createByTail(int arr[], int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        
        if (head == NULL) {
            head = newNode;   // 第一个节点
            tail = newNode;
        } else {
            tail->next = newNode;  // 尾节点指向新节点
            tail = newNode;        // 更新尾指针
        }
    }
    return head;
}

19.3 插入节点

插入节点分三种情况：头部插入、中间插入、尾部插入。核心操作就是改指针。

// 在指定位置 pos（从0开始）插入值为 val 的节点
Node *insertNode(Node *head, int pos, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    
    if (pos == 0) {  // 头部插入
        newNode->next = head;
        return newNode;
    }
    
    Node *prev = head;
    for (int i = 0; i < pos - 1 && prev != NULL; i++) {
        prev = prev->next;
    }
    
    if (prev == NULL) {
        printf("位置无效\n");
        free(newNode);
        return head;
    }
    
    newNode->next = prev->next;
    prev->next = newNode;
    return head;
}

19.4 删除节点

删除节点同样分三种情况。核心是找到要删除节点的前驱节点，然后绕过它。

Node *deleteNode(Node *head, int val) {
    if (head == NULL) return NULL;
    
    // 删除头节点
    if (head->data == val) {
        Node *temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    Node *prev = head;
    Node *curr = head->next;
    
    while (curr != NULL && curr->data != val) {
        prev = curr;
        curr = curr->next;
    }
    
    if (curr != NULL) {
        prev->next = curr->next;
        free(curr);
    }
    
    return head;
}

删除操作最容易被忽略的是内存释放。只改指针不 free，就会造成内存泄漏。我曾经在一个嵌入式项目里，因为频繁删除节点没释放内存，跑了三天后系统直接崩溃了。

19.5 销毁链表

销毁链表要逐个释放每个节点。不能只释放头节点，否则其他节点就变成孤儿了。

void destroyList(Node *head) {
    Node *curr = head;
    while (curr != NULL) {
        Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
}

这里有个关键点：一定要先用临时变量保存当前节点，再移动指针，最后释放。顺序错了，你就找不到下一个节点了。

19.6 链表操作的核心逻辑

我把链表的核心操作总结成一张图，方便你理解：

19.7 完整示例

把上面所有操作串起来，写一个完整的测试程序：

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

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

void printList(Node *head) {
    Node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // 创建链表
    Node *head = createByTail(arr, n);
    printf("初始链表: ");
    printList(head);
    
    // 插入节点
    head = insertNode(head, 2, 25);
    printf("插入25后: ");
    printList(head);
    
    // 删除节点
    head = deleteNode(head, 40);
    printf("删除40后: ");
    printList(head);
    
    // 销毁链表
    destroyList(head);
    printf("链表已销毁\n");
    
    return 0;
}

运行结果：

初始链表: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
插入25后: 10 -> 20 -> 25 -> 30 -> 40 -> 50 -> NULL
删除40后: 10 -> 20 -> 25 -> 30 -> 50 -> NULL
链表已销毁

嗯，链表这块内容就这些。说白了就是画图、写代码、调试。我建议你动手写一遍，把每个操作都跑通。光看代码是学不会的，指针这东西，得亲手调过才知道坑在哪。

---

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