15.8【保姆级教程】C语言链式结构（链表）：从0到1吃透单链表/双向链表，手写完整实战案例
🔥 关注博主不迷路！纯干货+可视化图解+完整可运行代码 | 解决数组痛点，掌握队列/二叉树的核心基础
在C语言中，链式结构（链表） 是突破数组“固定长度、插入删除低效”痛点的核心数据结构，也是实现队列、栈、二叉树、哈希表等高级数据结构的基础。不同于数组的连续内存布局，链式结构通过“指针”将分散的内存节点串联起来，实现数据的动态增删，是C语言进阶必须吃透的核心知识点。
本文将从“链式结构的核心认知”到“单链表完整实现”，再到“双向链表进阶”和“实战案例”，手把手拆解每一行代码、每一个逻辑，即使是零基础新手，也能轻松掌握链式结构的所有核心用法！
一、链式结构核心认知：为什么需要它？
1.1 数组的痛点（链式结构的诞生背景）
在学习链表前，先明确“为什么不用数组”——数组的三大致命缺陷：
| 数组的痛点 | 具体问题 |
|---|---|
| 长度固定 | 声明时必须指定长度（如int arr[10]），满了无法扩容，空着浪费内存 |
| 插入/删除效率低 | 插入元素需移动后续所有元素（如在数组头部插元素，需移动n个元素） |
| 内存连续分配 | 大数组可能因连续内存不足分配失败（如int arr[1000000]可能栈溢出） |
1.2 链式结构的定义
链式结构（以最基础的单链表为例）由若干个节点（Node） 组成，每个节点包含两部分：
- 数据域：存储实际业务数据（如员工姓名、年龄、薪资）；
- 指针域：存储下一个节点的内存地址（核心：通过指针串联节点）。
1.3 单链表的可视化图解
头节点(head) → 节点1（数据：张三，指针→节点2） → 节点2（数据：李四，指针→NULL） → NULL - 头节点（head）：指向链表第一个有效节点的指针（链表的“入口”）；
- 尾节点：最后一个节点的指针域为
NULL（表示链表结束）； - 空链表：
head = NULL。
1.4 链式结构 vs 数组（核心对比）
| 特性 | 链式结构（单链表） | 数组 |
|---|---|---|
| 内存布局 | 非连续，分散在堆内存 | 连续内存（栈/全局） |
| 长度 | 动态扩容/缩容，无需预设长度 | 固定长度，声明后不可修改 |
| 插入/删除 | 仅修改指针，效率O(1)（指定位置） | 需移动元素，效率O(n) |
| 随机访问 | 需遍历，效率O(n) | 下标直接访问，效率O(1) |
| 内存利用率 | 按需分配，无浪费 | 可能浪费（声明长度>实际使用） |
| 实现复杂度 | 较高（需处理指针/内存） | 简单（下标操作） |
核心结论：需要频繁增删、长度不确定 选链表；需要频繁随机访问、长度固定 选数组。
二、单链表：链式结构的基础（手写完整实现）
2.1 第一步：定义链表节点结构体
单链表的核心是“节点结构体”——包含数据域和指针域（指向同类型节点）：
#include<stdio.h>#include<stdlib.h>#include<string.h>// 定义单链表节点结构体（以学生信息为例）#defineMAX_NAME20#defineMAX_ID10structstudent_node{// 数据域：存储学生信息（字段）char name[MAX_NAME];char id[MAX_ID];int age;float score;// 指针域：指向链表中下一个节点（核心！）structstudent_node*next;};struct student_node *next：指针域的类型必须和节点结构体一致，才能指向“下一个同类型节点”；- 数据域可根据业务需求定义（如员工、商品信息），指针域是链表的“灵魂”。
2.2 第二步：基础操作函数声明（先明确功能）
// 1. 创建单个节点（动态分配内存）structstudent_node*create_node(constchar*name,constchar*id,int age,float score);// 2. 尾插法：将节点添加到链表末尾intinsert_node_tail(structstudent_node**p_head,structstudent_node*new_node);// 3. 头插法：将节点添加到链表头部（效率最高）intinsert_node_head(structstudent_node**p_head,structstudent_node*new_node);// 4. 遍历链表：打印所有节点数据voidtraverse_list(structstudent_node*head);// 5. 查找节点：按学号查找，返回节点指针structstudent_node*find_node_by_id(structstudent_node*head,constchar*id);// 6. 删除节点：按学号删除指定节点intdelete_node_by_id(structstudent_node**p_head,constchar*id);// 7. 释放链表：释放所有节点的内存（避免泄漏）voidfree_list(structstudent_node**p_head);2.3 第三步：实现核心操作（逐函数拆解）
2.3.1 创建单个节点（动态分配堆内存）
structstudent_node*create_node(constchar*name,constchar*id,int age,float score){// 1. 分配节点内存（堆内存，需手动释放）structstudent_node*new_node =(structstudent_node*)malloc(sizeof(structstudent_node));if(new_node ==NULL){// 必做：检查内存分配是否成功perror("malloc failed");returnNULL;}// 2. 初始化数据域（字符数组用strncpy，避免越界）strncpy(new_node->name, name, MAX_NAME-1); new_node->name[MAX_NAME-1]='\0';// 确保字符串结束符strncpy(new_node->id, id, MAX_ID-1); new_node->id[MAX_ID-1]='\0'; new_node->age = age; new_node->score = score;// 3. 初始化指针域：新节点默认指向NULL（后续插入时调整） new_node->next =NULL;return new_node;}关键解析：
- 节点必须用
malloc分配堆内存（栈内存会随函数结束销毁，无法串联）； - 指针域初始化为
NULL，避免野指针。
2.3.2 尾插法：添加节点到链表末尾
intinsert_node_tail(structstudent_node**p_head,structstudent_node*new_node){// 入参检查：节点为空/头指针地址为空if(new_node ==NULL|| p_head ==NULL){printf("入参错误！\n");return-1;}// 情况1：链表为空（头节点为NULL），新节点作为第一个节点if(*p_head ==NULL){*p_head = new_node;return0;}// 情况2：链表非空，找到尾节点（next=NULL的节点）structstudent_node*p =*p_head;// 遍历指针，从头节点开始while(p->next !=NULL){// 未到尾节点则继续 p = p->next;}// 尾节点的next指向新节点 p->next = new_node;return0;}关键解析：
- 头指针用
**p_head（二级指针）：因为需要修改头节点本身（链表为空时）； - 遍历找尾节点：从
*p_head开始，直到p->next == NULL。
2.3.3 头插法：添加节点到链表头部
intinsert_node_head(structstudent_node**p_head,structstudent_node*new_node){if(new_node ==NULL|| p_head ==NULL){printf("入参错误！\n");return-1;}// 1. 新节点的next指向原头节点 new_node->next =*p_head;// 2. 头节点更新为新节点*p_head = new_node;return0;}关键解析：
- 头插法无需遍历，直接修改指针，效率远高于尾插；
- 步骤不可颠倒：先让新节点指向原头，再更新头节点。
2.3.4 遍历链表：打印所有节点
voidtraverse_list(structstudent_node*head){// 链表为空if(head ==NULL){printf("链表为空！\n");return;}// 遍历指针，从头节点开始structstudent_node*p = head;int cnt =0;// 节点计数while(p !=NULL){ cnt++;printf("第%d个节点：姓名=%s | 学号=%s | 年龄=%d | 成绩=%.1f\n", cnt, p->name, p->id, p->age, p->score); p = p->next;// 移动到下一个节点}}关键解析：
- 遍历终止条件：
p == NULL（到链表末尾）； - 遍历指针
p仅用于访问，不修改原链表。
2.3.5 按学号查找节点
structstudent_node*find_node_by_id(structstudent_node*head,constchar*id){if(head ==NULL|| id ==NULL){returnNULL;}structstudent_node*p = head;while(p !=NULL){if(strcmp(p->id, id)==0){// 学号匹配return p;// 找到则返回节点指针} p = p->next;}returnNULL;// 未找到}关键解析：
- 字符串比较必须用
strcmp，不能用==； - 找到节点后返回指针，可直接修改该节点数据。
2.3.6 按学号删除节点
intdelete_node_by_id(structstudent_node**p_head,constchar*id){if(p_head ==NULL|| id ==NULL||*p_head ==NULL){printf("入参错误或链表为空！\n");return-1;}structstudent_node*p =*p_head;// 遍历指针structstudent_node*prev =NULL;// 记录前驱节点（删除需要前驱指针）// 步骤1：找到要删除的节点while(p !=NULL&&strcmp(p->id, id)!=0){ prev = p;// 保存当前节点为前驱 p = p->next;// 移动到下一个节点}// 步骤2：未找到节点if(p ==NULL){printf("未找到学号为%s的节点！\n", id);return-1;}// 步骤3：删除节点（分两种情况）// 情况1：删除头节点（前驱为NULL）if(prev ==NULL){*p_head = p->next;// 头节点指向原头节点的下一个节点}else{// 情况2：删除中间/尾节点，前驱节点的next指向当前节点的下一个节点 prev->next = p->next;}// 步骤4：释放被删除节点的内存（必做！）free(p); p =NULL;// 置空，避免野指针printf("成功删除学号为%s的节点！\n", id);return0;}关键解析：
- 删除节点的核心：找到“前驱节点”，让前驱的
next跳过被删节点； - 必须释放被删节点的内存，否则内存泄漏；
- 头节点删除需特殊处理（修改
*p_head）。
2.3.7 释放整个链表
voidfree_list(structstudent_node**p_head){if(p_head ==NULL||*p_head ==NULL){return;}structstudent_node*p =*p_head;// 当前节点structstudent_node*temp =NULL;// 临时保存下一个节点while(p !=NULL){ temp = p->next;// 先保存下一个节点地址（避免释放后找不到）free(p);// 释放当前节点 p = temp;// 移动到下一个节点}// 头节点置空，避免野指针*p_head =NULL;printf("链表已全部释放！\n");}关键解析：
- 必须先保存下一个节点地址，再释放当前节点（否则释放后
p->next无效）； - 最后将头节点置空，避免后续误操作野指针。
2.4 单链表完整测试代码（可直接运行）
intmain(void){// 初始化头节点：空链表structstudent_node*head =NULL;// 1. 创建节点并尾插structstudent_node*node1 =create_node("张三","2024001",18,92.5);structstudent_node*node2 =create_node("李四","2024002",19,88.0);insert_node_tail(&head, node1);insert_node_tail(&head, node2);// 2. 头插节点structstudent_node*node3 =create_node("王五","2024003",20,95.0);insert_node_head(&head, node3);// 3. 遍历链表printf("===== 初始链表 =====\n");traverse_list(head);// 4. 查找节点structstudent_node*find_node =find_node_by_id(head,"2024002");if(find_node !=NULL){printf("\n===== 查找结果 =====\n");printf("找到节点：姓名=%s | 学号=%s | 成绩=%.1f\n", find_node->name, find_node->id, find_node->score);// 直接修改找到的节点数据 find_node->score =90.0;printf("修改后成绩：%.1f\n", find_node->score);}// 5. 删除节点printf("\n===== 删除节点 =====\n");delete_node_by_id(&head,"2024002");traverse_list(head);// 6. 释放链表printf("\n===== 释放链表 =====\n");free_list(&head);traverse_list(head);// 验证链表为空return0;}三、链式结构进阶：双向链表（解决单链表反向遍历痛点）
单链表的痛点：只能从前往后遍历，无法反向查找；删除节点时需要找前驱节点（遍历效率低）。
双向链表：每个节点新增“前驱指针”，指向前一个节点，支持双向遍历/删除。
3.1 双向链表节点定义
// 双向链表节点结构体structstudent_dnode{// 数据域char name[MAX_NAME];char id[MAX_ID];int age;float score;// 指针域：前驱+后继structstudent_dnode*prev;// 指向前一个节点structstudent_dnode*next;// 指向后一个节点};3.2 双向链表核心操作（尾插示例）
// 双向链表尾插法intinsert_dnode_tail(structstudent_dnode**p_head,structstudent_dnode*new_node){if(new_node ==NULL|| p_head ==NULL){return-1;} new_node->prev =NULL; new_node->next =NULL;// 空链表if(*p_head ==NULL){*p_head = new_node;return0;}// 找尾节点structstudent_dnode*p =*p_head;while(p->next !=NULL){ p = p->next;}// 双向链接：尾节点<->新节点 p->next = new_node; new_node->prev = p;return0;}关键解析：双向链表插入时需同时维护prev和next指针，确保“双向链接”。
3.3 双向链表反向遍历
// 反向遍历双向链表（从尾到首）voidtraverse_dlist_reverse(structstudent_dnode*head){if(head ==NULL){printf("双向链表为空！\n");return;}// 先找到尾节点structstudent_dnode*p = head;while(p->next !=NULL){ p = p->next;}// 反向遍历int cnt =0;while(p !=NULL){ cnt++;printf("反向第%d个节点：姓名=%s | 学号=%s\n", cnt, p->name, p->id); p = p->prev;// 前驱指针，向前移动}}四、链式结构实战案例：简易通讯录（基于单链表）
结合“链表操作+文件持久化”，实现一个可新增、查询、删除、遍历、保存/读取的简易通讯录：
// 将 _CRT_SECURE_NO_WARNINGS 放在最前面#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_NAME20#defineMAX_PHONE11#defineMAX_ADDR50// 通讯录节点structcontact_node{char name[MAX_NAME];char phone[MAX_PHONE];char addr[MAX_ADDR];structcontact_node* next;};// 函数声明structcontact_node*create_contact(constchar* name,constchar* phone,constchar* addr);intinsert_contact_tail(structcontact_node** p_head,structcontact_node* new_node);voidtraverse_contact(structcontact_node* head);structcontact_node*find_contact_by_name(structcontact_node* head,constchar* name);intdelete_contact_by_name(structcontact_node** p_head,constchar* name);voidfree_contact(structcontact_node** p_head);intsave_contact_to_file(constchar* filename,structcontact_node* head);intload_contact_from_file(constchar* filename,structcontact_node** p_head);intmain(void){structcontact_node* head =NULL;// 1. 新增联系人insert_contact_tail(&head,create_contact("张三","13699998888","深圳市南山区"));insert_contact_tail(&head,create_contact("李四","13577779999","北京市海淀区"));// 2. 遍历联系人printf("===== 通讯录列表 =====\n");traverse_contact(head);// 3. 查找联系人structcontact_node* find =find_contact_by_name(head,"张三");if(find !=NULL){printf("\n===== 查找结果 =====\n");printf("姓名：%s | 电话：%s | 地址：%s\n", find->name, find->phone, find->addr);}// 4. 保存到文件save_contact_to_file("contact.dat", head);// 5. 清空链表，从文件加载free_contact(&head);load_contact_from_file("contact.dat",&head);printf("\n===== 从文件加载的通讯录 =====\n");traverse_contact(head);// 6. 删除联系人delete_contact_by_name(&head,"李四");printf("\n===== 删除后通讯录 =====\n");traverse_contact(head);// 7. 释放内存free_contact(&head);return0;}// 创建联系人节点structcontact_node*create_contact(constchar* name,constchar* phone,constchar* addr){structcontact_node* new_node =(structcontact_node*)malloc(sizeof(structcontact_node));if(new_node ==NULL)returnNULL;// 使用 strncpy 并手动确保字符串结尾strncpy(new_node->name, name, MAX_NAME -1); new_node->name[MAX_NAME -1]='\0';// 确保字符串结尾strncpy(new_node->phone, phone, MAX_PHONE -1); new_node->phone[MAX_PHONE -1]='\0';strncpy(new_node->addr, addr, MAX_ADDR -1); new_node->addr[MAX_ADDR -1]='\0'; new_node->next =NULL;return new_node;}// 尾插联系人intinsert_contact_tail(structcontact_node** p_head,structcontact_node* new_node){if(new_node ==NULL|| p_head ==NULL)return-1;if(*p_head ==NULL){*p_head = new_node;return0;}structcontact_node* p =*p_head;while(p->next !=NULL) p = p->next; p->next = new_node;return0;}// 遍历联系人voidtraverse_contact(structcontact_node* head){if(head ==NULL){printf("通讯录为空！\n");return;}structcontact_node* p = head;int cnt =0;while(p !=NULL){ cnt++;printf("第%d个：%s | %s | %s\n", cnt, p->name, p->phone, p->addr); p = p->next;}}// 按姓名查找structcontact_node*find_contact_by_name(structcontact_node* head,constchar* name){if(head ==NULL|| name ==NULL)returnNULL;structcontact_node* p = head;while(p !=NULL){if(strcmp(p->name, name)==0)return p; p = p->next;}returnNULL;}// 按姓名删除intdelete_contact_by_name(structcontact_node** p_head,constchar* name){if(p_head ==NULL|| name ==NULL||*p_head ==NULL)return-1;structcontact_node* p =*p_head,* prev =NULL;while(p !=NULL&&strcmp(p->name, name)!=0){ prev = p; p = p->next;}if(p ==NULL)return-1;if(prev ==NULL)*p_head = p->next;else prev->next = p->next;free(p); p =NULL;return0;}// 释放通讯录voidfree_contact(structcontact_node** p_head){if(p_head ==NULL||*p_head ==NULL)return;structcontact_node* p =*p_head,* temp =NULL;while(p !=NULL){ temp = p->next;free(p); p = temp;}*p_head =NULL;}// 保存到文件（二进制）intsave_contact_to_file(constchar* filename,structcontact_node* head){ FILE* fp =fopen(filename,"wb");if(fp ==NULL)return-1;structcontact_node* p = head;while(p !=NULL){// 注意：这里存在结构体中未初始化填充字节的问题// 更好的方法是逐字段写入fwrite(p,sizeof(structcontact_node),1, fp); p = p->next;}fclose(fp);printf("\n通讯录已保存到文件：%s\n", filename);return0;}// 从文件加载intload_contact_from_file(constchar* filename,structcontact_node** p_head){ FILE* fp =fopen(filename,"rb");if(fp ==NULL)return-1;structcontact_node temp;while(fread(&temp,sizeof(structcontact_node),1, fp)==1){insert_contact_tail(p_head,create_contact(temp.name, temp.phone, temp.addr));}fclose(fp);printf("通讯录已从文件：%s 加载\n", filename);return0;}运行结果
说明：ZEEKLOG自带编译器无法编译，可以使用菜鸟或者VS等其他编译器
===== 通讯录列表 ===== 第1个：张三 | 13699998888 | 深圳市南山区 第2个：李四 | 13577779999 | 北京市海淀区 ===== 查找结果 ===== 姓名：张三 | 电话：13699998888 | 地址：深圳市南山区 通讯录已保存到文件：contact.dat 通讯录已从文件：contact.dat 加载 ===== 从文件加载的通讯录 ===== 第1个：张三 | 13699998888 | 深圳市南山区 第2个：李四 | 13577779999 | 北京市海淀区 ===== 删除后通讯录 ===== 第1个：张三 | 13699998888 | 深圳市南山区 
五、程序要点与避坑指南（新手必看）
5.1 链式结构常见错误
| 错误类型 | 错误代码示例 | 解决方案 |
|---|---|---|
| 野指针（未初始化指针） | struct student_node *p; p->age=18; | 指针使用前必须指向有效内存（malloc/已有节点） |
| 内存泄漏 | 删除节点不free/链表不整体释放 | 每个malloc对应一个free，删除/结束时释放所有节点 |
| 空指针访问 | traverse_list(NULL); | 函数内先检查指针是否为NULL |
| 头插法步骤颠倒 | *p_head = new_node; new_node->next=*p_head; | 先new_node->next=p_head，再p_head=new_node |
| 双向链表漏维护prev指针 | 插入时只改next，不改prev | 双向操作需同时维护prev和next |
5.2 链表选型指南
| 场景 | 推荐链表类型 | 原因 |
|---|---|---|
| 仅需单向遍历、增删少 | 单链表 | 实现简单，内存占用少 |
| 需双向遍历、频繁删除 | 双向链表 | 无需找前驱节点，删除效率高 |
| 需循环遍历（如环形队列） | 循环链表 | 尾节点指向头节点，无NULL终止 |
5.3 性能分析
- 插入/删除：单链表头插O(1)，尾插/指定位置插O(n)；双向链表删除O(1)（已知节点）；
- 遍历/查找：所有链表均为O(n)，远低于数组的O(1)；
- 内存：链表每个节点多占用指针空间（单链表8字节/64位系统），但按需分配，无浪费。
六、总结
- 链式结构核心：节点=数据域+指针域，通过指针串联分散的堆内存节点，实现动态增删；
- 单链表关键操作：
- 创建节点：malloc分配内存，初始化数据+指针；
- 插入：头插（O(1)）、尾插（O(n)）；
- 删除：找到前驱节点，修改指针+释放内存；
- 释放：遍历释放每个节点，头节点置空；
- 进阶方向：双向链表（双向指针）、循环链表（尾节点指向头），是二叉树、哈希表的基础；
- 选型原则：频繁增删选链表，频繁查询选数组。
掌握链式结构，你就突破了C语言“静态数据结构”的限制，具备了实现复杂业务逻辑的能力——无论是通讯录、库存系统还是游戏道具背包，链式结构都是你的核心工具！
🔥 关注博主，获取更多C语言数据结构实战干货！
💬 评论区留言“链式结构”，交流你遇到的问题或优化思路！
👍 点赞+收藏，巩固链表核心知识点，面试/项目都能用！
#C语言 #链式结构 #单链表 #双向链表 #数据结构 #实战案例 #内存管理
🎁欢迎关注，获取更多技术干货！
🚀 C语言宝藏资源包免费送！14 本 C++ 经典书 + 编译工具全家桶 + 高效编程技巧，搭配 C 语言精选书籍、20 + 算法源码 + 项目规范，还有 C51 单片机 400 例实战！从零基础到嵌入式开发全覆盖，学生党、职场人直接抄作业～ 关注文章末尾的博客同名公众号，回复【C 语言】一键解锁全部资源，手慢也有！
