学链表这件事几乎每个写代码的人都经历过一个相似的时刻书上的图看懂了箭头画的明明白白可一旦自己动手写指针就开始不听话——插完结点整个表断了、删完结点打印乱码、逆置完只剩一个元素。我当年第一次手写单链表调试了整整一个下午最后发现是插入时两行赋值顺序写反了。这篇文章就把单链表从结构体定义到逆置、从插入删除到内存释放完整拆一遍代码以 C 语言为主关键处补上 C 结构体写法和 Python 的实现对照适合正在啃数据结构、准备实验报告或者想搞清楚指针到底在内存里干了什么的人。下面这份是能直接编译运行的原码不是伪代码。1. 数组明明够用为什么还要手写一条单链表很多人心里都有这个疑问int a[100]用得挺顺随机访问还是 O(1)为什么教材非要花一整章讲链表。答案不在能不能用在代价落在哪。数组的本质是一块连续内存它的所有优点和缺点都从连续这两个字来。随机访问快是因为下标乘元素大小就能算出地址插入删除慢也是因为要保持连续插一个元素后面的全部得往后挪。你往一个十万元素的数组头部插一个数就要搬十万次内存。链表反过来结点散落在堆上靠指针串起来头部插入删除只要改几个指针代价是丢掉随机访问能力想找第 i 个必须从头一个个数过去。维度顺序表数组单链表按下标访问O(1)O(n)头部插入删除O(n)整体搬移O(1)改指针尾部插入摊还 O(1)满了要扩容有尾指针 O(1)否则 O(n)内存分布连续缓存友好离散指针跳转多额外开销预留空间或扩容余量每个结点一个指针扩容方式realloc 搬迁天然按需一个结点一次 malloc这张表里最容易被忽略的是内存分布那一行。链表的渐进复杂度看着很美可实际跑起来往往没理论那么快原因是 CPU 缓存。数组的顺序访问能命中缓存行链表每跳一次指针可能就是一次缓存未命中数据量大时差距很明显。所以真实工程里数组用的远比链表多std::vector能覆盖绝大多数场景链表更像是特定场景的补充。那什么时候真该用链表我总结几个典型一是插入删除极其频繁、且位置已知比如实现 LRU 缓存淘汰需要 O(1) 把某个结点挪到头部用哈希表加双向链表是标准解法二是数据量动态且无法预估上界又不想承担扩容搬迁成本三是作为更复杂结构的骨架哈希表的拉链法、图的邻接表、内存分配器的空闲块链底层都是链表。所以手写单链表不是学个古董是在打地基。还有一层现实原因面试和考试。链表反转、找环、找中间结点、合并两个有序链表这些题考的不是你会不会写链表是你能不能把指针变量的每一步想在前面。王道数据结构里链表那几道题本质上都在训练同一件事——移动指针前先想清楚哪些信息马上要用、哪些可以丢。这个思维习惯一旦养成后面写任何涉及引用的代码都会稳很多。我建议的学习路径是先照着本文把一趟能跑的代码敲出来跑通插入删除逆置再合上书自己默写一遍最后去刷那几道经典题。只在书上画箭头是学不会链表的。2. 链表结点的结构体定义与它在内存里的真实样子真正卡住初学者的第一步往往是那行看起来有点怪的typedef。把它拆开看其实一点都不复杂。2.1 LNode 和 LinkList 是同一个结构体的两个名字typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;这里做了两件事。第一定义了结构体标签struct LNode成员是数据域data和指针域next。第二typedef一次给出两个别名LNode等价于struct LNodeLinkList等价于struct LNode *。所以后面写LNode *p和写LinkList p是一回事只是习惯上用LinkList强调这是一条链表的头指针用LNode *强调这是指向某个结点的指针。有个新手一定会踩的点为什么next要写成struct LNode *next不能直接写LNode *next。因为结构体内部自引用时typedef的别名LNode还没生效——结构体的定义还没结束编译器根本不知道LNode是什么。必须用带struct标签的写法这是 C 语言的规则。到了 C 里这条限制放开了可以直接写LNode *next这也是很多人看 C 代码时觉得更顺的原因。2.2 一次 malloc 到底申请了多少字节LNode *s (LNode *)malloc(sizeof(LNode));sizeof(LNode)是多少在我的 64 位机器上data是 int 占 4 字节next是指针占 8 字节。按理说 12 字节但实际输出是 16 字节——中间多出来的 4 字节是编译器做的内存对齐填充目的让 8 字节的指针落在 8 的倍数地址上CPU 访问更快。这个细节有两个实际影响。一是malloc返回的是void *C 里其实可以不写强制转换但写上更清楚C 里则必须写C 不做隐式 void* 转指针。二是千万别自己去凑字节数永远用sizeof(LNode)。我见过有人图省事写malloc(12)结果在 64 位机器上指针域被截断程序跑起来随机崩溃这种 bug 能查到你怀疑人生。拿到结点后要做两件事填数据s-data e;接指针s-next NULL;或指向后继。新建的结点指针域一定要初始化否则它是个野指针指向一块随机内存后面free它或者顺着它遍历就是灾难。2.3 头指针、头结点、首元结点别混为一谈这三个词很多人第一次学就绕晕我用一句话说清头指针是一个变量存着链表第一个结点的地址头结点是这块地址指向的结点它不存有效数据一般是哑结点首元结点才是第一个真正存数据的结点。LinkList L; // L 是头指针变量 InitList(L); // 让 L 指向一个头结点带头结点之后链表的结构是头指针 L → 头结点data 不用→ 首元结点 → ... → 最后一个结点最后结点的next是 NULL。空链表的判断变成了L-next NULL因为头结点永远存在头指针永远不为空。多花一个结点图什么图的是操作统一。不带头结点时空表用L NULL判断在第一个位置插入或删除都要特判——你得改头指针本身带头结点后第一个位置和其它位置的插入删除逻辑完全一样都是在某个结点后面插、删某个结点的后继代码少一堆if。这是工程上很典型的用一个哑结点换代码简洁。代价也有多一次malloc多占一个结点的内存遍历时要注意从L-next开始而不是L。教材和大多数工程实现都选带头结点我后面给的源码也是带头结点的版本。3. 建表这件事头插法和尾插法差在顺序上建表就是把一堆数据变成一条链表。看着简单但两种建法的区别恰好暴露了链表的一个核心性质。3.1 头插法天然的逆序机器头插法的逻辑是每来一个新元素就把它插到头结点后面也就是当前链表的最前面。void ListHeadInsert(LinkList L) { ElemType x; LNode *s; while (scanf(%d, x) 1 x ! 9999) { s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next L-next; // 新结点指向原来的首元结点 L-next s; // 头结点指向新结点 } }关键就两行顺序同样不能反先让新结点的next挂上老链表再让头结点指向新结点。如果你输入 1 2 3建出来的链表是 3 2 1正好反着。这个特性不是巧合它本身就是最省事的链表逆置手段等下第 5 节会用到。头插法还有一个隐含好处——不需要判空也不需要尾指针代码极短。缺点是结果逆序很多时候你不想这样。3.2 尾插法加个尾指针就没那么难受尾插法顺着正序来新结点接到链表末尾。问题是如果你每次都要从头遍历找到尾巴建一条 n 个元素的表就是 O(n²)这不能忍。解决办法是加一个尾指针r始终指向当前最后一个结点。void ListTailInsert(LinkList L) { ElemType x; LNode *s, *r L; // r 一开始指向头结点 while (scanf(%d, x) 1 x ! 9999) { s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; r-next s; // 老尾巴接上新结点 r s; // 尾指针后移 } r-next NULL; // 收尾别漏 }r-next NULL这行是新手最容易漏的。你要是不写最后一个结点的next就是malloc那块内存里的垃圾值遍历时会顺着它跑到不知道哪里去打印出一串乱码然后段错误。这个坑我踩过一次当时百思不得其解为什么前几个数都正常最后一个崩——就是尾巴没封口。输入结束的哨兵值 9999 是教材常用套路实际写程序最好用scanf的返回值判断或者干脆传入一个数组和长度别依赖魔法数字。用9999当哨兵万一数据里真有 9999 就被截断了这种 bug 很隐蔽。3.3 两种建法的选择如果你需要输入顺序等于链表顺序用尾插法。如果你碰巧需要一个逆序结果用头插法白捡一个逆置。我个人在写题时如果构建完还要逆置会直接用头插法省一次遍历如果构建完要顺序遍历或做别的操作就用尾插法加尾指针。没有绝对优劣看你下一步要干什么。4. 查找、插入、删除指针操作的顺序不能反着来这是整篇里最需要专注的部分因为链表 80% 的 bug 都出在这里。核心原则只有一条在断开旧连接之前先把要用的信息存下来。4.1 按位查找的边界从 0 开始是有意的LNode *GetElem(LinkList L, int i) { if (i 0) return NULL; int j 0; LNode *p L; while (p ! NULL j i) { p p-next; j; } return p; }注意这里j从 0 开始初始p指向头结点。这样设计的结果是GetElem(L, 0)返回头结点GetElem(L, 1)返回首元结点。为什么把第 0 个定义为头结点因为插入和删除都需要找前驱。要在第 i 个位置插入实际是在第 i-1 个结点后面插调用GetElem(L, i-1)就行。当 i 等于 1 时GetElem(L, 0)正好返回头结点插入逻辑统一了不需要对第一个位置特判。如果你把边界改成从 1 开始返回首元结点那么处理 i1 的插入就要单独写一段。这就是接口设计影响调用方复杂度的典型例子。循环结束条件p ! NULL不能省它是防止 i 超出表长时越界的关键。当 i 大于表长循环会在p变成 NULL 时停下函数返回 NULL调用方检查 NULL 就知道位置非法。按值查找更简单从L-next开始挨个比对LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) p p-next; return p; }返回 NULL 表示没找到。返回的是结点指针而不是下标这也体现了链表——你拿到结点指针后如果要在它后面插删是 O(1) 的而顺序表你得重新试下标。4.2 插入的两行赋值顺序反了链表直接断bool ListInsert(LinkList L, int i, ElemType e) { if (i 1) return false; LNode *p GetElem(L, i - 1); if (p NULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return false; s-data e; s-next p-next; // 第一步 p-next s; // 第二步 return true; }画个图就明白了插入前是p → q。第一步让s-next指向q第二步让p-next指向s结果是p → s → q正确。如果你反过来先执行p-next s那么p的后继变成了s原来的q已经没人指了这时再执行s-next p-next其实是让s指向自己链表从s往后全部丢失q及其后面所有结点变成泄漏的孤儿内存。这就是我开头说的我调试了一下午的那个 bug。记忆口诀新结点先接线老前驱后接线。永远先动s再动p。4.3 删除结点free 之前必须先把后继存好删除第 i 个结点同样是先找它的前驱。bool ListDelete(LinkList L, int i, ElemType *e) { if (i 1) return false; LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) return false; LNode *q p-next; // q 是被删结点 *e q-data; // 先把数据带出去 p-next q-next; // 前驱跳过 q先接上后继 free(q); // 最后才释放 return true; }顺序上的死规矩是free(q)必须是最后一步。一旦free了q那块内存就归还给系统了q-next的值还能读出来纯属运气正规说法叫释放后使用行为未定义可能正常可能崩溃可能在别的场景下读出错误数据。所以必须先把q-next赋给p-next把链表接好再free。另外p-next NULL这个判断千万留着它防的是删除位置超过表长的情况——此时p可能就是最后一个结点它没有后继再执行q p-next拿到 NULL*e q-data直接解引用空指针崩溃。4.4 想在某个结点前面插入但你没有前驱怎么办单链表只能往后走所以在给定结点 p 之前插入看起来做不到因为找不到 p 的前驱。教材里给了一个很妙的偷懒写法bool InsertPriorNode(LNode *p, ElemType e) { if (p NULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return false; s-next p-next; // s 插到 p 后面 p-next s; s-data p-data; // 把 p 的数据挪到 s p-data e; // p 换成新数据 return true; }思路是既然没法在 p 前面插那就在 p 后面插一个结点 s然后交换 p 和 s 的数据。逻辑上看p 变成了有数据 e 的结点s 变成了原来 p 的数据相当于 e 出现在 p 原来的位置前面。O(1) 完成很聪明。但这个技巧有个坑必须提醒它改变了 p 结点的数据域。如果外部还有别的指针指向 p或者 p 的地址被记在某个哈希表、索引结构里当 key 用那它的数据被换掉就会引发连锁错误。所以这招只适合p 只在当前函数作用域里被使用的场景别在 map 之类的结构上随便用。这是我做了几年代码之后才真正理解的看起来聪明但要看场合的写法。5. 单链表逆置三个指针到底怎么走位逆置是链表里出现频率最高的操作之一也是最容易写错的。网上有好多写法归根结底就两种思路。5.1 头插法重建最不容易错的版本思路是断开链表把每个结点当成新元素用头插法一个个重新插回头结点后面插完自然逆序。void ReverseByHeadInsert(LinkList L) { LNode *p L-next; // 从首元结点开始 L-next NULL; // 先把链表清空 while (p ! NULL) { LNode *q p-next; // 先存后继因为马上要改 p-next p-next L-next; // 头插第一步 L-next p; // 头插第二步 p q; // 处理下一个 } }这个版本的好处是你复用已经理解的头插逻辑不用重新记指针走位。唯一容易错的地方还是那句q p-next必须在改p-next之前执行因为p-next一改原来的后继就找不回来了。5.2 三指针原地翻转教科书标准写法void ReverseByThreePtr(LinkList L) { LNode *pre NULL; LNode *cur L-next; LNode *nxt; while (cur ! NULL) { nxt cur-next; // 第一步保存后继 cur-next pre; // 第二步指针反向 pre cur; // 第三步pre 前进 cur nxt; // 第四步cur 前进 } L-next pre; // 别忘了接回头结点 }四个步骤的顺序是有讲究的。假如你先把cur-next pre做了再想取cur-next保存后继拿到的已经是pre了后面全部乱掉。所以保存后继必须是循环里的第一件事。pre和cur同步往前走走完时cur变 NULLpre停在原来最后那个结点上它现在是新的首元结点要挂回头结点的next。最后这行特别容易漏漏了头结点后面就是空的打印什么都不显示。我个人的经验是三指针法写三遍就会了但哪怕写熟了也建议每写一次在纸上把三个指针画一遍。因为这个东西一旦出错是静默的——程序不崩就是数据错排查起来比崩溃还烦。5.3 Python 对照换个语言看同一个逻辑热词里有人搜 Python 单链表逆序其实逻辑完全一样只是指针变成了引用。class Node: def __init__(self, val0, nxtNone): self.val val self.next nxt def reverse(head): pre, cur None, head while cur: nxt cur.next cur.next pre pre cur cur nxt return pre对照着看会发现C 和 Python 在这一层的差别只是内存管理。C 里你申请和释放都要自己来指针是裸地址Python 里对象由 GC 管理cur.next pre之后原来那个被覆盖的引用如果没人再指GC 会回收。逻辑结构一模一样。用两种语言各写一遍对理解指针帮助很大因为你不会被free、malloc这些细节分散注意力能专注在指针走位上。6. 释放和调试野指针、内存泄漏、断链这三件事链表代码能跑通只是及格能稳定跑、跑完不泄漏才算过关。6.1 free 之后那一秒最容易出事释放链表要用循环从头结点开始一个个释放注意释放当前结点前先保存下一个。void DestroyList(LinkList *L) { LNode *p *L; while (p ! NULL) { LNode *q p-next; free(p); p q; } *L NULL; // 关键把外部头指针置空 }这里为什么参数用LinkList *L二级指针因为我们不仅要释放结点还要把调用方那个头指针变量置成 NULL。如果只传LinkList L函数内改L NULL只是改了形参副本调用方的头指针还指着一块已经释放的内存这就是野指针的经典来源。后面如果再对它做任何操作都是访问已释放内存。置 NULL 这个动作看起来多余实际很重要。很多空指针崩溃的根源不是空指针本身而是以为已经释放了但指针没置空后面又用了一次。养成释放完立刻置空的习惯能省掉大量排查时间。6.2 内存泄漏最爱藏在提前 return 里内存泄漏是指malloc了但没free。链表里的泄漏大多是两种来源一是插入时malloc成功了但后续逻辑返回没接上链表那块内存就永远找不回来了二是删除时只改了指针没free结点和链表断开了但内存没回收。// 这一段如果有提前返回s 就泄漏了 LNode *s (LNode *)malloc(sizeof(LNode)); s-data e; if (some_check_fail) return false; // s 泄漏 s-next p-next; p-next s;规避方法很简单规范一点先做完所有可能失败的检查通过了再malloc一旦malloc成功后面就到函数结尾中途不再有提前返回。我自己的做法是malloc之后立即补一个 NULL 判断然后一口气把结点接进链表。6.3 断链怎么快速定位链表出问题时最好的调试工具是你自己写的打印函数void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }在每个可能出错的步骤前后各调一次打印看输出在哪一步变得不对就能反推出是哪行指针操作出了问题。如果打印时程序直接崩溃或者输出乱码大概率是断链加野指针也就是某个结点的next指向了已经释放的内存或者随机值。这时候可以改用printf(%p, (void *)p)把结点地址也打出来看看是不是跳到了奇怪的地方。还有一个排查技巧遍历时加一个计数器如果遍历次数超过预期表长还在继续说明链表里成环了——大概率是某处next指回了前面的结点。成环的链表就像迷路走进死循环打印会永远刷下去这时候计数上限判断能救你。现象可能的根因排查切入点打印中途崩溃尾结点 next 未置 NULL检查建表收尾那行元素少了一个free 后使用了已释放内存看删除的顺序顺序错乱插入两行赋值写反检查 s-next 与 p-next 顺序元素无限循环链表成环加计数器检查是否有 next 指回随机崩溃结构体大小被手写数字统一用 sizeof(LNode)7. 一份可直接编译运行的完整原码下面这份代码包含了头文件、建表、查找、插入、删除、逆置、打印、销毁main里给了测试用例。你用gcc main.c -o main编译直接跑就能看到每一步的输出。我特意把两种逆置都留了出来方便你对照。#include stdio.h #include stdlib.h #include stdbool.h typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; /* 初始化建立带头结点的空表 */ bool InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) return false; (*L)-next NULL; return true; } /* 尾插法建表输入 9999 结束 */ void ListTailInsert(LinkList L) { ElemType x; LNode *s, *r L; while (scanf(%d, x) 1 x ! 9999) { s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; r-next s; r s; } r-next NULL; } /* 头插法建表输入 9999 结束结果逆序 */ void ListHeadInsert(LinkList L) { ElemType x; LNode *s; while (scanf(%d, x) 1 x ! 9999) { s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next L-next; L-next s; } } int Length(LinkList L) { int len 0; LNode *p L-next; while (p ! NULL) { len; p p-next; } return len; } /* i0 返回头结点i1 返回第 i 个结点 */ LNode *GetElem(LinkList L, int i) { if (i 0) return NULL; int j 0; LNode *p L; while (p ! NULL j i) { p p-next; j; } return p; } LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) p p-next; return p; } bool ListInsert(LinkList L, int i, ElemType e) { if (i 1) return false; LNode *p GetElem(L, i - 1); if (p NULL) return false; LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return false; s-data e; s-next p-next; p-next s; return true; } bool ListDelete(LinkList L, int i, ElemType *e) { if (i 1) return false; LNode *p GetElem(L, i - 1); if (p NULL || p-next NULL) return false; LNode *q p-next; *e q-data; p-next q-next; free(q); return true; } /* 头插法逆置 */ void ReverseByHeadInsert(LinkList L) { LNode *p L-next; L-next NULL; while (p ! NULL) { LNode *q p-next; p-next L-next; L-next p; p q; } } /* 三指针逆置 */ void ReverseByThreePtr(LinkList L) { LNode *pre NULL; LNode *cur L-next; LNode *nxt; while (cur ! NULL) { nxt cur-next; cur-next pre; pre cur; cur nxt; } L-next pre; } void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } void DestroyList(LinkList *L) { LNode *p *L; while (p ! NULL) { LNode *q p-next; free(p); p q; } *L NULL; } int main(void) { LinkList L; if (!InitList(L)) return -1; int arr[] {1, 2, 3, 4, 5}; for (int i 0; i 5; i) { ListInsert(L, i 1, arr[i]); } printf(原始链表: ); PrintList(L); ListInsert(L, 3, 99); printf(在第3位插入99: ); PrintList(L); ElemType e; if (ListDelete(L, 4, e)) { printf(删除第4位(值 %d): , e); PrintList(L); } printf(查找值 4 的结点: %s\n, LocateElem(L, 4) ? 找到 : 没找到); ReverseByThreePtr(L); printf(三指针逆置后: ); PrintList(L); ReverseByHeadInsert(L); printf(头插法再逆置回来: ); PrintList(L); printf(表长: %d\n, Length(L)); DestroyList(L); printf(释放后头指针: %s\n, L NULL ? NULL : 非空); return 0; }跑出来大概是这样原始链表: 1 2 3 4 5 在第3位插入99: 1 2 99 3 4 5 删除第4位(值 3): 1 2 99 4 5 查找值 4 的结点: 找到 三指针逆置后: 5 4 99 2 1 头插法再逆置回来: 1 2 99 4 5 表长: 5 释放后头指针: NULL输出对上了就说明插入、删除、两种逆置、释放全都正常。你可以把ElemType换成char或者结构体验证一下代码的通用性这也是 C 语言用typedef带来的一点小便利。关于练习我个人最推荐的方法是把上面ListInsert和ListDelete里的那几行核心指针操作删掉凭记忆补全然后跑测试看结果对不对。真正掌握链表的标准不是能看懂而是能默写。另外学有余力可以顺手做这三道经典题它们覆盖了链表里最容易考的几个思维点找中间结点用快慢指针判断有没有环用快慢指针相遇找两个链表的交点先用长度差对齐起点。这三道题做完链表这块基本就通透了。我自己带过几个刚入门的朋友最快掌握链表的路径从来不是看多少讲解是自己写一遍、错一遍、打印一遍、改对一遍。指针这东西脑子里想明白和手上写对之间隔着一整个下午的段错误。所以别怕崩崩了才有信息。