零基础手写单链表：从内存模型到核心操作全解析-北京尧图网络

链表的魅力就在于它把“内存管理”和“逻辑关系”拆开了。数组的内存是连续的像电影院座位一人挨一人链表的内存是分散的像一队人拉着绳锁链每个人手里抓着下个人的手。这个差别导致了两种数据结构截然不同的性格。这篇文章完全面向零基础假设你刚刚学完C语言的指针、结构体但对“怎么把这些东西用到实际代码里”还比较模糊。我会从内存模型开始把单链表的创建、遍历、插入、删除、反转、释放这些核心操作全部手写一遍并且告诉你每段代码为什么这么写、踩过什么坑。代码我全部在本地环境实测过直接在标准C环境下编译运行即可。1. 动手前的底层认知结构体、指针与内存模型1.1 链表节点到底长什么样在写任何链表操作前先把节点的定义刻在脑子里typedef struct Node { int data; // 数据域存放业务数据 struct Node *next; // 指针域存放下一个节点的地址 } Node;这里的struct Node *next是自引用指针。注意在struct还没定义完整的时候就可以声明指向这种结构体的指针了因为指针的大小是固定的64位系统下8字节编译器不关心它指向的对象完不完整只关心“存地址需要占多少字节”。我见过一些初学者会把next定义成int类型这是错的next存的不是数据是伙伴的地址。也可以把next定义成void *也能跑但后续每次用都要强转污染代码不值得。1.2 链表和数组的本质差异数组int a[5]定义出来内存里就是连续的一段你只要知道首地址就能用下标算出任何一个元素的地址。好处是随机访问快坏处是插入、删除要挪动后面所有元素。链表每个节点是独立malloc出来的内存地址不连续。你找不到第3个节点只能从头节点开始一个个顺着next指过去。这叫顺序访问。但好处是插入、删除只需要改指针指向不需要搬动数据。用生活场景类比一下数组是带编号的储物柜你知道第几号柜子在哪但是柜子之间不能塞新柜子要加一个就得把后面全挪了。链表是狗拉雪橇每只狗脖子上挂着绳子连接后面那只狗你想在中间塞一只狗只需要把前狗的绳子摘下来挂在新狗身上再把新狗的绳子挂到后狗身上其他狗完全不用动。1.3 malloc初始化之后必须做的事很多零基础同学写链表第一步就是malloc然后直接p-data xxx但这会踩到垃圾值的坑。malloc只在内存里划出一块空间并不清空里面的数据。这块空间以前可能被别人用过残留了乱码这时候如果你的代码逻辑里有“判断next是否为NULL”的操作而这些垃圾值里碰巧有个非零值你的链表就会串到不知道哪里去。所以我写链表代码在malloc之后习惯紧跟着初始化Node *p (Node *)malloc(sizeof(Node)); if (p NULL) { // 处理分配失败 return NULL; } p-data 0; p-next NULL;用calloc也行它的确会把分配的内存清零但我个人更习惯malloc 手动初始化原因后面讲指针和释放的时候会说清楚。2. 从零手写单链表核心操作2.1 创建节点与空链表的正确姿势创建一个节点的函数没什么神秘的就是malloc 赋值返回指针Node *createNode(int data) { Node *new (Node *)malloc(sizeof(Node)); if (new NULL) { printf(内存分配失败\n); return NULL; } new-data data; new-next NULL; return new; }现在关键问题来了一个空链表它长什么样是NULL还是包含一个头节点dummy node的结构体这两种风格在教材和实际项目里都常见。初学者我强烈建议用“空指针表示空链表”因为这是最朴素的理解不需要额外的“哨兵位”概念。定义方式Node *head NULL;操作时凡是需要修改head本身的都必须传Node **指向指针的指针因为 C 语言函数传参是值传递你传head进去函数里改的是副本外面不会变。这个点需要特别对待后面插入和删除的时候我会反复强调。如果你项目里用带头节点的写法逻辑上会更统一不用区分“插头部”和“插中间”但入门阶段建议先用不带头节点的把指针的底层逻辑吃透后再切换事半功倍。2.2 头插法从空链表开始建立头插法是指新节点每次都插到链表最前面新节点变成新的头节点。它的代码非常短void insertAtHead(Node **head, int data) { Node *new createNode(data); if (new NULL) return; new-next *head; // 新节点先接住旧头部 *head new; // 更新头部指针为新节点 }为什么要Node **head因为我们要改外界的head指向。你希望函数结束后调用者手里的head变量指向新节点就必须传head本体的地址函数里用*head去修改。对照操作顺序想象一下假设现在链表是A - B - C头在A。你要插入X到最前面第一步让X-next指向A第二步让head指向X。两步顺序不能反过来如果先把head指向X你就丢了A的地址链表断了。很多人第一次写头插法在这个顺序上翻车先在纸上画一遍再动手写。头插法建立链表也有个特点输入顺序是反着的。假如你依次输入1 2 3 4用头插法建立的链表是4 3 2 1。因为后输入的新节点总在最前面。如果业务上需要保持顺序就别用头插法。2.3 尾插法保持顺序的建表方式尾插法是在链表尾部追加节点需要先找到现在的最后一个节点。初学者最容易犯的错是用Node *tail *head直接操作然后函数结束了tail还在原来位置下次又在老地方追加把链表弄丢了。正确的尾插需要一个技巧遍历到最后一个节点然后把它指向新节点void insertAtTail(Node **head, int data) { Node *new createNode(data); if (new NULL) return; if (*head NULL) { *head new; // 空链表时新节点就是头 return; } Node *cur *head; while (cur-next ! NULL) { cur cur-next; // 一路走到最后一个节点next为NULL的节点 } cur-next new; // 挂上新节点 }这段里的while (cur-next ! NULL)很容易被写成while (cur ! NULL)那就出大问题了。假设链表里有3个节点用cur ! NULL循环会一直走到NULL等循环结束cur已经是空指针你根本没法给cur-next赋值编译器直接报错或者更隐蔽的是运行时崩溃。还有一种常见优化在结构体里额外维护一个tail指针每次插入后更新它这样尾插法就是 O(1) 而不是 O(n)。但如果只有一个头指针每次尾插都得从头遍历链表很长的时候效率很让人捉急。业务上如果频繁尾插建议考虑维护 tail如果是学习阶段每次都从头走一遍也无妨思路反而更清晰。2.4 按位置插入找到前驱是关键中间插入是链表操作的第一个小门槛。核心思路是要在第pos个节点前面插入新节点必须先找到第pos - 1个节点前驱节点然后腾挪指针。完整实现从1开始计数pos1表示插到最前面void insertAtPosition(Node **head, int pos, int data) { if (head NULL) return; if (pos 1) { printf(插入位置不合法\n); return; } if (pos 1) { insertAtHead(head, data); return; } Node *new createNode(data); if (new NULL) return; Node *prev *head; int i 1; while (prev ! NULL i pos - 1) { prev prev-next; i; } if (prev NULL) { printf(位置超出链表长度\n); free(new); return; } new-next prev-next; // 新节点先指向原来 prev 的后继 prev-next new; // prev 再指向新节点 }这里的指针操作要严格保持顺序必须先让new-next指向prev-next再更新prev-next new。如果反过来先把prev-next指向new原来的后继节点就找不到了链表就断了。这也是链表操作里最经典的“先接后断”原则先让新加入的节点把后续链条接住再切断旧连接点。每次写这类代码前在纸上画出黑点代表节点、箭头代表next用铅笔去挪比凭空想靠谱得多。2.5 按值查找与修改查找的思路非常简单就是遍历依次比对data和valNode *findByValue(Node *head, int val) { Node *cur head; while (cur ! NULL) { if (cur-data val) { return cur; // 找到返回指针注意这个指针是链表的内部地址 } cur cur-next; } return NULL; // 找不到 }注意这里返回的是节点指针调用方拿到这个指针后理论上可以直接修改node-data。但是要小心如果你把这个节点的地址存下来了然后链表结构发生变化比如这个节点被删除了、被 free 了你手里的指针就成了野指针再去访问就会产生未定义行为。这也是面试里经常追着问的“悬挂指针”。如果你只是想知道第几个节点可以返回位置下标不返回指针。我还写过一个变种链表数据域不是整数而是字符串的时候比较依旧strcmp代码整体逻辑一模一样只是cur-data val这行的判断条件变了。插入到某个指定节点后面也是一种高频操作本质就是改两个指针不需要遍历全表只要指针在手O(1) 就能完成。这个操作看着简单但如果你只拿到目标节点的指针没拿到前驱删除操作是做不了的这就引出了下面这个经典问题。2.6 删除节点前驱指针是生命线删除一个节点核心是“让前驱跳过它直接指向它的后继”然后释放它占用的内存。也就是说你必须知道它的前驱是谁。先写按值删除删除第一个匹配的void deleteByValue(Node **head, int val) { if (*head NULL) return; Node *cur *head; Node *prev NULL; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur NULL) { printf(链表中不存在值为 %d 的节点\n, val); return; } if (prev NULL) { // 要删除的是头节点 *head cur-next; } else { prev-next cur-next; } free(cur); cur NULL; // 建议置空避免误用野指针 }这段代码里的prev就是前驱指针一路跟着cur走当cur停住时prev正好是它的前一个节点。如果prev是NULL说明删除的是头节点那么必须用*head cur-next更新头部。这里也是必须传Node **的场景之一。如果删除的是头节点你不更新调用方的head指针外面的链表就指向了一块已经被free的内存下次一访问就是崩溃级别的 bug。我在 debug 的时候遇到过一次函数里面明明删掉了打印出来却是垃圾值排查了很久才发现是头指针没更新。如果只给你要删除节点的指针不给你头指针那有一个经典技巧叫“狸猫换太子”把后继节点的值拷贝到当前节点然后删除后继。这个方法确实能绕过找不到前驱的问题但它只适用于非尾节点并且有副作用不推荐入门阶段深究。2.7 链表翻转三个指针的万金油链表反转是链表操作里最经典、也最容易让人懵的一个。很多人看过代码觉得懂了一合上书就写不出来原因是没有画图。反转的本质每个节点本来指向后面现在让它指向前面同时头尾互换。头节点指向NULL原来的尾节点成为新头。典型解法是“三指针法”void reverse(Node **head) { if (*head NULL) return; Node *prev NULL; Node *cur *head; Node *next NULL; while (cur ! NULL) { next cur-next; // 1. 先保存当前节点的下一个防止断链 cur-next prev; // 2. 当前节点指向前一个 prev cur; // 3. prev 往前走一步 cur next; // 4. cur 往前走一步 } *head prev; // 循环结束后prev 指向原链表尾节点即新头 }循环体里四句话的顺序极其重要每一句都不能错位。为什么必须先next cur-next因为第二步一执行cur-next就被覆盖了你要是没有提前保存后面的节点地址就丢了剩余链表整体失联。我建议初学者自己在纸上画三个节点搞个箭头模拟这四步操作走两轮就会理解得很快。一次画不清就画三次这个投入绝对划算。还有一种递归反转写法代码极其优雅Node *reverseRecursive(Node *head) { if (head NULL || head-next NULL) return head; Node *newHead reverseRecursive(head-next); head-next-next head; head-next NULL; return newHead; }递归版的核心理解点是先把第二个节点以后的链表反转得到一个新头然后让原第二个节点现在是新链表的尾指向原来的头节点。这行head-next-next head是灵魂。但递归会占用系统栈空间链表很长时可能导致栈溢出工程实现里一般还是优先写迭代版本。2.8 链表长度与打印遍历求长度和打印可以合并成一类都是线性扫一遍。这里有一个容易忽略的细节打印的时候两个节点之间要加分隔符但最后一个不要加我在代码里通常这样处理void printList(Node *head) { if (head NULL) { printf(空链表\n); return; } Node *cur head; while (cur ! NULL) { printf(%d, cur-data); if (cur-next ! NULL) printf( - ); cur cur-next; } printf(\n); }求长度更简单注意计数器加到NULL为止才能包含最后一个节点int listLength(Node *head) { int count 0; Node *cur head; while (cur ! NULL) { count; cur cur-next; } return count; }有些同学会纠结循环条件cur ! NULL和cur-next ! NULL的区别。用cur ! NULL循环会覆盖包括最后一个节点在内的所有节点用cur-next ! NULL循环会在最后一个节点之前停下。打印、求长度必须用前者找尾节点插入用后者区分很清晰。2.9 内存释放防止内存泄漏的收尾工作C 语言没有垃圾回收malloc出来的内存不用了必须free。链表释放的要领是先保存下一个节点的地址再释放当前节点否则你释放掉当前节点后就拿不到下一个节点的地址了。void freeList(Node **head) { Node *cur *head; while (cur ! NULL) { Node *tmp cur-next; // 先记住下一个节点 free(cur); // 释放当前节点 cur tmp; // 移动到下一个节点 } *head NULL; // 防止调用方手里留下野指针 }循环结束后把*head置为NULL。这句话很多人不写结果链表释放后调用方手里还留着一个指向已释放内存的地址万一又走了一遍printList打印出来的是随机垃圾内容非常难排查。Valgrind 是检测内存泄漏的利器Linux 下写链表练习时建议开着它跑一跑。命令很简单valgrind --leak-checkfull ./a.out输出里出现definitely lost就说明有内存没释放对照代码一处一处查。说实话链表这块最容易出现的运行时 bug 基本都集中在内存上比如释放了还在用、用了没释放、释放两次。3. 整合成一个完整可跑的示例3.1 主流程的串联思路光看零散函数不行我来把它们拼成一个可以在本地直接跑起来的程序。这个示例做了这些事建立一个链表、尾插几个节点、在指定位置插入、打印、查找、删除、反转、再打印、最后释放。整个文件大概 160 行左右把上面每个函数原样组装再加上一个main函数就是一个完整的单链表操作演示。我实测在 Linux 下gcc编译零警告通过Windows 下用 Visual Studio 的 C 环境也可以跑。第一个观察点main里需要传入head的场景全部用取地址符。凡是函数内部要修改head本身比如插入头部、头节点删除、反转、释放链表都传head。凡是只读取链表内容的比如打印、查找、求长度直接传head。第二个观察点测试用例要覆盖边界情况。我建议至少测这几种空链表上直接插入、删除不存在的节点、在位置1插入、在超长位置插入、反转只有一个节点的链表。边界条件出错了能让你对代码的理解更深刻。3.2 完整代码与编译运行方式#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int data) { Node *new (Node *)malloc(sizeof(Node)); if (new NULL) { printf(内存分配失败\n); return NULL; } new-data data; new-next NULL; return new; } void insertAtHead(Node **head, int data) { Node *new createNode(data); if (new NULL) return; new-next *head; *head new; } void insertAtTail(Node **head, int data) { Node *new createNode(data); if (new NULL) return; if (*head NULL) { *head new; return; } Node *cur *head; while (cur-next ! NULL) { cur cur-next; } cur-next new; } void insertAtPosition(Node **head, int pos, int data) { if (head NULL) return; if (pos 1) { printf(插入位置不合法\n); return; } if (pos 1) { insertAtHead(head, data); return; } Node *new createNode(data); if (new NULL) return; Node *prev *head; int i 1; while (prev ! NULL i pos - 1) { prev prev-next; i; } if (prev NULL) { printf(位置超出链表长度\n); free(new); return; } new-next prev-next; prev-next new; } void deleteByValue(Node **head, int val) { if (*head NULL) { printf(空链表无法删除\n); return; } Node *cur *head; Node *prev NULL; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur NULL) { printf(链表中不存在值为 %d 的节点\n, val); return; } if (prev NULL) { *head cur-next; } else { prev-next cur-next; } free(cur); cur NULL; } Node *findByValue(Node *head, int val) { Node *cur head; while (cur ! NULL) { if (cur-data val) { return cur; } cur cur-next; } return NULL; } void reverse(Node **head) { if (*head NULL) return; Node *prev NULL; Node *cur *head; Node *next NULL; while (cur ! NULL) { next cur-next; cur-next prev; prev cur; cur next; } *head prev; } void printList(Node *head) { if (head NULL) { printf(空链表\n); return; } Node *cur head; while (cur ! NULL) { printf(%d, cur-data); if (cur-next ! NULL) { printf( - ); } cur cur-next; } printf(\n); } int listLength(Node *head) { int count 0; Node *cur head; while (cur ! NULL) { count; cur cur-next; } return count; } void freeList(Node **head) { Node *cur *head; while (cur ! NULL) { Node *tmp cur-next; free(cur); cur tmp; } *head NULL; } int main() { Node *head NULL; // 尾插建立 1 - 2 - 3 insertAtTail(head, 1); insertAtTail(head, 2); insertAtTail(head, 3); printf(尾插3个节点: ); printList(head); // 头插一个 0 insertAtHead(head, 0); printf(头插0: ); printList(head); // 在位置3插入 99 insertAtPosition(head, 3, 99); printf(位置3插入99: ); printList(head); // 查找 Node *find findByValue(head, 99); if (find ! NULL) { printf(找到节点: %d\n, find-data); } // 删除 0 deleteByValue(head, 0); printf(删除0: ); printList(head); // 反转 reverse(head); printf(整体反转: ); printList(head); printf(链表长度: %d\n, listLength(head)); // 释放 freeList(head); printf(释放后链表: ); printList(head); return 0; }编译运行很简单Linux 下gcc -Wall -o list_demo list_demo.c ./list_demo-Wall选项会把所有警告都显示出来我强烈建议练习阶段全程开着。预期输出尾插3个节点: 1 - 2 - 3 头插0: 0 - 1 - 2 - 3 位置3插入99: 0 - 1 - 99 - 2 - 3 找到节点: 99 删除0: 1 - 99 - 2 - 3 整体反转: 3 - 2 - 99 - 1 链表长度: 4 释放后链表: 空链表注意看“位置3插入99”这一步原链表0 - 1 - 2 - 3插入到第3个位置结果是0 - 1 - 99 - 2 - 399 确实排在了第三位。这里的计数是从1开始的和第2节我的实现一致。再注意反转的细节删除0之后链表是1 - 99 - 2 - 3反转后是3 - 2 - 99 - 1原链表尾节点3成了新头原头1的next指向了NULL。整个指针翻转逻辑完全符合预期。4. 调试技巧与踩坑实录4.1 野指针与内存泄漏最常见的运行时报错野指针在链表开发里是出场率最高的 bug绝大部分是这几种情况导致的malloc之后直接用没有初始化next为NULL。节点被free后外部还有指针指向它且继续访问。传参时用了Node *head而不是Node **head函数里对head的修改不生效外面的head还指向旧地址。插入或删除时指针改的顺序反了导致链表里的next形成错链。我回忆自己最初学链表时零基础阶段最常见的错误是第一种和第三种。第一种的坑在于你以为链表末尾是安全的但其实cur-next存的垃圾值不是NULL继续遍历就可能跑到垃圾地址直接段错误。第三种更魔幻——调试的时候你在函数内部打印链表明明是对的回到main打印又不对半天找不到原因。这时候就要马上意识到“修改没有传地址”。内存泄漏的坑则更隐蔽。C 语言不会主动帮你释放内存free漏了也不报错只是程序运行时间长了内存占用越来越大。用 Valgrind 一测就能看出来。我每次写完链表练习都会主动跑一遍 Valgrind确认输出中没有definitely lost才敢说代码写完了。4.2 链表的“画图调试法”这个方法我想单独拎出来讲因为它是所有链表 debug 技巧里最朴实有效的办法。遇到链表相关的 bug不要先在脑子里空想直接在纸上画出来。每个节点画一个矩形框分成上下两半上半写数据下半写next箭头指向谁。然后照着代码逻辑一步一步去动箭头。比如反转你就从prev NULL开始把箭头一步步改改完一眼就能看出哪里断了、哪里成环了。对于插入删除这种两步操作画完图还会发现一个深层规律凡是插入新节点都先让新节点的next接好后继凡是删除节点先让前驱的next跳过要删的节点。这个“先接后断”原则是从画图里自己悟出来的比死记硬背强一百倍。4.3 常见问题速查表症状可能原因排查方法打印链表死循环链表成环末尾节点的next没置NULL检查所有malloc后的初始化程序段错误访问了已释放内存或野指针用gdb查看崩溃行确认指针是否NULL头插后把头丢了传参没用Node **检查函数签名与调用处是否传入head反转后只剩一个节点反转循环里next cur-next顺序错了用三指针法逐步画图删除后链表断开前驱没有正确跳过被删节点检查prev-next cur-next这行连续两次删除崩了删除后节点没有置NULLfree之后加cur NULL释放链表后打印乱码释放后没把外界head置NULLfreeList末尾加*head NULL4.4 零基础学习者最容易在哪一步放弃根据我带项目的经验零基础同学往往不是卡在“不知道怎么写”而是卡在“不知道写对了没有”。他们写完了、编译通过了但不确定链表操作是否真的是对的。这时候最好的做法是写一个测试程序把每一步都打印出来像我上面那个示例一样跟预期结果逐行比对。测试用例要专门覆盖边界空链表、只有一个节点、删除不存在的值、插入位置超过长度。把这些全部打印出来你就同时在验证逻辑正确性和程序健壮性。还有一点遇到编译错误不要慌。C 编译器给出的报错信息虽然有时候不够友好但绝大多数是“语法错误”或者“未定义标识符”。初学者看到一长串报错容易懵我建议从第一个报错开始看改完一个再编译一个不要试图一口气改完所有的。C 语言这种静态编译的语言报错是程序在保护你而不是在刁难你。5. 从单链表扩展到更复杂结构的路线图学会了单链表之后数据结构这条路上会继续遇到双向链表、循环链表、栈、队列这些本质都是链表思想的变体和组合。双向链表在节点里多了一个prev指针能往后走删除时不需要前驱指针了。循环链表把最后一个节点的next指向头节点适合“约瑟夫环”这类问题。栈和队列如果用链表实现核心就是对链表进行受限的插入删除只允许在头部操作就是栈头部删除尾部插入就是队列。单链表这些操作你都手写过的话它们就是家常便饭了。再往后会学到树结构二叉树的孩子节点就是多叉的next指针递归遍历树的写法跟链表递归反转是一脉相承的。图结构里更进阶一些的“邻接表”也是用链表数组实现的。可以说理解了链表的指针操作就去掉了数据结构里最底层的一个“理解障碍”。我自己练链表时的体会是看十遍不如写一遍写一遍不如跑一遍跑一遍不如耐心从头 build 一遍然后断点调试一份能跑生成的例程。单链表的学习曲线是平缓的难点在于一开始对抽象的内存模型不习惯但只要亲手写熟一个节点结构体、一个插入函数、一个遍历打印那种“怕指针”的感觉很快就消失了。

零基础手写单链表：从内存模型到核心操作全解析

相关推荐

Knowledge Agent Template 生产部署完全指南：环境变量、GitHub App 配置与自托管

Snowy 前端组件 XnTreeSelect：懒加载树选择器与编辑回显完整实战指南

媒体爬虫实战指南：五分钟跑通社交数据

更多资讯

PEEK与PEKK选型指南：从分子结构到工艺窗口的工程实践

TrollStore 装 IPA 卡在 ldid 下载？排查并修复下载源

torchtune 数据集与微调实战：一条样本的四段旅程和六类任务接入详解

MCreator 生物群系水雾颜色（Water Fog Color）参数详解：从界面配置到数据包 JSON 生成原理

Argos Translate离线翻译排错全手册

基于ODConv动态卷积的YOLO26小目标检测与多尺度感知改进

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？