数据结构实验三单链表详解：从指针原理到工程实现与避坑指南

说来也巧，每年到这个节点，总能在群里看到同一类问题：“实验3到底要写什么”“链表怎么老崩”“排序排完链表断了”。中国矿业大学的数据结构实验课进行到第三个实验，基本上就到了大家集体和指针搏斗的阶段。前两个实验如果还能靠静态数组和顺序表蒙混过关，实验3开始，底子不扎实的同学会明显感觉到吃力。这篇东西不打算给你贴一份能直接抄的源码了事，而是把实验3这类题目拆开，讲清楚每一段代码为什么非得这么写、哪些地方最容易丢分、出了问题怎么定位，最后再给一套能直接用的工程骨架和排查套路。

我用一个在大多数学校实验3里都非常有代表性的题目来展开——学生成绩管理系统的单链表实现。只要你实验3的题目是“用链表做XX管理系统”“约瑟夫环”“多项式加减法”或者“长整数运算”中的任何一种，这篇里的实现思路和避坑经验都适用。这些题目表面上各有不同，内核考的是同一套东西：结构体定义、动态内存管理、链表的基本操作、排序遍历，可能再加一个文件读写。把这套内核嚼碎了，换什么题型你都能接得住。

1. 实验3到底在考什么：别急着敲代码，先读懂题目意图

1.1 实验3在课程进度里的真实位置

如果你用的是严蔚敏《数据结构（C语言版）》那本教材，课程进度走到实验3的时候，大概率刚讲完第二章线性表。教材前两章看起来内容不多，但实际上埋了三个以后所有实验都会反复用到的能力：结构体与指针的组合使用、动态内存的申请和释放、线性结构在各种操作下的边界处理。

顺序表那张实验可能还有一些同学是“照着书敲一遍”就交差的，到了链表就完全行不通了。原因很简单：顺序表的下标访问符合直觉，arr[5]就是第6个元素；链表你得自己拿指针走到那个位置去，中间隔着多少个结点完全取决于你的循环走了几次。这个思维转换，是实验3和之前实验最大的分水岭。

1.2 一个典型的实验3题目会长什么样

假设题目是这样的：从键盘录入若干学生的学号、姓名、成绩，用单链表存储；支持按学号插入、按学号删除、按姓名查找；最后按成绩从高到低排序，并把排序后的结果保存到文件，下次程序启动能从文件恢复数据。

乍一看，函数还挺多，但冷静下来拆一下，其实就是五件事：

• 定义学生结构体，包含学号、姓名、成绩和指向下一个结点的指针
• 两个“增”操作：尾插建表和按位置插入
• 一个“删”操作：按学号删除结点，同时释放内存
• 一个“查”操作：支持精确按学号查和模糊按姓名查
• 一个“排”操作：按成绩排序，这里隐含了一个复杂度分析考点
• 一个“存”操作：把整条链表写入文件，并能重新读回内存

你看，所有高校最常见的实验3题目，基本都能装进这五件事里。题目花里胡哨，但骨架万年不变。

1.3 老师评分时会看什么

根据我听过不少同学反馈的评分细则，实验3的打分通常分四块：

检查点	基本要求	常见扣分点
功能完整性	增删改查排序都能用	删除后链表断链、插入位置越界没处理
代码规范	函数拆分合理、有注释、命名清晰	所有代码塞在main里，没有头文件组织
运行健壮性	非法输入不崩溃	空链表删除、重复学号、文件不存在
实验报告	有算法思路、复杂度分析、测试截图	只贴代码没有分析过程

第四点看上去最虚，实际上越是大面积代码雷同的实验，老师越会把重心放在报告上。后面我专门用一章来讲报告和演示环节怎么准备，这里先不展开。

2. 环境与工程骨架：把编译器和头文件问题一次解决掉

2.1 VS里scanf报错C4996的处理方法

