【C语言-指针-链表】7. 链表——动态内存和指针的终极结合

前面咱们把指针、动态内存分配都啃完了。今天这节课，是把前面所有知识全部串起来的终极实战——链表。

说实话，链表这东西，你第一次听可能觉得“不就是个数据结构吗”。但你真正写起来才会发现，链表逼着你把指针的每一个细节都想清楚。指针怎么指？内存怎么分配？节点怎么串？删掉一个节点怎么不断链？这些问题全得考虑。

但反过来，你要是把链表彻底搞明白了，你对指针的理解就上了一个大台阶。以后再看什么二叉树、图、哈希表，都是从这个基础上长出来的。

先说说数组有啥毛病

咱们前面学数组的时候，你肯定有过这种体验：定义一个int a[100]，结果来了150个数，装不下了。或者你只用了10个位置，剩下90个全浪费了。

数组的毛病总结起来就三条：

第一，大小固定。定义了100个，就只能装100个。多了装不下，少了浪费空间。

第二，插入删除麻烦。你要在数组中间插一个数，后面的全部得往后挪一位。删一个数，后面的全部得往前挪一位。数据量大的时候，这个挪动的开销很吓人。

第三，内存必须连续。数组申请内存的时候，系统必须给你找一块连续的空间。内存碎片多了之后，你可能明明有足够的总空间，但就是找不到一块连续的大空间，数组就申请不了。

链表就是来解决这些问题的。

链表长啥样？你就想象一排小盒子，每个盒子里装着数据，还装着一根“线”，这根线告诉你下一个盒子在哪儿。这些盒子不需要挨在一起，可以散落在内存的各个角落，只要那根“线”能把它们串起来就行。

你只要知道第一个盒子在哪儿，就能顺着线找到第二个、第三个、第四个……直到最后一个盒子，它的线是空的，表示“后面没有了”。

链表节点怎么定义？

在C语言里，每个盒子就是一个结构体。结构体里有两个成员：一个存数据，一个存指针（那根线）。

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

这行代码的意思：Node这个结构体里，有一个int数据，还有一个指针，这个指针指向的是另一个Node。

注意这里有个很有意思的地方：结构体里面引用自己。这在C语言里是允许的，因为指针的大小是固定的（8字节），编译器知道给next分配多大空间。

为了写起来方便，一般用typedef给它起个别名：

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

这样后面你就能直接写Node *p，不用写struct Node *p了。

创建一个节点

链表的节点不是预先定义好的，而是程序运行的时候动态创建的。用的就是咱们上节课学的malloc。

Node* create_node(int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = value;   // 存数据
    newNode->next = NULL;    // 新节点的next先指向空
    return newNode;
}

你看，这里用到了malloc、指针、结构体、->运算符——前面学的东西全用上了。

malloc(sizeof(Node))申请一块刚好能放一个Node的内存。newNode->data = value把数据存进去。newNode->next = NULL表示这个节点后面暂时还没接东西。

构建链表：两种方式

有了创建节点的函数，现在要把它们串起来。串的方式有两种：头插法和尾插法。

头插法：新节点插在最前面

想象你手里有一摞牌，每来一张新牌，你就把它放到最上面。

Node* create_by_head() {
    Node *head = NULL;   // 一开始链表是空的
    int value;

    printf("输入数字（-1结束）：\n");
    scanf("%d", &value);

    while (value != -1) {
        Node *newNode = create_node(value);
        newNode->next = head;   // 新节点指向原来的头
        head = newNode;         // 头指针更新为新节点
        scanf("%d", &value);
    }
    return head;
}

追踪一下执行过程：

输入3：创建节点3，newNode->next = head（此时head是NULL），head = newNode。链表：3 -> NULL
输入5：创建节点5，newNode->next = head（指向节点3），head = newNode。链表：5 -> 3 -> NULL
输入2：创建节点2，newNode->next = head（指向节点5），head = newNode。链表：2 -> 5 -> 3 -> NULL

你看，你输入的顺序是3、5、2，输出的顺序是2、5、3，正好反过来了。这就是头插法的特点。

尾插法：新节点接在最后面

这个更符合咱们的直觉——先来的排前面，后来的排后面。但要多一个指针记录“尾巴”在哪儿，不然每次插新节点都得从头遍历找尾巴，效率太低。

Node* create_by_tail() {
    Node *head = NULL;
    Node *tail = NULL;   // 记录尾巴
    int value;

    printf("输入数字（-1结束）：\n");
    scanf("%d", &value);

    while (value != -1) {
        Node *newNode = create_node(value);
        if (head == NULL) {
            // 第一个节点，既是头也是尾
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;   // 接到尾巴后面
            tail = newNode;         // 更新尾巴
        }
        scanf("%d", &value);
    }
    return head;
}

