【C语言-算法-链表】5. 进阶的数据结构基础——链表（指针的终极试炼）

前面咱们聊了数组、排序、字符串，这些都是C语言里的"基础款"。但说句实在话，这些内容学完之后，你对C语言的理解可能还停留在"用数组存数据、用循环处理数据"这个层面。真正让你对指针"开窍"的，是链表。

为啥这么说？因为链表强迫你真正理解"地址"这两个字是什么意思。数组是连续的内存块，你通过下标来访问，本质上是在做"基地址+偏移量"的运算。但链表不一样，它的每个节点都是独立分配的，散落在内存的各个角落，靠指针把它们串起来。你操作链表的时候，每一步都在跟地址打交道。

很多同学学到链表就开始懵了——struct Node *next是个什么东西？p = p->next到底指向了哪里？malloc出来的内存怎么释放？别急，今天咱们从头到尾捋一遍，从最基础的定义开始，把链表的创建、遍历、插入、删除挨个拆一遍。你跟着代码一步一步走，把每一行执行完内存里发生了什么想清楚，链表这关就过了。

一、先搞清楚一个问题：为啥要用链表？

在讲链表之前，你得先明白数组有啥毛病。

数组的优点是：连续存储、随机访问快（通过下标O(1)就能找到）。但它的缺点也很要命：

大小固定。你定义了int a[100]，就只能放100个数。如果来了第101个，放不下。
插入和删除效率低。在数组中间插入一个元素，后面的所有元素都得往后挪；删除一个元素，后面的所有元素都得往前挪。数据量大的时候，这个开销很吓人。

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

大小不固定。需要多少就申请多少，随时可以增加或减少节点。
插入和删除只需要改指针，不用挪动数据。
代价是访问慢。想找第10个节点？得从头开始一个一个往后数，不能像数组那样直接下标定位。

所以数组和链表各有各的适用场景，没有谁比谁绝对好。

链表在内存里长啥样？想象一下：你有一堆小纸片（节点），每张纸片上写着数据，还有一行写着"下一张纸片放在哪里"（指针）。这些纸片不需要放在一起，你只要知道第一张纸片在哪儿，就能顺着"下一张在哪儿"的指引，一张一张找到所有纸片。

二、链表的节点长啥样？——结构体套指针

C语言里实现链表，靠的是结构体，结构体里有一个成员是指向同类型结构体的指针。

定义方式：

struct Node {
    int data;           // 存数据，这里以整数为例
    struct Node *next;  // 指向下一个节点的指针
};

struct Node *next这行是关键。它在说：我这个节点里存了一个地址，这个地址指向的是另一个struct Node类型的变量。这样就把节点和节点串起来了。

为了方便，通常用typedef给它起个别名，省得每次写struct Node那么长：

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

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

三、创建一个节点——malloc是你的好兄弟

链表的节点是在程序运行的时候动态创建的，用的是malloc函数。malloc从堆上申请一块内存，返回这块内存的起始地址。

#include <stdio.h>
#include <stdlib.h>   // malloc和free都在这个头文件里

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

// 创建一个新节点
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(sizeof(Node))：申请一块刚好能放一个Node结构体的内存，单位是字节。
(Node*)是强制类型转换，把malloc返回的void*转成Node*，这样赋值给newNode的时候类型匹配。
if (newNode == NULL)：检查内存分配是否成功。如果内存不够，malloc会返回NULL。虽然现在电脑内存都大，写作业很难碰上失败，但养成检查的习惯是专业程序员的基本素养。
newNode->data = value;：用->运算符访问结构体指针的成员。相当于(*newNode).data = value;，但->更简洁。
newNode->next = NULL;：新节点的next先设为NULL，表示这个节点后面还没接东西。

四、链表的两种创建方式：头插法和尾插法

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

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

思路：新节点的next指向当前的头节点，然后头指针指向新节点。

Node* create_by_head_insert() {
    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，next指向NULL（因为head此时是NULL），head指向节点3。链表：3
输入5：创建节点5，next指向head（也就是节点3），head指向节点5。链表：5 -> 3
输入2：创建节点2，next指向head（节点5），head指向节点2。链表：2 -> 5 -> 3

头插法的特点：你输入的顺序是3、5、2，输出的顺序是2、5、3，正好反过来。头插法简单，但如果你想要输入顺序和输出顺序一致，就得用尾插法。

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

思路：如果链表为空，新节点就是头。如果链表不为空，先找到最后一个节点（next为NULL的那个），把它的next指向新节点。

Node* create_by_tail_insert() {
    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
输入5：head不为空，tail->next = 节点5，tail指向节点5。链表：3 -> 5
输入2：tail->next = 节点2，tail指向节点2。链表：3 -> 5 -> 2

尾插法的特点：输入顺序和输出顺序一致。多了一个tail指针，省去了每次插入都要从头遍历找尾巴的麻烦。

你现在写作业或者考试，建议用尾插法，因为保持输入顺序更符合直觉。但你一定要知道头插法，因为有些场景（比如栈）就是从头插的，用的就是头插法的思路。

五、遍历链表——把每个节点走一遍

有了链表，怎么把里面的数据全打出来？从头节点开始，沿着next指针一个一个往后走，直到走到NULL。

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

这步特别重要，你要在脑子里把这个过程走通：

p指向head（第一个节点），打印它的data，然后p移动到p->next（第二个节点）。
打印第二个节点的data，p移动到第三个。
一直走，直到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;   // 没找到
}

返回的是节点的指针。调用的时候，如果返回值是NULL，说明没找到；如果不是NULL，你就拿到了那个节点，想对它干啥都行。

七、插入节点——这才是链表的优势

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

在链表头部插入：这个最简单，头插法就是干这个的。

Node* insert_at_head(Node *head, int value) {
    Node *newNode = create_node(value);
    newNode->next = head;
    head = newNode;
    return head;   // 新的头指针
}

在链表尾部插入：如果有一个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个位置插入一个新节点（从0开始数）。

思路：找到第pos-1个节点（也就是插入位置的前一个），让新节点的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;
}

删除指定值的节点：删除第一个data等于target的节点。

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->next赋值给p），再释放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：插入的时候顺序写反了

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

最后说两句：

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

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

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

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