简介面向C语言学习者的一份数据结构链表实例PDF集中演示了链表十九种常用操作的完整写法。资源以单个PDF文件打包体积仅57KB内容精炼、便于下载后随时查阅。目前已吸引734人学习适合正在学习C语言数据结构、特别是链表部分的初学者对照理解也可供备考或复习者快速参考。PDF中的示例代码覆盖了链表创建、遍历打印、结点计数、判空检查、冒泡排序等基础操作同时包含按值或按位置进行查找、修改、插入、删除以及元素交换和整表释放等进阶操作代码附有注释和参考来源结构清晰读者可直接运行或按需修改复用是链表编程练习中一份实用的参考材料。1. 一份能跑的 C 语言单链表十九种操作先说清楚它到底值不值得你花时间C 语言数据结构里链表永远是最绕不开的一块。这份实例代码把单链表的十九种操作全部塞进了一个 .c 文件里从建表、遍历、查长度到按位置查找、按值查找、改值再到头插、尾插、指定位置插入、有序插入、冒泡排序、四种删除、交换节点、整表清空基本把面试和考试里能问到的单链表场景都覆盖了。它适合三类人正在补数据结构基础的学生、准备考研或面试的开发者、以及做嵌入式或单片机开发需要自己维护链表的工程师。但我要先泼一盆冷水这份代码能编译、能运行却藏着好几个看着对、跑起来不对的典型写法比如length参数从头到尾都没刷新过比如指定位置插入在position 1时会插到第二个节点后面。正因为有这些坑它反而比那些完美封装的链表库更适合拿来逐行拆解。我按先看懂内存模型再逐类拆操作最后统一排坑的顺序把它过一遍。2. 动手前先看懂两个关键点节点内存模型与二级指针读这份代码的第一个门槛不是十九个函数而是理解它为什么几乎每个函数都要传Node **pHead。不搞懂这一点后面看insertHeadList和modifyElem时会一直犯迷糊。2.1 节点结构体与内存分配malloc、memset、判空三件套先看节点的定义这是整份代码的地基typedef int elemType; typedef struct NODE { elemType element; /* 数据域存放元素值 */ struct NODE *next; /* 指针域指向下一个节点 */ } Node;typedef int elemType这行值得多说一句。作者没有直接用int element而是先给int起了个别名叫elemType好处是将来想把数据域换成float、换成结构体只需要改这一行后面所有scanf(%d, ...)、printf(%d, ...)的格式符再跟着调一遍就行主逻辑完全不用动。这是一种非常朴素的泛型化思路在课程设计和工程里都很常见比写死int要聪明。再看建表时分配节点的标准动作p1 (Node *)malloc(sizeof(Node)); if (p1 NULL) exit(0); memset(p1, 0, sizeof(Node));这三行是一个组合拳。malloc在堆上分配一块大小为sizeof(Node)的内存返回void *所以要强转成Node *分配失败时返回NULLif (p1 NULL)就是兜底这个情况memset(p1, 0, sizeof(Node))把整块内存清零避免后续读到未初始化的脏数据。提示memset在这里不是必需的但它能消灭一类特别难查的 bug——malloc 出来的内存里next可能是任意值如果忘了赋NULL遍历链表走到末尾时会继续访问一个野地址直接段错误。清零后再人工赋一遍p1-next NULL双保险。2.2 为什么几乎每个函数都传 Node **pHeadC 语言是值传递函数拿到的永远是参数的副本。想在一个函数里改变调用者持有的指针变量本身——比如头插之后让pList指向新节点——只传Node *pHead是做不到的你得传pList的地址也就是Node **pHead。看头插函数最典型void insertHeadList(Node **pHead) { Node *p1; p1 (Node *)malloc(sizeof(Node)); if (p1 NULL) exit(0); memset(p1, 0, sizeof(Node)); printf(Please enter a number to be inserted:); scanf(%d, p1-element); p1-next (*pHead); /* 新节点的 next 指向原来的第一个节点 */ (*pHead) p1; /* 把头指针改写为新节点 */ }p1-next (*pHead)是把新节点串到链表头部但如果不写(*pHead) p1调用者手里的pList仍然指向旧节点新插入的节点就彻底找不到了——这就是传二级指针的原因。用一张简陋的话说一级指针能改指针指向的内容二级指针才能改指针本身指向哪里。在 main 里调用方式是insertHeadList(pList)注意取了地址。而像printList(pHead)这种只遍历、不改链表结构的函数传一级指针就够了因为它只读节点里的数据。2.3 十九种操作按什么规律组织把这十九种操作按职责分类能看出来作者其实是按增删改查 排序的思路写的只是没有刻意归类分类函数核心行为建表/销毁creatList、clearList从无到有、从有到无遍历/查询printList、sizeList、isEmptyList读链表不改结构查找getElement、getElemAddr按下标找、按值找修改modifyElem改指定位置的值插入insertHeadList、insertLastList、isAddPos、OrrderList头插、尾插、按位置插、有序插删除DelHeadList、DelLastList、DelPos、Delx删头、删尾、按下标删、按值删排序/交换Arrange、exchange2pos冒泡排序、交换两个节点的数据这个分类表本身就是一个复习提纲如果你能不看代码把每一行的核心行为自己写出来单链表的基本操作就过关了。后面三章我就按这个顺序把查询、插入、删除、排序里的关键函数逐段拆开讲顺带把参数的含义和边界情况交代清楚。3. 创建链表与基础遍历creatList、printList、sizeList 的完整解读3.1 creatList以输入为正数作为终止条件的建表方式建表函数是整份代码里最容易出内存问题的函数原作者的处理方式很直白——读一个数只要为正就挂进链表读到 0 或负数直接结束建表。void creatList(Node **pHead) { printf(Please enter the list:\n); Node *p1, *p2; p1 p2 (Node *)malloc(sizeof(Node)); if (p1 NULL || p2 NULL) exit(0); memset(p1, 0, sizeof(Node)); scanf(%d, p1-element); p1-next NULL; while(p1-element 0) { if (*pHead NULL) (*pHead) p1; else p2-next p1; p2 p1; p1 (Node *)malloc(sizeof(Node)); if (p1 NULL) exit(0); memset(p1, 0, sizeof(Node)); scanf(%d, p1-element); p1-next NULL; } }这段的流程我拆成四步看第一步先给p1、p2分配第一块内存p1和p2指向同一个节点读入第一个数到p1-element。这里p1 NULL || p2 NULL的写法其实是重复判断因为p1和p2是同一块内存判一个就够了但不影响正确性。第二步进入while(p1-element 0)循环。第一次进来时*pHead NULL直接把p1作为链表的头节点后续进来的数走p2-next p1把新节点挂到当前尾节点后面。p2始终记录已经挂好的最后一个节点p1是正在处理的新节点。第三步挂完当前节点后重新分配一块内存给下一个p1再读一个数。注意这一步p2 p1把新节点的位置记下来但此时p1已经被重新 mallocp2仍然指着链表的尾部。第四步如果下一次读到的数是 0 或负数循环直接退出——但此刻的p1已经分配了内存、读入了不满足条件的数据它没有被挂上链表也没有被free。这就是一个内存泄漏点后面避坑章我会单独讲。参数上要注意scanf(%d, p1-element)要求输入必须是整数中间不能混入字母或符号否则scanf返回 0p1-element保留旧值循环会卡死在你意想不到的地方。3.2 printList 与 sizeList遍历链表的两种写法遍历是单链表最基础的操作打印和数长度本质上是同一件事从头走到尾每经过一个节点做一次处理。void printList(Node *pHead) { if (NULL pHead) printf(The list is empty\n); else while(NULL ! pHead) { printf(%d , pHead-element); pHead pHead-next; } printf(\n); } int sizeList(Node *pHead) { int size 0; while(pHead ! NULL) { size ; pHead pHead-next; } return size; }两个函数都用了同一个遍历模式一个临时指针从头部出发每轮循环读当前节点信息再pHead pHead-next挪到下一个节点直到指针变成NULL。这个模式你得写到肌肉记忆里后面查找、定位、删除无不建立在它之上。printList里有个细节它修改的是形参pHead不是 main 里的pList。pHead是pList的副本函数里把它一路往后挪调用者的指针纹丝不动。这正是值传递的特性——要想遍历链表而不破坏头指针就放心大胆地复用这个形参。sizeList的返回值类型是int链表长度理论上可以超过 21 亿但实际场景里单链表存到这个量级不太现实所以够用。它每次都要从头到尾走一遍时间复杂度 O(n)如果频繁调用开销会累积。3.3 isEmptyList 与初始化检查空表的用法与缺陷void isEmptyList(Node *pHead) { if (pHead NULL) { printf(The list is empty\n); exit(0); } }main 里Node *pList NULL;先把头指针置空然后调creatList(pList)建表再调isEmptyList(pList)检查。问题在于isEmptyList发现空表时直接exit(0)把整个程序干掉了而不是返回一个状态值让调用方决定怎么处理。在单文件 demo 里这种写法能跑但你想把它改造成一个可复用的库函数时就会撞墙——调用方想自己处理空表场景结果程序直接退出了。常见的做法是int isEmptyList(Node *pHead) { return (pHead NULL) ? 1 : 0; }让调用方拿返回值来判断。这是把决策权交还给调用者的设计思想后面第 6 章我会把exit(0)泛滥的问题集中讲。4. 查找、修改与指定位置插入删除六个高频操作的代码级拆解4.1 getElement 与 getElemAddr按下标找元素、按值找位置查找操作有两条路线按下标找值和按值找位置。这两个函数正好各代表一条。void getElement(Node *pHead, int num) { for (int i 1; i num; i) pHead pHead-next; printf(The value of the %dth element is:%d\n, num, pHead-element); }getElement的逻辑是从第一个节点开始走num - 1步到达第num个节点。注意它没有判空也没有判断num是否超出链表长度。如果num大于节点总数pHead会一路挪过NULL循环结束于空指针然后pHead-element直接触发段错误。main 里调用前做了if (n length || n 1)的防护所以单跑这个 demo 没问题但函数本身是裸奔的。getElemAddr的情况更有意思int getElemAddr(Node *pHead, int number) { int i 1; while(pHead ! NULL) { if (pHead-element number) return i; i; pHead pHead-next; } return 0; }函数名和注释都说返回该结点的地址但实际返回的是i——也就是这个值在链表中的序号第几个节点不是内存地址。真正拿到节点地址应该返回Node *类型这里却返回了int。看 main 里的打印语句printf(The location of the number is:%d\n, addr)说明作者自己也是把它当位置用的命名和实现没对齐这是一个容易误导阅读者的点。返回值 0 表示没找到这在设计上是合理的但和地址为 0的语义撞了车换成-1会更明确。4.2 modifyElem 与 insertHeadList改值操作如何不污染头指针修改第n个节点的值看起来很简单作者却做了一个很隐蔽的处理void modifyElem(Node **pList, int addr, int number) { Node *pHead; int i 1; pHead *pList; while(pHead ! NULL) { if (i addr) break; pHead pHead-next; i; } pHead-element number; }关键在第二行pHead *pList先把二级指针解引用一次把链表头指针的值拷贝给局部变量pHead。之后所有遍历操作都走pHead不碰*pList。原代码注释写得很直白在此处如果直接更改 pList 指向的话主函数中调用 printList 就会从 addr 处开始打印——一旦你在遍历中移动了*pList调用者手里的头指针就被改了后面的printList(pList)会从中间某个节点开始打印。这个细节值得背下来凡是拿到Node **pHead的函数想遍历链表时先Node *p *pHead拷贝一份绝对不要动*pHead本身。头插、头删例外那本来就是故意要改头指针。insertHeadList前面已经拆过头插的关键就是记住两句话新节点接管旧链表首节点的身份p1-next *pHead然后头指针更新*pHead p1。malloc出来的节点要记得memset清零避免p1-next残留垃圾值。4.3 isAddPos 与 DelPos指定位置插入删除的前驱定位指定位置插入和删除是链表操作里最容易写错的一对难点全在前驱节点的定位上。void isAddPos(Node **pHead, int length) { Node *p1, *p2; int position, i; printf(Please enter the insert position:); scanf(%d, position); if (position length || position 0) { printf(Input error, the program ends\n); exit(0); } p1 (Node *)malloc(sizeof(Node)); p2 (*pHead); if (p1 NULL) exit(0); memset(p1, 0, sizeof(Node)); printf(Please enter a number to be inserted:); scanf(%d, p1-element); for (i 1; i position - 1; i) p2 p2-next; p1-next p2-next; p2-next p1; }先说正常流程。假设要在第 3 个位置插入p2初始指向第 1 个节点for循环i从 1 到position - 2即 1走一次p2变成第 2 个节点——这就是新节点的前驱。然后p1-next p2-next让新节点指向原来的第 3 个节点p2-next p1让前驱指向新节点插入完成。但position 1时for循环一次都不走p2还指着第 1 个节点执行完插入后链表变成原第 1 个节点 → 新节点 → 原第 2 个节点新节点实际上排在第二位。想让新节点成为新表头必须单独处理position 1的情况走insertHeadList的逻辑。作者没做这个分支判断所以这个函数所谓的指定位置插入对表头位置是失效的。删除指定位置的函数DelPos有同样的问题void DelPos(Node **pHead, int length) { int n, i; Node *p1, *p2; p1 (*pHead); p2 p1-next; printf(Please enter the serial number number to delete:); scanf(%d, n); if (n 1 || n length) exit(0); for (i 1; i n - 1; i) { p2 p2-next; p1 p1-next; } p1-next p2-next; free(p2); }p2被初始化为第 2 个节点p1是第 1 个节点。n 2时循环不走p1是第 1 个节点待删节点的前驱p2是第 2 个节点待删节点p1-next p2-next把第 1 个节点直接链到第 3 个节点然后free(p2)删除成功。但n 1时p1是第 1 个节点待删节点p2是第 2 个节点执行完p1-next p2-next后删除的是第 2 个节点第 1 个节点根本没被释放。想删表头得调DelHeadList。这两处边界错误放一起看特别有意思作者把链表第一个节点默认当成了不可变更的前驱所有定位循环都以它为起点于是 position1 / n1 这两个特例全军覆没。5. 排序、有序插入、交换与清空剩下六个边界操作的实现细节5.1 Arrange不交换节点只交换数据的冒泡排序void Arrange(Node **pHead, int length) { Node *p1; p1 (*pHead); int i, j, temp; for (i length; i 0; --i) { for(j i - 1; j 0; --j) { if ((p1-element) (p1-next-element)) { temp p1-element; p1-element p1-next-element; p1-next-element temp; } p1 p1-next; } p1 (*pHead); } }这是标准冒泡排序的链表实现外层循环控制轮数i从length递减内层循环做相邻比较j决定每轮比较次数。每轮把当前范围内最大的数一路交换到末尾下一轮范围缩小一个节点。p1 (*pHead)在每轮结束重置回头部这是最容易写漏的一行——忘了它下一轮就从错误的位置开始比较了。这个实现刻意选择了交换数据域element而不是交换节点。交换节点需要同时改前驱的next和节点的next涉及三个节点的指针调整在单链表里极易写错。交换数据则简单得多一个temp就够了代价是排序过程中节点之间的相对位置不变只是数据在节点间搬移。对这份 demo 代码来说这个取舍是明智的因为它的目的是演示冒泡排序不是演示链表节点的移动。时间复杂度是 O(n²)空间复杂度 O(1)和数组冒泡排序完全一致。5.2 OrrderList有序链表插入的三种分支int OrrderList(Node **pHead, int length) { Node *p1, *p2; p1 (*pHead); p2 (Node *)malloc(sizeof(Node)); if (p2 NULL) exit(0); memset(p2, 0, sizeof(Node)); printf(Enter the value of the element to be inserted:); scanf(%d, p2-element); if (p2-element p1-element) { p2-next p1; (*pHead) p2; return 1; } while(p1-next ! NULL p2-element (p1-next-element)) p1 p1-next; if (p1-next NULL) { p2-next NULL; p1-next p2; return 1; } else { p2-next p1-next; p1-next p2; return 1; } }有序插入的前提是链表已经排好序这个函数怎么保证这一点靠的是调用顺序——main 里先调Arrange做冒泡排序再调OrrderList插入新元素。函数内部按三种情况分支第一种新值比头节点还小直接走头插逻辑p2-next p1(*pHead) p2新节点成为链表头仍然有序。第二种新值比所有节点都大while循环会一直走到链尾p1停在最后一个节点p1-next NULL成立把新节点挂到尾部有序性保持。第三种新值落在中间while循环在p1-next-element p2-element时停下此时p1是新节点的前驱p2-next p1-next让新节点指向原本 它的那个节点p1-next p2把新节点插入链中。这个函数没判链表为空的情况。如果*pHead是NULL第一行p1 (*pHead)就拿到空指针判断p2-element p1-element会崩溃。空链表上做有序插入正确做法是直接让*pHead p2。作者在 main 里先建表、排序再调用刚好绕开了这个崩溃路径。5.3 exchange2pos 与 clearList交换数据与整表销毁void exchange2pos(Node **pHead, int length) { Node *p1, *p2; int n1, n2, i, j, temp; printf(Please enter the first number:); scanf(%d, n1); printf(Please enter the second number:); scanf(%d, n2); if (n1 1 || n1 length || n2 1 || n2 length) exit(0); p1 p2 (*pHead); for (i 1; i n1; i) p1 p1-next; for (j 1; j n2; j) p2 p2-next; temp p1-element; p1-element p2-element; p2-element temp; }交换两个位置节点的值实现思路和排序如出一辙先各自走到n1、n2对应的节点然后通过temp交换element数据。这里有个隐藏问题如果n1 n2两个循环走到的节点是同一个交换前后值一样不报错但没意义如果n1和n2都传了旧length建表后没刷新边界判断同样是失真的。清空链表是整份代码里少有的每一步顺序都不能反的操作void clearList(Node **pHead) { Node *p1; p1 (*pHead); while(p1 ! NULL) { p1 p1-next; /* 先记住下一个节点的地址 */ free((*pHead)); /* 再释放当前头节点 */ (*pHead) p1; /* 头指针重新指向下一个节点 */ } }顺序反了的后果是先free((*pHead))再取p1-nextp1指向的是一块已经被释放的内存读它的next属于野指针访问。正确姿势永远是先保存下一个节点再释放当前节点最后更新头指针。这个循环结束后链表的每个节点都被free*pHead变为NULL整条链表归零。6. 避坑这份链表实例里最值得记下来的五个常见问题6.1 输入一个非正数就退出creatList 的终止条件是个双刃剑现象建表时输入0或负数链表直接结束创建你想往链表里存一个0值或者负数永远存不进去。原因while(p1-element 0)把正数当成了有效数据的标记0和负数天然被当成结束信号。这在 demo 里没问题但一旦数据域需要支持负数比如温度、差分信号、余额这套逻辑就废了。解决换一个独立的结束标志不再用数据的符号位。常见做法是单独读一行指令——比如输入q或-9999作为终止符或者先问一句是否继续输入。如果坚持用数字做标记至少把结束条件改成读取次数上限比如「最多读 100 个数」循环到了上限强制结束并free掉最后的临时节点。6.2 length 永远不更新插入删除后校验范围全部失真现象先用length sizeList(pList)取了链表长度接着做了一次头插、一次尾插、一次指定位置插入再往后调用isAddPos(pList, length)和DelPos(pList, length)时length还是建表时的老值位置校验和边界判断全线漂移。原因main 里length只被赋值一次后续没有任何一行length sizeList(pList)或者length / length--。插入和删除函数内部也不维护长度信息它们接收的length纯粹是调用方传进来的快照。解决最笨也最可靠的办法是每次操作前先重新sizeList一次工程上一般把链表封装成结构体里面带一个int size字段插入成功size删除成功size--头指针和长度永远绑定在一起。这个实例的选择是快照式 length你复刻它的 demo 时不需要改但移植到别处一定要记住它是会过期的。6.3 insertLastList 拖着一个过期的 length 参数现象连续执行insertHeadList(pList)再insertLastList(pList, length)新节点没有出现在链表末尾而是插到了中间某个位置。原因insertLastList的实现是从头部走n - 1步挂到第n个节点后面它默认链表的长度就是建表时的length。但前一步头插已经让链表多了一个节点旧length指向的不再是表尾。尾插的正确做法根本不需要length直接遍历到p1-next NULL再挂新节点void insertLastList(Node **pHead) { Node *p1, *p2; p2 (*pHead); p1 (Node *)malloc(sizeof(Node)); if (p1 NULL) exit(0); memset(p1, 0, sizeof(Node)); printf(Please enter a number to be inserted:); scanf(%d, p1-element); p1-next NULL; while(p2-next ! NULL) p2 p2-next; p2-next p1; }解决删掉int n这个参数让函数自己走到链表尽头。如果*pHead是空表还得先做一次空表判断直接让*pHead p1。这是链表操作里能用遍历解决就别依赖长度参数的典型教训。6.4 position1 和 n1指定位置插入删除的两个隐蔽死角现象调用isAddPos(pList, length)想插到第一个位置结果是新节点排在第二位原第一个节点跑到最前面调用DelPos(pList, length)想删第一个节点结果删掉的是第二个节点第一个节点还在。原因前面 4.3 节拆解过两个函数的定位循环都从第一个节点是前驱这个假设出发position 1和n 1时循环一次不走逻辑上直接错位。作者显然默认了第一个位置的操作应该由头插/头删函数负责但isAddPos和DelPos的入口校验又放行了1于是这两个边界值落进了一个没人处理的夹缝。解决在函数入口把1单独分流。比如isAddPos里if (position 1) { insertHeadList(pHead); return; }DelPos同理if (n 1) { DelHeadList(pHead); return; }这样1不再是沉默的边界值而是显式转移给专门的函数处理。这个特例分流的思路写任何有边界值的函数都可以套用。6.5 内存泄漏与 exit(0)creatList 退出时那个没人管的 p1现象程序正常跑完用 valgrind 检查时报告definitely lost并且isEmptyList在空表时让整个程序戛然而止。原因creatList的while循环退出时p1已经 malloc 了一块内存但没挂进链表也没有free这块内存成了孤儿。另外这份代码里exit(0)出现在四五个错误分支里它做的是进程级退出不是函数返回——调用方想做后续处理比如打印友好提示都没有机会。解决循环结束后补上释放if (p1 ! NULL) free(p1);把exit(0)改成return错误码或提前返回让调用方决定是否终止程序。一个库函数里出现exit(0)基本等于老子不干了这在课程设计里能接受放到工程里就是灾难。7. 把这份链表代码彻底吃透的三个技巧断点对比、辅助打印与内存扫描看链表代码最容易犯的错是眼睛以为懂了跑起来立刻翻车。我的习惯是拿到一份链表代码先不改逻辑直接上三样工具把它从头到尾验证一遍。第一用 gdb 在关键函数前后给头指针打断点。比如在insertHeadList的*pHead p1这一行打断点先print p1-element看新节点的值再next单步print *pHead确认头指针已经变成新节点。头插最容易犯的错就是忘了*pHead p1这一行断点一打哪里写错了当场现行。gdb 里还可以print pHead-element检查链表中途某个节点的值配合x/4gx pHead看内存里的next指针指向排查节点头尾接错很快。第二写一个dumpList辅助函数每次操作后打印链表当前长度和全部元素。这个函数不用讲究什么算法就是sizeList加printList的合体但它的价值在于让每次操作的结果立刻可见。我习惯在每个printList调用后面再补一行printf(len%d\n, sizeList(pList))这样头插、尾插、删除后长度该变 1 变 1该变 -1 变 -1一眼就能看出length失效的问题。第三把代码编出来跑一遍 valgrind 内存检测这是验证链表内存管理唯一靠谱的手段gcc -g -o linklist linklist.c valgrind --leak-checkfull --show-leak-kindsall ./linklist-g选项让 gcc 生成调试符号valgrind 报错时能精确到源码行号。跑完你会看到definitely lost的块数和字节数对照 6.5 节那个没人释放的p1再回去看代码内存模型的印象会深很多。从那以后我每次拿到别人写的链表代码第一件事不是读逻辑而是先问三个问题哪些函数会改动头指针、长度变量什么时候会过期、每个malloc是不是都有对应的free。这三个问题过完代码里大部分的坑基本都浮出水面了。这份十九种操作的实例你花一小时顺着这个思路走一遍收获会比读十遍教科书都大。希望帮到你。本文还有配套的精品资源点击获取