追踪一下：

输入3：head==NULL，head指向节点3，tail指向节点3。链表：3 -> NULL
输入5：head不为空，tail->next = 节点5，tail = 节点5。链表：3 -> 5 -> NULL
输入2：tail->next = 节点2，tail = 节点2。链表：3 -> 5 -> 2 -> NULL

输入顺序和输出顺序一致。

建议你用尾插法，因为保持顺序更符合直觉。但你得知道头插法，因为有些场景就是需要反序的。

遍历链表

创建完了，怎么把里面的数据打出来？从头节点开始，沿着next一路走到底。

void print_list(Node *head) {
    Node *p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;   // 走到下一个
    }
    printf("NULL\n");
}

这个循环的精髓：p一开始指向head，打印当前节点的数据，然后p = p->next走到下一个，直到p变成NULL（走到链表末尾了）退出。

你可以在脑子里过一遍：p指向第一个节点，打印它的data，p移动到第二个节点，打印，再移动……直到最后一个节点的next是NULL，p变成NULL，循环退出。

查找某个值

遍历的时候加上判断就行：

Node* find_node(Node *head, int target) {
    Node *p = head;
    while (p != NULL) {
        if (p->data == target) {
            return p;   // 找到了，返回这个节点的地址
        }
        p = p->next;
    }
    return NULL;   // 没找到
}

返回的是节点的指针。调用者拿到这个指针，可以读数据，也可以改数据。

插入节点

这才是链表真正比数组强的地方——插入不需要挪动数据，只需要改几个指针。

在头部插入最简单：

Node* insert_at_head(Node *head, int value) {
    Node *newNode = create_node(value);
    newNode->next = head;
    return newNode;   // 新节点成为新的头
}

在尾部插入，如果有tail指针就O(1)搞定。没有的话得先走到尾巴：

Node* insert_at_tail(Node *head, int value) {
    Node *newNode = create_node(value);
    if (head == NULL) {
        return newNode;
    }
    Node *p = head;
    while (p->next != NULL) {   // 找到最后一个节点
        p = p->next;
    }
    p->next = newNode;
    return head;
}

在指定位置插入，比如在第pos个位置后面插入。思路：找到第pos个节点，让新节点的next指向它的next，再让它的next指向新节点。

Node* insert_at_pos(Node *head, int pos, int value) {
    if (pos == 0) {
        return insert_at_head(head, value);
    }
    Node *newNode = create_node(value);
    Node *p = head;
    int i = 0;

    // 找到第pos-1个节点（插入位置的前一个）
    while (i < pos - 1 && p != NULL) {
        p = p->next;
        i++;
    }

    if (p == NULL) {
        printf("位置无效\n");
        free(newNode);
        return head;
    }

    // 关键两步：先连后面，再连前面
    newNode->next = p->next;
    p->next = newNode;

    return head;
}

注意那两步的顺序：

先执行newNode->next = p->next;，让新节点指向后一个节点。

再执行p->next = newNode;，让前一个节点指向新节点。

如果你把顺序写反了——先p->next = newNode;，然后再newNode->next = p->next;，这时候p->next已经被改成新节点了，新节点的next指向自己，整个链表后面就丢了。这个顺序是个经典坑，每次写插入都要在脑子里过一遍。

删除节点

删除某个节点，思路：找到要删的节点的前一个节点，让它直接指向要删节点的下一个，跳过要删的那个，然后释放掉要删的节点。

删除头部节点：

Node* delete_at_head(Node *head) {
    if (head == NULL) return NULL;
    Node *temp = head;
    head = head->next;
    free(temp);
    return head;
}

删除指定值的节点：

Node* delete_by_value(Node *head, int target) {
    if (head == NULL) return NULL;

    // 如果要删的是头节点
    if (head->data == target) {
        return delete_at_head(head);
    }

    Node *p = head;
    // 找到目标节点的前一个节点
    while (p->next != NULL && p->next->data != target) {
        p = p->next;
    }

    if (p->next == NULL) {
        printf("没找到\n");
        return head;
    }

    Node *toDelete = p->next;    // 要删的节点
    p->next = toDelete->next;    // 跳过它
    free(toDelete);              // 释放内存

    return head;
}

注意：找到的是前一个节点，不是要删的那个。 画个图：A -> B -> C，你想删B。你找到A，让A->next直接从B变成C，然后把B free掉。如果你只有B的指针，你就不知道A在哪儿，没法改A的next。所以删除操作的核心是“找到前驱节点”。

释放整个链表

动态申请的内存，用完一定要释放。链表用完不释放，就会造成内存泄漏。

void free_list(Node *head) {
    Node *p = head;
    while (p != NULL) {
        Node *temp = p;    // 记住当前节点
        p = p->next;       // 先走到下一个
        free(temp);        // 再释放当前
    }
}

