简介面向C语言初学者与数据结构复习者这份文档以完整可运行的C代码为主线系统讲解单链表的十九种常用操作涵盖链表创建、遍历打印、结点统计、空表判断、冒泡排序以及按位置/按值查找、结点修改、表头/表尾/指定位置插入、有序插入、表头/表尾/指定位置/指定值删除、交换结点和整表删除等场景从基础构建到灵活维护形成完整练习闭环。资源为一个PDF文件大小仅57KB内容紧凑、便于离线查阅。目前已有734位学习者下载适合在课程实验、期末复习或研究生复试上机前对照练习。文档内含完整C代码和关键函数注释重点演示内存动态分配、内存初始化以及指针链接操作读者通过实际运行可直观观察每个操作对链表结构的影响快速加深对单链表和内存管理的理解。1. 为什么还要手写链表十九种操作到底解决什么问题在 C 语言的数据结构课程里链表永远是第一个需要亲手实现的非线性存储结构而「十九种操作」几乎是每份数据结构实验报告的标配清单。你以为自己会用头插法建链表就算过了实际上面试里问的、综合实验里卡的、后续学到二叉树时返回来补的都是这些操作里的边界细节指定位置插入算不算越界、按值删除删到几个、逆置之后头指针还在不在。这篇内容就是把这十九种操作拆开从结构体定义到销毁链表全部用代码走一遍把每个函数的参数约定和翻车点讲清楚。适合正在写实验报告的学生也适合想把链表基础重新夯一遍的从业者。2. 链表骨架结构体定义、初始化与两种创建方式2.1 结构体与宏定义动手前先把类型约定写清楚写链表第一行代码不是malloc而是结构体定义。常见做法是这样#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; typedef Node *LinkedList;结构体内部的next必须写成struct Node *next不能写成Node *next。原因是typedef的别名Node在这一行还没有定义完编译器此时还不知道Node是什么类型只有struct Node这个标签在结构体声明一开始就生效。这个细节在期末上机和单片机移植场景里都很容易卡住因为很多教材直接写Node *next学生照着抄就报unknown type name Node。数据域的类型我默认用int链表操作实验和数据结构考研题里int基本够用。如果以后要存字符串或者结构体可以把int data换成void *data但涉及深拷贝和类型转换不是这篇文章的重点。类型别名LinkedList表示头节点指针Node *表示普通节点指针两者实质相同但语义上分开写能让代码读起来清楚不少。命名约定也要提前定头节点指针统一叫head循环遍历指针统一叫p待删除节点叫toBeDeleted。这样十九种操作写下来代码风格一致实验报告里贴代码也好看。别小看命名后面写mergeLists这类多链表操作时pa、pb、pc的区分全靠约定在撑。2.2 初始化与判空带头节点让代码统一链表分带头节点和不带头节点两种。我强烈建议在数据结构实验和初学阶段一律用带头节点的写法原因是带头节点能让「空链表」和「非空链表」的插入删除代码合并成同一套逻辑不用单独判断头指针是否为NULL。LinkedList initList() { LinkedList head (LinkedList)malloc(sizeof(Node)); if (head NULL) { printf(初始化失败内存分配失败\n); exit(1); } head-next NULL; return head; } int isEmpty(LinkedList head) { return head-next NULL; }头节点本身不存有效数据data字段闲置next才指向第一个实际数据节点。初始化时头节点的next必须置NULL这是新手最容易漏的一步。如果不置空head-next就是一个随机地址后续isEmpty、遍历、插入全部跟着崩而且崩得毫无规律看起来像玄学其实就是这一步没做。exit(1)用在初始化失败这种致命错误上是合理的因为链表都没建起来程序继续跑没有意义。但插入节点时malloc失败就不能exit最好是打印提示后return让调用方决定怎么处理。2.3 头插法与尾插法两条创建路线的选择创建链表有两种基础手法。头插法把新节点插到头节点后面尾插法把新节点追加到链表末尾。直接看代码void insertAtHead(LinkedList head, int value) { Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(插入失败内存分配失败\n); return; } newNode-data value; newNode-next head-next; head-next newNode; } void insertAtTail(LinkedList head, int value) { Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(插入失败内存分配失败\n); return; } newNode-data value; newNode-next NULL; Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; }头插法的代码顺序有讲究先给newNode-next赋值成head-next再把head-next指向newNode。反过来写就把原来的链表丢了因为head-next一旦被覆盖旧链表的入口就找不到了。尾插法需要一个遍历过程p从头节点开始一路走到p-next NULL为止此时p就是最后一个节点把newNode挂上去。注意循环条件是p-next ! NULL而不是p ! NULL如果写成后者p会走到NULL再执行p-next newNode就野指针了。两种方法的取舍看场景维度头插法尾插法创建顺序与输入顺序相反与输入顺序相同时间复杂度O(1)O(n)每次都要遍历典型用途逆序建表、栈结构保持原始顺序用头插法连插 1、2、3最终链表是 3、2、1。想要正向输出要么用尾插法要么建完表再逆置一次。很多数据结构实验要求「按输入顺序建立单链表」那就是尾插法的活别用头插法建完发现顺序反了又回头问为什么——这不是 bug是特性。3. 插入、删除与查找链表操作的核心三角3.1 在指定位置插入链表先找前驱再改指针在指定位置插入是链表操作里最常考的一个。约定位置从 1 开始计数pos 1表示插到第一个节点之前pos length 1表示插到末尾。void insertAtPos(LinkedList head, int pos, int value) { if (pos 1) { printf(插入失败位置必须从 1 开始\n); return; } Node *p head; int i 0; while (p ! NULL i pos - 1) { p p-next; i; } if (p NULL) { printf(插入失败位置 %d 超出链表长度\n, pos); return; } Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(插入失败内存分配失败\n); return; } newNode-data value; newNode-next p-next; p-next newNode; }核心思路是插入到第pos个位置必须找到第pos - 1个节点作为前驱。p从头节点出发从头节点到第一个实际节点正好走一步到位所以p初始是head循环pos - 1次就是对的。这个「头节点参与计数但不占位置」的设计正是带头节点省事的体现。循环条件用p ! NULL而不是p-next ! NULL是为了允许插入到末尾。假设链表长度是 3要插到第 4 个位置循环会走到最后一个节点然后停下此时p ! NULL可以正常插入。如果用p-next ! NULL做条件p只能走到倒数第二个节点就停插入位置直接从 4 变成 3语义就错了。越界判断也在这里如果pos比length 1还大p最终会走到NULL说明前驱不存在插入失败。参数说明收一下pos合法区间是[1, length 1]value是任意int数据函数无返回值失败全靠打印提示正式项目里可以改成返回bool或错误码。3.2 删除链表节点释放顺序决定程序生死删除操作比插入更容易出事因为涉及free。删除第pos个节点和删除第一个值为value的节点是两种最常见的删除方式。void deleteAtPos(LinkedList head, int pos) { if (pos 1) { printf(删除失败位置必须从 1 开始\n); return; } Node *p head; int i 0; while (p-next ! NULL i pos - 1) { p p-next; i; } if (p-next NULL) { printf(删除失败位置 %d 超出链表长度\n, pos); return; } Node *toBeDeleted p-next; p-next toBeDeleted-next; free(toBeDeleted); } void deleteByValue(LinkedList head, int value) { Node *p head; while (p-next ! NULL p-next-data ! value) { p p-next; } if (p-next NULL) { printf(删除失败链表中不存在值为 %d 的节点\n, value); return; } Node *toBeDeleted p-next; p-next toBeDeleted-next; free(toBeDeleted); }删除的关键顺序是先用一个临时指针toBeDeleted记住待删节点然后把前驱的next跨过待删节点最后才free(toBeDeleted)。如果顺序反过来先free再访问p-next那块内存已经还给堆了读出来的是垃圾值写回去就是野指针操作。deleteAtPos和insertAtPos的循环条件不一样注意deleteAtPos用的是p-next ! NULL。因为删除要求待删节点必须存在p-next就是待删节点所以循环条件保证p不会走到最后一个节点之后这样p-next永远有值可判断。而insertAtPos允许「空位插入」所以用p ! NULL。这个差异是链表操作里最容易混淆的一对实验报告里经常有人把两个函数的循环条件抄串结果一个越界一个漏删。deleteByValue只删除第一个匹配的节点。如果要删掉所有值为value的节点改成循环删除即可但注意每次删除后p不要往后走因为删掉当前节点后p-next已经指向了下一个节点需要继续判断它是不是也要删。3.3 按值查找与按位查找返回下标还是返回指针查找操作有两种基本问题给值找位置、给位置取值。这正是顺序表「按值查找」和「按位查找」在链表上的对应版本。int findNode(LinkedList head, int value) { Node *p head-next; int pos 1; while (p ! NULL p-data ! value) { p p-next; pos; } if (p NULL) { return 0; } return pos; } int getNode(LinkedList head, int pos) { if (pos 1) { printf(查找失败位置必须从 1 开始\n); return -1; } Node *p head-next; int i 1; while (p ! NULL i pos) { p p-next; i; } if (p NULL) { printf(查找失败位置 %d 超出链表长度\n, pos); return -1; } return p-data; }findNode从第一个实际节点开始找pos跟着p同步递增找到返回位置找不到返回0。这里有个约定问题位置从 1 开始所以0可以作为「不存在」的哨兵值。如果数据域允许存储0而且会查找0这个值这个约定就失效了。更稳妥的做法是让函数返回Node *找到返回节点指针找不到返回NULL但这会让调用方的判断逻辑从if (pos 0)变成if (p ! NULL)两种风格都有人用选一种并在整个项目里保持一致。getNode按位取值越界返回-1同样存在类似问题。一个更健壮的签名是int getNode(LinkedList head, int pos, int *outValue)用函数返回值表达是否成功用出参带回数据。这在处理数据域可能为负数的场景下是必要的链表操作实验里一般不会抠到这个程度但如果你要写通用工具库建议直接上出参版本。4. 进阶操作链表逆置、排序、合并与去重的实现细节4.1 链表逆置三指针法为什么稳定逆置是链表操作里第一个让新手血压升高的函数。十九种操作里如果只能挑一个重点背我建议背这个。三指针法的代码很短但每一步都不能省void reverseList(LinkedList head) { Node *prev NULL; Node *current head-next; while (current ! NULL) { Node *next current-next; current-next prev; prev current; current next; } head-next prev; }三指针分别是prev、current、next。核心动作就三个先用next记住current后面的节点再把current-next指回prev最后prev和current同步前移。最容易翻车的是第一步。current-next prev执行之后current原来的后继就丢了所以必须在改指向之前把它存到next里。很多初学者会问「能不能先current current-next再改prev」答案是不能因为current一移动原来那个节点的next就找不到了。循环结束时current已经走到NULLprev停在原链表的尾节点也就是新链表的头节点。最后一步必须把head-next指向prev否则头节点还指着原来的第一个节点而这个节点现在已经变成新链表的最后一个节点了遍历会直接从第一个跳到NULL看起来就像链表被截断了一样。三指针法的时间复杂度是 O(n)空间复杂度 O(1)不依赖递归栈这是它作为标准答案的原因。递归逆置也可以做但链表长到几千个节点时递归深度可能撑爆栈嵌入式环境里尤其不建议。4.2 链表排序冒泡排序只换数据不换节点链表排序有两条路线换数据、换指针。换数据简单粗暴适合int这类小数据域直接套用数组冒泡排序的思路void sortList(LinkedList head) { if (head-next NULL || head-next-next NULL) { return; } Node *end NULL; int swapped; do { swapped 0; Node *p head-next; while (p-next ! end) { if (p-data p-next-data) { int temp p-data; p-data p-next-data; p-next-data temp; swapped 1; } p p-next; } end p; } while (swapped); }这个实现是标准冒泡排序的链表版。外层do-while控制多轮遍历内层指针p从头开始两两比较end记录每一轮最后一个参与比较的位置——每完成一轮最大的数就沉到末尾end前移一位。swapped是提前退出开关某一轮没有发生交换说明已经有序直接结束。换数据的问题在于如果链表存的是大结构体每次交换要拷贝整个结构体开销很高。换指针的做法是只改节点的next指向不碰数据域复杂度高不少一般用插入排序实现更自然。数据结构实验阶段用换数据的冒泡排序完全够用。有一个容易忽略的点排序return的边界条件是链表空或只剩一个节点。两个节点以下没必要排如果强行进入外层循环end head-next时内层判断p-next ! end永远为假函数直接空转一轮虽然没有 bug 但白跑一次。4.3 有序链表合并哨兵节点让代码干净一半合并两个有序链表核心是双指针游走。新建一个带头节点的链表Cpa和pb分别遍历A、B谁小谁先进CLinkedList mergeLists(LinkedList A, LinkedList B) { LinkedList C (LinkedList)malloc(sizeof(Node)); if (C NULL) { return NULL; } C-next NULL; Node *pa A-next; Node *pb B-next; Node *pc C; while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { pc-next pa; pa pa-next; } else { pc-next pb; pb pb-next; } pc pc-next; } pc-next (pa ! NULL) ? pa : pb; return C; }pc始终指向新链表C的当前尾节点。每接入一个节点pc后移一位。剩下的pa或pb的剩余部分直接整体挂到pc-next后面不需要逐个遍历因为剩下的那一段本来就是有序的整体接上去不会破坏有序性。合并操作有个坑它返回的新链表C里的节点和A、B的节点是共享的没有发生malloc复制。这意味着调用方如果对C执行了清空操作A、B里的节点也会被释放。这是设计选择但必须写清楚。如果实验要求「原链表不受影响」就得在合并时逐节点复制代价是 O(n) 的malloc一般不这么干。4.4 链表去重重复节点的释放时机去重一般针对有序链表因为无序链表去重必须用哈希表辅助复杂度完全不同。有序链表去重的逻辑很简单相邻节点值相同就删掉一个。void removeDuplicates(LinkedList head) { if (head-next NULL) { return; } Node *p head-next; while (p ! NULL p-next ! NULL) { if (p-data p-next-data) { Node *dup p-next; p-next dup-next; free(dup); } else { p p-next; } } }注意一个细节发现重复时p不要往后移动。因为删掉dup之后p-next已经指向了下一个节点这个节点可能仍然和p的值相同需要继续判断。只有当前p和下一个节点值不同时p才往前走。这个「删除时原地踏步」的细节和deleteByValue循环删除是一样的道理。去重前建议先排序否则这个函数的行为未定义——它只检查相邻节点无序链表里相同的值分散在不同位置根本删不干净。5. 链表常见问题排查野指针、内存泄漏与边界条件5.1 野指针free 之后忘了置空现象链表删除几个节点之后继续遍历程序随机崩溃gdb里看到的指针地址有时有效有时是垃圾值。多跑几次崩溃位置还不一样看起来像玄学。原因free(toBeDeleted)只是把内存还给堆但toBeDeleted这个指针变量还保留着旧地址。如果后续代码不小心free(toBeDeleted-next)或者toBeDeleted-data访问的是一块已经释放的内存行为未定义。更隐蔽的是同一块内存可能被堆管理器重新分配出去变成别的变量再操作就污染了别的数据。解决free之后立刻置NULL并且把这条写成肌肉记忆。C 语言的free不会帮你置空指针这是语言设计不是缺陷。如果删除函数比较多可以在工具函数里统一封装void freeNode(Node **nodePtr) { if (nodePtr ! NULL *nodePtr ! NULL) { free(*nodePtr); *nodePtr NULL; } }5.2 头节点悬空带头节点与不带头节点的混用现象从教材 A 上抄了带头节点的创建函数又从教材 B 上抄了一个不带头节点的遍历函数两个函数接在一起输出少一个节点或者遍历直接崩。原因不带头节点的链表头指针指向的是第一个有效节点带头节点的链表头指针指向的是哨兵节点head-next才是第一个有效节点。如果混用两种模式的头指针含义不同一个函数里head是有效数据另一个函数里head是空的哨兵互相一传就错位。解决整个项目从头到尾只选一种模式。我在文章里全部使用带头节点理由前面说过——插入和删除的边界逻辑统一。如果你确实要兼容别人写的不带头节点代码唯一的办法是在入口处做转换比如写一个适配函数把头节点去掉再传进去但这样做代码很丑不如直接统一风格。5.3 内存泄漏malloc 与 free 的配对记账现象程序跑完操作系统内存占用缓慢上涨或者一个循环里反复创建链表跑几分钟内存就爆了。在单片机等嵌入式环境里泄漏几次系统直接重启。原因每个节点malloc一次就必须对应一次free。创建的时候用insertAtTail插了 100 个节点如果最后只free了头节点那 100 个节点全泄漏了。链表是链式结构只释放头节点并不会自动释放后续节点——每个节点的内存是独立分配的。解决先清空再销毁顺序不能反void clearList(LinkedList head) { Node *p head-next; while (p ! NULL) { Node *temp p; p p-next; free(temp); } head-next NULL; } void destroyList(LinkedList *headPtr) { if (headPtr NULL || *headPtr NULL) { return; } clearList(*headPtr); free(*headPtr); *headPtr NULL; }clearList只释放所有数据节点保留头节点destroyList先清空数据节点再释放头节点本身最后把外部的头指针置NULL。destroyList必须接收LinkedList *而不是LinkedList因为要把调用方手里的头指针改成NULL否则调用方那个指针就成了野指针这和free后置空是同一个道理。5.4 越界访问位置参数超出链表长度现象调用insertAtPos(head, 10, 5)让链表保持不变倒还好调用deleteAtPos(head, 10)直接段错误或者删掉了链表最后一个节点。原因deleteAtPos的循环条件已经是p-next ! NULL越界时p停在最后一个节点此时p-next为NULL条件判断会拦截下来。但如果有人在deleteAtPos里误用了p ! NULL做循环条件p会走到NULL随后判断p-next NULL时直接解引用空指针当场崩溃。insertAtPos越界时则可能把NULL当成前驱执行p-next newNode同样崩。解决每个函数的边界判断写两遍也不为过。插入前判断pos 1遍历后判断p NULL删除前判断pos 1遍历后判断p-next NULL。还要提醒一句位置从 1 开始计数如果调用方从 0 开始传结果会整体错位一位。要是项目里有人习惯了数组下标从 0 开始务必在函数注释里写清楚或者干脆所有位置参数统一从 0 开始看你自己定关键是全项目只认一个约定。6. 验证与调试用最小用例把十九种操作跑通操作写完了怎么证明它是对的我的习惯是写一个最小验证程序把十九种操作按依赖顺序串起来跑一遍每步打印结果出了错能立刻定位到是第几个函数的问题。int main() { LinkedList list initList(); insertAtTail(list, 3); insertAtTail(list, 1); insertAtTail(list, 4); printList(list); insertAtPos(list, 2, 2); printList(list); deleteByValue(list, 3); printList(list); printf(find 4 at: %d\n, findNode(list, 4)); reverseList(list); printList(list); sortList(list); printList(list); insertAtTail(list, 2); sortList(list); removeDuplicates(list); printList(list); LinkedList other initList(); insertAtTail(other, 0); insertAtTail(other, 5); LinkedList merged mergeLists(list, other); printList(merged); destroyList(merged); destroyList(list); destroyList(other); return 0; }这个验证流程按依赖排序先建表再插入和删除再查找再逆置、排序、去重、合并最后销毁。每一行打印都对应一个操作的结果如果findNode打印的pos不对说明前面插入的位置逻辑错了如果逆置后打印顺序是 2、1、3说明head-next prev那步漏了。用gdb调试时重点盯head-next和每个节点的next地址打印p-data辅助判断但不要只看data两个节点的data相同不代表链表结构对。我的个人习惯是保留这份最小用例每次改完链表代码就先跑一遍比重新翻实验报告快得多。链表这东西手写一遍会了就是会了后面学到二叉树、图很多遍历思路还是从链表这里长出来的。希望这些操作和踩坑记录能帮到你。本文还有配套的精品资源点击获取