链表（一）：链表的概念、单向链表的节点定义、链表的创建与遍历

数组用久了，你可能会遇到一个烦心事——它的大小是固定的。我刚开始学C语言那会儿，总觉得数组够用了，直到有一次做项目，需要动态存储用户输入的数据，数量不确定，数组要么开小了不够用，要么开大了浪费内存。这时候，链表就派上用场了。

什么是链表？

链表，说白了就是一种动态的数据结构。它不像数组那样在内存里连续存放，而是通过指针把一个个节点串起来。每个节点里存着数据，还存着下一个节点的地址。

你想想看，数组就像一列固定座位的火车，座位号是连续的。链表呢，就像一群人手拉手站成一排，每个人只知道自己后面是谁。想加人？随时拉一个进来，把手牵上就行。

核心特点：

  • 动态分配内存，不需要预先知道数据总量
  • 插入和删除操作效率高，不需要移动其他元素
  • 访问元素必须从头开始遍历，不支持随机访问

单向链表的节点定义

单向链表是最简单的一种链表。每个节点包含两部分：数据域和指针域。数据域存你要存的东西，指针域指向下一个节点。

我习惯用结构体来定义节点，这样代码清晰又好维护。来看个例子：

// 定义一个学生信息节点
struct Student {
    int id;              // 学号
    char name[20];       // 姓名
    float score;         // 成绩
    struct Student *next; // 指向下一个节点的指针
};

这里有个关键点——next指针的类型是struct Student *，它指向的是同类型的结构体。这就是链表的精髓：自己指向自己这种类型。

小技巧：我建议给结构体起个别名，用typedef，这样写代码时能少敲几个字：

typedef struct Student {
    int id;
    char name[20];
    float score;
    struct Student *next;
} StudentNode;

链表的创建

创建链表，说白了就是一个个地创建节点，然后把它们串起来。我常用的方法是头插法和尾插法。先讲尾插法，因为它更符合直觉——新节点加在末尾。

来看这段代码：

// 创建链表，返回头节点指针
StudentNode* createList(int n) {
    StudentNode *head = NULL;
    StudentNode *tail = NULL;
    
    for (int i = 0; i < n; i++) {
        // 动态分配一个新节点
        StudentNode *newNode = (StudentNode*)malloc(sizeof(StudentNode));
        if (newNode == NULL) {
            printf("内存分配失败！\n");
            return NULL;
        }
        
        // 给节点赋值
        printf("请输入第%d个学生的学号、姓名、成绩：", i + 1);
        scanf("%d %s %f", &newNode->id, newNode->name, &newNode->score);
        newNode->next = NULL;  // 新节点的next先指向NULL
        
        // 如果是第一个节点
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    return head;
}

这段代码里，我用了malloc动态分配内存。嗯，这里要注意——每次malloc之后一定要检查返回值，我曾经因为忘了检查，程序跑着跑着就崩了，查了半天才发现是内存分配失败。

避坑指南：我曾经在项目里犯过一个低级错误——创建节点后忘了把next指针初始化为NULL。结果遍历链表时，最后一个节点的next是个野指针，程序直接段错误。记住：每次创建新节点，一定要把next置为NULL。

链表的遍历

遍历链表，就是从头节点开始，顺着next指针一个个往下走，直到遇到NULL。说白了就是"跟着指针走"。

// 遍历链表，打印所有节点信息
void traverseList(StudentNode *head) {
    StudentNode *current = head;
    int count = 0;
    
    printf("\n===== 学生信息列表 =====\n");
    while (current != NULL) {
        count++;
        printf("第%d个学生：学号=%d, 姓名=%s, 成绩=%.1f\n", 
               count, current->id, current->name, current->score);
        current = current->next;  // 移动到下一个节点
    }
    printf("共%d个学生\n", count);
}

这里有个细节——我用了current指针来遍历，而不是直接用head。为什么？因为如果直接移动head，遍历完链表后，头节点就丢了，再也找不回来了。我刚开始学的时候犯过这个错，后来就养成了用临时指针的习惯。

完整示例：创建并遍历一个学生链表

把上面的代码拼起来，就是一个完整的程序：

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

typedef struct Student {
    int id;
    char name[20];
    float score;
    struct Student *next;
} StudentNode;

// 创建链表
StudentNode* createList(int n) {
    StudentNode *head = NULL, *tail = NULL;
    
    for (int i = 0; i < n; i++) {
        StudentNode *newNode = (StudentNode*)malloc(sizeof(StudentNode));
        if (newNode == NULL) {
            printf("内存分配失败！\n");
            return NULL;
        }
        
        printf("请输入第%d个学生的学号、姓名、成绩：", i + 1);
        scanf("%d %s %f", &newNode->id, newNode->name, &newNode->score);
        newNode->next = NULL;
        
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    
    return head;
}

// 遍历链表
void traverseList(StudentNode *head) {
    StudentNode *current = head;
    int count = 0;
    
    printf("\n===== 学生信息列表 =====\n");
    while (current != NULL) {
        count++;
        printf("第%d个学生：学号=%d, 姓名=%s, 成绩=%.1f\n", 
               count, current->id, current->name, current->score);
        current = current->next;
    }
    printf("共%d个学生\n", count);
}

int main() {
    int n;
    printf("请输入学生人数：");
    scanf("%d", &n);
    
    StudentNode *head = createList(n);
    traverseList(head);
    
    return 0;
}

链表结构示意图

光说可能不太好理解，我画张图给你看看链表长什么样：

头节点 数据域 指针域 (指向下一个) 数据域 指针域 (指向下一个) 数据域 指针域 (指向NULL) NULL 单向链表结构示意图 每个节点包含数据域和指针域，最后一个节点的指针指向NULL

链表 vs 数组：一张表看懂区别

对比项 数组 链表
内存分配 静态分配，大小固定 动态分配，大小可变
内存位置 连续内存 不连续，通过指针连接
访问方式 随机访问，通过下标O(1) 顺序访问，必须遍历O(n)
插入/删除 需要移动元素，效率低 只需修改指针，效率高
额外开销 无 每个节点需要额外存储指针

我的建议：如果你知道数据量大概有多少，而且经常要随机访问，用数组。如果数据量不确定，或者经常要插入删除，用链表。我在做嵌入式项目时，经常用链表来管理动态变化的传感器数据列表，灵活得很。

链表这东西，刚开始接触可能觉得有点绕，尤其是那个指针指来指去的。但只要你动手写几遍，画几张图，慢慢就理解了。记住一句话：链表就是"节点 + 指针"的组合，节点存数据，指针指方向。

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

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