几乎每个用Visual Studio写C语言的同学都会遇到这个报错：

error C4996: 'scanf': This function or variable may be unsafe.

这是VS的安全警告，不是你的代码有错，也不是编译器坏了。处理方式有两种：

一种是在代码文件最顶部加一行：

#define _CRT_SECURE_NO_WARNINGS

注意，这行必须在所有#include之前，否则不生效。

另一种是右键项目 → 属性 → C/C++ → 预处理器 → 预处理器定义，在末尾追加_CRT_SECURE_NO_WARNINGS。这种方式对项目里所有.c文件生效，不用每个文件都写一遍。

我建议用第二种，因为实验代码通常拆成好几个文件，每个文件都加宏有点烦。另外提醒一句，别用scanf_s去改代码，虽然VS里能跑，但提交到OJ或者换到Code::Blocks、Dev-C++、Linux环境就会编译失败，这种写法绑死了你的代码。

2.2 头文件与结构体定义

工程骨架建议分三个文件：

• student.h：结构体定义、函数声明、宏定义
• student.c：所有链表操作的实现
• main.c：主函数和菜单交互逻辑

student.h里有个细节值得注意，用#ifndef这种老式但稳妥的防止重复包含方式：

#ifndef STUDENT_H #define STUDENT_H #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_NAME_LEN 32 typedef struct StudentNode { int id; // 学号 char name[MAX_NAME_LEN]; // 姓名 float score; // 成绩 struct StudentNode* next; // 指向下一个结点的指针 } StudentNode; // 函数声明 StudentNode* createNode(int id, const char* name, float score); void appendNode(StudentNode** head, StudentNode* newNode); void insertAt(StudentNode** head, StudentNode* newNode, int pos); void deleteById(StudentNode** head, int id); StudentNode* findById(StudentNode* head, int id); StudentNode* findByName(StudentNode* head, const char* name); void sortByScore(StudentNode* head); void saveToFile(StudentNode* head, const char* filename); StudentNode* loadFromFile(const char* filename); void freeList(StudentNode* head); #endif

关于结构体命名，一个很常见的问题是有人写成这样：