顺序很重要：先存下p->next，再释放p。如果你先free(p)，然后p = p->next，你访问的是一块已经释放的内存，这叫“野指针访问”，程序会崩溃。

一个完整的例子：学生信息链表

把所有东西串起来，写一个完整的例子。需求：用链表存学生学号，能添加、删除、查找、打印。

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

typedef struct Student {
    int id;
    struct Student *next;
} Student;

// 创建节点
Student* create_student(int id) {
    Student *new = (Student*)malloc(sizeof(Student));
    if (new == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    new->id = id;
    new->next = NULL;
    return new;
}

// 尾插添加
Student* add_student(Student *head, int id) {
    Student *new = create_student(id);
    if (head == NULL) {
        return new;
    }
    Student *p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new;
    return head;
}

// 按学号查找
Student* find_student(Student *head, int id) {
    Student *p = head;
    while (p != NULL) {
        if (p->id == id) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

// 按学号删除
Student* delete_student(Student *head, int id) {
    if (head == NULL) return NULL;
    if (head->id == id) {
        Student *temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    Student *p = head;
    while (p->next != NULL && p->next->id != id) {
        p = p->next;
    }
    if (p->next == NULL) {
        printf("学号%d不存在\n", id);
        return head;
    }
    Student *temp = p->next;
    p->next = temp->next;
    free(temp);
    return head;
}

// 打印所有
void print_students(Student *head) {
    if (head == NULL) {
        printf("链表为空\n");
        return;
    }
    Student *p = head;
    while (p != NULL) {
        printf("%d ", p->id);
        p = p->next;
    }
    printf("\n");
}

// 释放链表
void free_all(Student *head) {
    Student *p = head;
    while (p != NULL) {
        Student *temp = p;
        p = p->next;
        free(temp);
    }
}

int main() {
    Student *head = NULL;

    head = add_student(head, 101);
    head = add_student(head, 102);
    head = add_student(head, 103);
    head = add_student(head, 104);
    printf("当前学生：");
    print_students(head);   // 101 102 103 104

    head = delete_student(head, 102);
    printf("删除102后：");
    print_students(head);   // 101 103 104

    Student *found = find_student(head, 103);
    if (found != NULL) {
        printf("找到了学号%d\n", found->id);
    }

    free_all(head);
    return 0;
}

这个例子虽然简单，但把链表的核心操作——创建、添加、查找、删除、遍历、释放——全过了一遍。你把它敲一遍，跑起来，然后改一改加点功能，链表你就真正上手了。

几个必踩的坑

坑1：malloc之后忘记free

程序跑完的时候操作系统会回收内存，所以写小作业的时候感觉不到问题。但如果你写的是长期运行的程序，每创建一个节点都不释放，内存会一点点被吃光，最后程序崩溃。养成习惯，用完就free。

坑2：删除节点的时候把链表弄断了

删除的时候，如果你没有先保存要删节点的next，而是直接把p->next改了，那后面的节点就丢了，内存也泄露了。正确的顺序是：先存要删的节点，再改指针，最后free。

坑3：对空指针解引用

p->next的前提是p不是NULL。如果你没检查就直接用p->next，而p是NULL，程序瞬间崩溃。每次访问指针成员之前，脑子里过一下：这个指针有没有可能是NULL？

坑4：插入的时候顺序写反了

前面说了，插入的时候必须先连后面再连前面。顺序反了链表就断了。这个错误很难发现，因为编译能过，运行可能也不崩，但遍历链表的时候发现少了数据。每次写插入都把顺序默念一遍：“先连后，再连前”。

坑5：free之后没有置NULL

free(p);
// p现在是个悬空指针，还存着已经释放的地址
p = NULL;   // 好习惯：置空

最后说两句

链表是C语言指针知识的大汇总。你学完链表，再看int *p、&取地址、*解引用这些东西，感觉就不一样了——因为你真正用它们做过事了。

练到什么程度算过关？ 不看书、不查资料，能独立写出链表的创建、遍历、插入（头尾和指定位置）、删除（头和指定值）、释放。并且每写一行代码都知道它改变的是内存里的什么东西，执行完指针指向了哪里。做到这一步，链表的精髓你就掌握了。

还是那句话，别光看。链表必须手敲，必须画图。每写一个操作，把链表的结构画在纸上，用箭头标出每个节点的next指向哪儿，然后把代码一步步走一遍，看指针的变化跟你的图是不是一致。这个过程做一遍，顶你看十遍教材。

去吧，打开编译器，先把那个学生管理的例子敲一遍，然后在它上面加功能——比如按学号修改数据、按位置插入、统计链表长度。改着改着，链表就是你的了。