typedef struct { int id; char name[32]; float score; struct StudentNode* next; // 编译报错：StudentNode未定义 } StudentNode;

这个错误特别容易在赶实验的时候出现：匿名的struct里不能自己引用自己的类型名，因为类型名在定义完才生效。必须像上面那样给结构体先起名struct StudentNode，然后用它声明next指针，最后再用typedef统一取别名StudentNode。这个顺序不能反。

2.3 为什么很多操作函数要传二级指针

这是实验3里最劝退的一个点。你看appendNode、insertAt、deleteById这几个函数的第一个参数都是StudentNode** head，而findById、sortByScore这些函数又是StudentNode* head。为什么有的要两个星号，有的只要一个？

判断标准很简单：看这个函数要不要改变head指针本身的值。

插入到第一个位置、删除第一个结点的时候，链表的第一个结点变了，外部那个记录链表头的指针就得跟着变。如果只传StudentNode* head，函数里改的是形参拷贝，外面main函数里的头指针还是原来的旧地址，链表就从中间断了，甚至整个链表都找不到了。

打个比方：你要用一根绳子和一串钥匙把门窗换了，光把绳子的头递给别人不够，你得告诉人家装钥匙的那个抽屉在哪。&head就是那个抽屉的位置，head只是绳子头。C语言里传值就是递绳子，传指针才是告诉人家抽屉地址。

3. 单链表的五个核心操作：建表、插入、删除、查找的实现细节

3.1 创建结点：malloc之后必须检查返回值

任何结点操作的第一步都是创建结点。这个函数是整个实验里最不起眼但是最不能省的一个：

StudentNode* createNode(int id, const char* name, float score) { StudentNode* node = (StudentNode*)malloc(sizeof(StudentNode)); if (node == NULL) { printf("内存分配失败，程序退出\n"); exit(1); } node->id = id; strcpy(node->name, name); node->score = score; node->next = NULL; return node; }

三点说明：

第一，sizeof(StudentNode)是结构体的完整大小，不是指针的大小。新手最容易写错的地方是把sizeof(StudentNode*)当成sizeof(StudentNode)，前者只有8个字节（64位系统），后者至少40个字节，写成前者后面所有赋值都是越界写。

第二，malloc返回的void*在C语言里可以隐式转换到任意指针类型，所以(StudentNode*)这个强转在纯C里其实可以省略。但VS会用C++编译器来编译.c文件，C++里void*不能隐式转换成其他指针类型，所以这个强转写上，兼容性更好。

第三，exit(1)处理失败是有意为之。链表操作里如果内存都申请不到，后续任何操作都没有意义，直接退出比返回一个NULL让上层一路检查下去更干净。这个取舍在实验报告里如果你主动写出来，老师会觉得你考虑问题比一般人细致。

3.2 尾插建表：为什么不用头插法

录入一组学生信息，自然希望后续查找、打印的时候还是按输入顺序来，所以用尾插法。代码逻辑不复杂：

void appendNode(StudentNode** head, StudentNode* newNode) { if (*head == NULL) { *head = newNode; return; } StudentNode* p = *head; while (p->next != NULL) { p = p->next; } p->next = newNode; }

有些同学偷懒想用头插法——每次新结点都插到最前面，代码短很多，但结果就是数据顺序和输入顺序完全相反。如果实验题目要求“按输入顺序显示”，头插法直接扣分。

再提一个性能相关的点：每次尾插都要从头遍历到尾部，插入n个结点的时间复杂度是O(n²)。数据量小无所谓，但如果测试数据有几千条，能感觉到明显的卡顿。改进方案是额外维护一个尾指针，或者直接用双向链表，但实验3一般不要求这个，你在报告里把这个复杂度问题写明白就够了。

3.3 按位置插入：边界条件是最容易扣分的地方

题目要求“在第pos个位置插入一个结点”，pos由用户输入。这个函数的边界条件特别多，我直接给出完整实现：

void insertAt(StudentNode** head, StudentNode* newNode, int pos) { // pos <= 0 或链表为空时，统一当作头插处理 if (pos <= 0 || *head == NULL) { newNode->next = *head; *head = newNode; return; } // 找到第 pos-1 个结点，注意循环条件里两个判断不能互换 StudentNode* p = *head; int index = 0; while (p->next != NULL && index < pos - 1) { p = p->next; index++; } // 中间位置插入 newNode->next = p->next; p->next = newNode; }

这里有三个隐藏考点：

第一个，为什么pos <= 0要当头插处理？因为用户可能输入0、-1、-3这种数字，如果程序不处理，后面index < pos - 1这个条件在pos为负数时可能根本不进入循环，然后newNode->next = p->next就把新结点插到了第一个结点之后，完全不是用户要的位置。稳妥做法就是直接约定：小于等于0一律视为插到最前面。

第二个，p->next != NULL && index < pos - 1这两个条件的顺序不能写反。如果写成index < pos - 1 && p->next != NULL，当pos非常大（比如1000）而链表只有5个结点时，循环会一直走到p为NULL，然后下一行p->next就是空指针访问，程序崩溃。把p->next != NULL放前面，走到链表尾部就停下，正好当作尾插。

第三个，走到循环结束时有两种可能：要么找到了第pos-1个结点，要么链表刚好走完了。这两种情况共用后面的插入代码是没问题的，因为链表最后一个结点的next本来就是NULL，这时候插入等价于尾插。

3.4 按学号删除结点：断链和释放的顺序不能乱

删除操作是所有链表题里最容易写错的地方，几乎所有断链bug都出在这里。完整实现：

void deleteById(StudentNode** head, int id) { if (*head == NULL) { printf("链表为空，无法删除\n"); return; } StudentNode* p = *head; StudentNode* prev = NULL; // 找到目标结点，同时保存它的前驱 while (p != NULL && p->id != id) { prev = p; p = p->next; } if (p == NULL) { printf("未找到学号为%d的学生\n", id); return; } // 如果删除的是第一个结点，要更新头指针 if (prev == NULL) { *head = p->next; } else { prev->next = p->next; } free(p); // 释放目标结点的内存 printf("删除成功\n"); }

三个必须强调的细节：

第一，必须用prev保存前驱结点。单链表只能从头往后走，目标结点的前一个结点如果不记录，一旦修改了p->next就再也找不到前驱了。这就像拆火车车厢，你不先断开前一节车厢的连接钩，后一节车厢就拖着跑了。

第二，删除头结点时，*head = p->next这一步必不可少。你删掉的是当前链表第一个结点，如果不更新头指针，main函数里的head还指向一块已经被free掉的内存，下次遍历程序直接崩溃。

第三，free(p)不是可选项。有些同学写到最后整个程序跑起来“看起来没问题”，但就是忘了释放结点内存。实验规模小，程序退出了操作系统会回收，所以表面没问题。但这是被老师问住的高频点：“你的程序频繁插入删除，时间长了内存会不会越用越多？”

3.5 查找：按学号精确查找和按姓名模糊查找

查找函数不需要修改链表，所以传一级指针就够了：

StudentNode* findById(StudentNode* head, int id) { StudentNode* p = head; while (p != NULL) { if (p->id == id) { return p; } p = p->next; } return NULL; } StudentNode* findByName(StudentNode* head, const char* name) { StudentNode* p = head; while (p != NULL) { if (strstr(p->name, name) != NULL) { // 子串匹配，实现模糊查找 return p; } p = p->next; } return NULL; }

findById没什么好说的，顺序遍历对比。findByName用了一个strstr函数，它的作用是判断第二个参数是不是第一个参数的子串。比如你输入“王”，它能匹配到“王小明”“王芳”“小王”这些名字里带“王”的人。这就是题目里“按姓名模糊查找”的实现。

实际写的时候，有一种情况要处理：查不到时怎么办。我上面对应的函数都是返回NULL，所以main函数里调用后要先判断：

StudentNode* result = findById(head, target); if (result == NULL) { printf("查无此人\n"); } else { printf("学号：%d 姓名：%s 成绩：%.1f\n", result->id, result->name, result->score); }

不判断直接result->name，在查不到的时候就是空指针访问了。

4. 排序与文件持久化：链表上怎么玩转数据落盘

4.1 链表排序：用数据域交换还是指针域交换

按成绩排序有两种思路，一种是把结点里的数据成员交换来交换去，一种是把结点之间的next指针重新链接。很多人上来就选第二种，觉得“链表排序嘛，肯定要改指针”，结果写了两天没调通。

我的建议是实验3级别用数据域交换。直接给实现：

void sortByScore(StudentNode* head) { if (head == NULL) return; for (StudentNode* p = head; p != NULL; p = p->next) { for (StudentNode* q = p->next; q != NULL; q = q->next) { if (p->score < q->score) { // 从高到低排序 // 交换三个数据成员 int tmpId = p->id; p->id = q->id; q->id = tmpId; char tmpName[MAX_NAME_LEN]; strcpy(tmpName, p->name); strcpy(p->name, q->name); strcpy(q->name, tmpName); float tmpScore = p->score; p->score = q->score; q->score = tmpScore; } } } }

这个写法本质上是选择排序：每次找到一个比当前结点成绩更大的，交换数据。它的时间复杂度O(n²)，数据交换次数较多，但胜在实现简单、不出错。

为什么不推荐在实验里硬啃指针域交换？因为链表结点的后面所有结点都跟着那个next指针走，改一处next，整个链表拓扑就变了，你至少需要维护四个指针（前驱、当前结点、目标结点、目标的前驱），边界情况多到足以让你在实验室待一晚上。实验3的考察重点是会不会用链表、有没有复杂度意识，不是考察你能不能写出来一个O(n log n)的链式归并排序。如果你主动在报告里写清楚“这里用数据域交换，避免指针重链接带来的复杂边界处理，代价是数据交换开销较大，适用于数据量较小的场景”，老师不仅不会扣分，反而会觉得你思路清楚。

4.2 保存文件的正确姿势：不要直接把整个结点写进文件

文件保存这块，最大的坑是把fwrite(p, sizeof(StudentNode), 1, fp)当成理所当然的保存方式。

StudentNode结构体里面有next这个指针成员。如果直接把整个结构体写入文件，指针的值只是一个内存地址数字，比如0x00B66F20，你把这个数字写进文件没有任何意义，下次程序运行内存布局和这次完全不一样，这个地址是无效的。更糟糕的是，如果保存的结点是链表中间的某个结点，指针指向的内存区域一旦被其他程序覆盖，这个文件就会产生乱码。

正确做法是定义一个不包含指针的“数据中转结构体”，只把数据成员写入文件：

// 用于文件读写的数据结构，不含指针 typedef struct StudentData { int id; char name[MAX_NAME_LEN]; float score; } StudentData; void saveToFile(StudentNode* head, const char* filename) { FILE* fp = fopen(filename, "wb"); if (fp == NULL) { printf("无法打开文件 %s\n", filename); return; } StudentNode* p = head; StudentData data; while (p != NULL) { data.id = p->id; strcpy(data.name, p->name); data.score = p->score; fwrite(&data, sizeof(StudentData), 1, fp); p = p->next; } printf("保存成功，共写入 %d 条记录\n", getListLength(head)); fclose(fp); }

这里还有个小优化，保存前可以先把文件里的旧内容删掉，避免新旧数据混在一起。做法是先remove(filename)再fopen，或者直接用fopen(filename, "wb")，"wb"模式本来就会覆盖旧文件，所以不需要额外处理。

4.3 读取恢复：用数据中转结构体重新建链

读取的时候就是反向操作，从文件里一条条读数据，每次创建一个新结点并尾插到链表里：

StudentNode* loadFromFile(const char* filename) { FILE* fp = fopen(filename, "rb"); if (fp == NULL) { printf("文件 %s 不存在，请先录入数据\n", filename); return NULL; } StudentNode* head = NULL; StudentData data; while (fread(&data, sizeof(StudentData), 1, fp) == 1) { StudentNode* node = createNode(data.id, data.name, data.score); appendNode(&head, node); } fclose(fp); printf("成功从文件加载数据\n"); return head; }

fread的返回值是成功读取的数据块个数。对于二进制文件，当读到文件末尾时返回0，这正好作为循环终止条件。用feof(fp)判断文件结束是一个很常见的错误，因为feof是要先触发一次读失败后才会返回真，导致循环多读一次。用fread的返回值来控制循环是更标准的做法。

文件操作还有一个很实际的问题：如果你在保存过程中程序突然断电或者崩溃，文件可能只写了一半，下次读取就会读到半条不完整的数据。要彻底解决这个问题，得用“先写临时文件，再改名”的策略，但实验3一般不会要求到这一步，把fwrite和fread配对用对了，已经能拿大部分分数了。

5. 内存管理三连坑：野指针、断链与泄漏的排查全过程

5.1 坑一：删除结点之后继续访问，野指针

有同学给我看过这样的代码：

StudentNode* p = findById(head, 2022001); deleteById(&head, 2022001); printf("删除的学生是：%s\n", p->name);

看起来合情合理：先找到结点，再删除，最后打印一下删除的学生的姓名。问题在于deleteById函数里已经对这个结点free(p)了，p变成野指针，再访问p->name就是访问一块已经归还给操作系统的内存。

更麻烦的地方在于：很多情况下这个printf可能还“碰巧”能打印出正确的姓名。原因是free只是把这块内存标记为可用，操作系统并没有立刻清空里面的数据。于是你又往里写了别的数据，或者这块内存被分配给其它变量，再访问就会打印出一堆乱码或直接崩溃。

实验演示的时候，这恰恰是老师最喜欢点的一个位置：“你删完了为什么还能访问？你确认这个内存已经释放了吗？”这个问题的标准答案是：free(p)之后要立刻把p = NULL，让后续任何使用p的代码都能在运行时暴露出错误，而不是等到数据被改写了才出莫名其妙的问题。

5.2 坑二：尾插忘记把next置NULL，遍历直接越界

createNode里面最后一行是node->next = NULL。这一行看起来毫无技术含量，但是漏掉它的后果非常严重。

malloc出来的内存里存的可能是什么？可能是之前被释放的内存残留数据，也就是一个野指针地址。尾插的时候：

p->next = newNode; // 这行没问题

遍历的时候，从头开始while (p != NULL) { ... p = p->next; }，走到最后一个结点时，p->next是一个随机地址，程序就会跑到一个完全不确定的内存区域，读出来的数据无意义，再往p->next访问就直接段错误。

虽然有些人巧合地发现malloc返回的内存恰好初始化为0（有些系统会在某些情况下清零堆内存），但这个行为没有任何保证。调试这类bug是最费时间的，因为表现不稳定，时而崩溃时而正常。

所以记住一个铁律：任何从malloc出来的结构体，成员指针必须显式初始化为NULL。这个习惯养成了，能省掉一大半的调试时间。

5.3 坑三：malloc出来的结点没free，内存泄漏

内存泄漏比野指针隐蔽得多，因为症状通常不会立刻爆发，而是表现为“程序越跑越卡”“总内存占用越来越大”：

void deleteWithLeak(StudentNode** head, int id) { // 找到p之后 if (prev == NULL) { *head = p->next; } else { prev->next = p->next; } // 漏了 free(p) }

链表结构已经正确更新了，删除后遍历打印都正常，看起来“没问题”，但被删除的结点的内存没有被归还。如果这个程序是一个循环菜单，用户反复执行删除操作，每次泄漏几十个字节，程序运行时间长，内存占用会一路涨上去。

检查方法很多，最朴素有效的是在main函数退出前打印一个计数：

// 统计链表当前结点数和累计创建的结点数 printf("当前链表结点数：%d\n", countNodes(head)); printf("累计创建的结点数：%d\n", totalCreated);

如果totalCreated - countNodes != 删除失败的次数，那肯定有地方漏了free。

5.4 三个排查手段从快到慢排个序

我先说结论：出问题了不要一开始就开调试器单步走，先打印。

第一个手段是打印定位法，在关键操作前后加printf，比如删除前后打印“准备删除：学号%d”、“删除成功，头指针=%p”。用打印把程序执行的路径画出来，很快就能定位到是哪个环节出的问题。调试链表问题时，最好再写一个printList(head)函数，遍历打印整个链表的所有结点数据，每次增删改之后都调用一次看链表状态是否符合预期。

第二个手段是调试器单步跟踪。Visual Studio里F10逐过程、F11逐语句，配合监视窗口查看head、p、p->next的值，观察指针变化是否和你预期的一致。建议看地址值的时候在监视窗口输入(StudentNode*)类型转换，VS对自定义结构体的显示有时候不友好。单步跟踪对新手特别有用，走两遍很快就把链表“走”明白了。

第三个手段是专门的内存检查工具。GCC环境下编译时加-fsanitize=address会提供内存错误检测，能精确定位到是第几行对内存的非法访问。Windows下Visual Studio可以用_CrtDumpMemoryLeaks()函数检查内存泄漏，但需要在调试模式下使用。这个工具手段要提前配好环境，别等到演示前才手忙脚乱去查。

6. 实验报告与演示答辩：决定最终分数的隐藏环节

6.1 实验报告的整体框架

很多同学以为实验报告就是把代码粘上去，实际上老师想看到的是你对题目和方案的理解过程。给你一个参考框架：

板块	要写的内容	避坑提示
题目分析	用你自己的话描述题目要求，给出输入输出示例	别抄题目原文，用自己的话转述
数据结构设计	结构体定义、为什么选单链表而不是顺序表	分析两种结构的优缺点，对比说明
核心算法思路	建表、插入、删除、排序、文件读写的文字描述加流程图描述	这个环节不用写代码，写思路
复杂度分析	每个操作的时间复杂度和空间复杂度	尾插建表是O(n²)，直接写O(n)会被发现
测试记录	正常情况、边界情况、异常情况的运行截图	截图必须能看到输入和输出对应
经验总结	遇到的问题和解决方法	写得越具体越真实，老师最反感“我学会了链表”这种空话

复杂度分析这块最容易翻车。比如插入操作，单链表已知位置插入是O(1)，但按位置查找是O(n)，所以整体是O(n)。查找是O(n)，排序是O(n²)，文件写入是O(n)。你把这些写清楚，报告就已经超过80%的人了。

6.2 演示前的边界测试清单

演示的时候，老师会挑几个刁钻的操作看你的程序崩不崩。你可以提前把这些测试全部跑一遍：

• 在空链表上执行删除操作，程序不能崩溃，要提示“链表为空”
• 删除不存在的学号，要提示“未找到”而不是崩溃
• 查找不存在的姓名，要提示“查无此人”而不是崩溃
• 插入位置输入负数、0、超过链表长度的大数字，程序行为要合理
• 打开一个不存在的文件，要给出友好提示而不是黑屏
• 连续创建几千条数据，程序不能明显卡顿或崩

我见过太多演示翻车的场景：老师删除一个不存在的学号，程序直接段错误，前面的功能全部前功尽弃。所以演示前一定把这些边界测试跑一遍。

6.3 老师最经常问的几个问题

演示过程中或者交报告时，老师会随机问几个涉及原理的问题，这里列几个高频的，你提前把答案准备好：

• “为什么这里要用链表而不是数组？”答题思路：链表插入删除不需要搬移元素，O(1)完成指针调整；数组插入删除需要移动后续所有元素，O(n)。但链表的随机访问是O(n)，数组是O(1)，所以适合频繁增删、较少随机访问的场景。
• “你的删除操作时间复杂度是多少？”答题思路：如果已经知道目标结点的前驱，O(1)；但通常需要先查找，所以查找O(n) + 删除O(1) = 整体O(n)。
• “为什么删除结点之后要free？”答题思路：防止内存泄漏，让操作系统能够重新利用这部分内存。程序长期运行，泄漏会导致内存耗尽。
• “你的排序算法最坏情况时间复杂度是多少？”答案是O(n²)。如果再追问能不能优化，你就说还有归并排序的链式版本可以做到O(n log n)，意识到这个问题说明了你的深度。
• “文件里保存的是什么？下次打开为什么能恢复？”答题思路：保存的是每个结点的数据域（学号、姓名、成绩），不含指针。读取时逐条重建链表。

最后再分享一点个人体会。我在带学弟学妹做实验的时候发现，链表这东西，你说它难，它真的不难，无非就是画图——把一个结点画成一个盒子，里面放着数据和一个箭头，然后按代码走两步，看箭头怎么指。你卡住的每一道链表题，几乎都是因为没在纸上画图，直接对着代码空想。说句实话，你做实验3花掉的三五个小时里，有一个小时花在画图上，后面能省出两倍的时间。画着画着你就会发现，所谓指针操作，不过就是“把某个盒子里装的地址改成另一个地址”而已。