单链表这东西说简单也简单说容易翻车那也是真的容易翻车。C面试八股里它是常客考研408数据结构第一课也是它真正写底层引擎、网络库、游戏组件的时候链表节点的变形更是到处都是。这篇文章我不想再讲那些烂大街的“概念图示”而是直接给你一套完整可编译的C单链表实现源码从设计思路到每一个操作为什么这么写再到最容易崩的边界全部拆开讲清楚。不管你是刚学指针的新手还是准备面试想快速复习的老手照着这份源码敲一遍再对照我后面列的问题自查比你死记十遍定义都管用。1. 设计思路与方案选型1.1 标准库都有链表了为什么还要手写有人说C标准库不是有std::forward_list吗单链表现成的还自己造什么轮子。这话分两头说。工程上能用标准库我当然用标准库但问题是单链表这个数据结构几乎是所有高阶数据结构的基石你要是连它的指针链接关系都没亲手捋过后面学二叉树、图、跳表、LRU缓存的时候全都是一笔糊涂账。面试官让你手写一个链表的反转你不是不会STL你是不理解指针指向谁、谁应该指向谁这就暴露基本功了。另一个容易被忽略的原因是std::forward_list的接口设计得非常“别扭”它只有push_front、emplace_after、splice_after这些很多新手拿到手根本不知道怎么用更别说改造成一个能配合内存池、自定义分配器的底层结构了。真正面向底层的代码往往需要你自己定义节点布局、控制内存生命周期这时候拿标准容器硬套反而费劲。手写一个单链表不是为了重复造轮子是为了让你拥有“在需要的时候能徒手造轮子”的能力。1.2 节点结构和类接口怎么设计更顺手先说节点。我用的还是经典的struct Node里面就两个成员一个是数据域一个是next指针。为什么用struct不用class因为节点是一个纯数据载体它不需要封装、不需要私有成员struct默认public成员语义上更简洁直接。构造函数我写了初始化列表并且加了explicit防止出现隐式类型转换带来的意外。你可能会觉得这是小题大做但代码规范这东西越小的细节越能看出一个程序员的习惯。再谈链表类。我对外暴露的操作包括头插、尾插、按位置插入、按值删除、按位置删除、查找、反转、打印、清空、获取大小。这些基本覆盖了日常绝大多数使用场景。类内部我保留了一个size_成员很多教材的实现是不维护这个的遍历一遍就能算出来但我还是建议维护。有了它带下标的插入删除可以直接做范围检查getSize()可以做到O(1)成本只是每次插入删除时改一下计数器几乎可以忽略不计。这是典型的“用一点空间换代码简洁度”的思路。1.3 裸指针还是智能指针别被“现代C”带偏我知道现在的风气是猛推智能指针一个unique_ptr下去内存都自动释放了多香。但具体到单链表这个场景我建议你第一遍老老实实用裸指针配合手工析构理由有两个。第一unique_ptrNode存next指针会让节点变成递归持有结构链表一旦很长析构时容易因为递归展开过深导致栈溢出你需要特地去改成循环释放这比自己管理裸指针还绕。第二智能指针的get、reset写满代码之后指针的指向语义被隐藏了新手反而看不明白到底谁指向谁学不到东西。至于shared_ptr单链表这种单一归属权的结构用不上多个对象共享同一个节点你一删除链表另一个持有者就拿着悬空指针隐患更大。我的结论很朴素学单链表阶段就该用裸指针把内存管理的每一步都看清楚。等你把析构写对、把拷贝构造写好再回头看智能指针实现理解就深了。这不是拒绝现代C这是训练基本功的必经阶段。2. 核心操作实现解析2.1 构造、析构、拷贝先把内存账算明白一个链表类如果内存管理没搞定后面写再多功能都是虚的。我按三个问题来说怎么建立、怎么销毁、怎么复制。默认构造很简单头指针置空size置0。空链表不需要任何头节点占位这也是单链表和循环链表的一个区别。析构函数直接调clear()从头节点开始遍历每一步都必须先保存cur-next然后delete cur。为什么必须这么干因为你一旦释放掉当前节点它里面的next指针就悬空了再访问就属于未定义行为程序可能当场崩也可能隔了好久才出错这种问题最难查。所以正确顺序永远是先记下后路再动手拆。拷贝构造和赋值运算符是最多新手翻车的地方。C编译器默认生成的拷贝构造是浅拷贝两个链表对象点同一个头节点运行起来看着好像没问题直到其中一个析构了另一个访问那块已释放的内存——恭喜你拿到了一个野指针。我的做法是深拷贝遍历源链表的每个节点逐个pushBack到新链表形成完全独立的内存结构。赋值运算符多了一步自赋值判断先clear()自己再重建这样反复赋值也不会崩。2.2 插入操作指针变更顺序差一步就全乱头插pushFront是整个链表里最容易让人想当然的操作。新节点入链第一步必须是newNode-next head_把新节点的next指向当前头节点第二步才是head_ newNode。这个顺序反了会发生什么head_先指向了新节点原链表头就找不到了你的链表直接丢掉了一大串节点。别看教科书写了无数遍实际写代码的时候真有人犯这个错原因就是没理解“指针是联系不是本体”这件事。尾插pushBack的逻辑分支在空链表和非空链表之间。空链表直接让head_指向新节点非空链表从头遍历到最后一个节点把它的next接到新节点上。如果不维护尾指针尾插就是O(n)的这是单链表的天然代价。后面我会说如果你高频尾插可以考虑增加tail_尾指针这是后话。按位置插入insert(pos, val)我的下标约定从0开始允许插入到等于链表长度的位置等效尾插。这里我偷了个懒pos 0的情况直接调用pushFront省去了单独处理头部的麻烦。其他情况先移动到pos-1位置的节点此时它一定存在新节点接在它后面就行。这个写法把“头部特殊分支”抹平了不少代码也更容易读对。2.3 删除操作前驱指针一旦弄丢链表就断了删除节点是单链表里产生bug的重灾区核心原因在于这是一个只能“往后看”的数据结构你想摘掉当前节点必须知道它前面那个节点是谁。遍历的时候你一路顺着next走当前节点的前驱悄悄就从手里溜走了。所以删除操作的核心就是额外维护一个prev指针跟着cur同步移动。按值删除remove(val)的逻辑我拆成了两步。遍历找到匹配节点后先判断prev是否为空为空说明删的就是头节点直接把head_移到cur-next不为空的话让prev-next cur-next。重新接好链条之后再delete cur--size_。这里最容易漏掉的就是头部那个if分支很多人只写了prev-next cur-next一测试发现删除头节点时链表纹丝不动就是没处理prev nullptr的情况。按位置删除removeAt(pos)的思路类似只是多一个前置条件pos必须落在合法区间内。有了size_这个检查写起来非常顺。删除头节点时用临时指针toDelete head_head_ head_-next其他位置则走到pos-1处找到前驱再摘除目标节点。无论哪种情况记得把toDelete释放掉。2.4 反转链表三个指针画一遍就通了链表反转是面试高频题也是检验指针理解的经典题目。我的实现用的是迭代三指针不新建任何节点原地把next方向全部掉头空间复杂度O(1)。逻辑我推演给你看以1 - 100 - 5 - 7 - nullptr这个链表为例这是上面删除3之后的实际链表。第一轮循环开始前prev nullptrcur指向1。进入循环先用next cur-next把100保存下来然后让cur-next prev也就是1的next变成nullptr再把prev移到1cur移到100。第二轮next保存5cur-next指向1链表方向从100 - 5变成100 - 1prev变成100cur变成5。这样一路推进最后一轮cur指向7时next nullptr7-next 5prev 7cur nullptr循环结束。最后把head_ prev链表就成了7 - 5 - 100 - 1 - nullptr。这个推演过程建议你自己在纸上画一遍。我看到太多人背代码背了忘忘了背根因就是不理解这三指针的交接过程。画一遍之后你会彻底明白反转的本质就是逐个把节点的next指针从“指向后一个”改成“指向前一个”。3. 完整源码与测试3.1 完整可编译源码下面是完整的实现我把它放在一个list_demo.cpp里环境只要有支持C11的编译器就行VS2019、GCC 8、Clang都可以。源码里面包含了深拷贝、赋值运算符、增删查改、反转、打印你直接复制到本地编译就能跑。#include iostream struct Node { int data; Node* next; explicit Node(int val) : data(val), next(nullptr) {} }; class SinglyLinkedList { public: SinglyLinkedList() : head_(nullptr), size_(0) {} ~SinglyLinkedList() { clear(); } SinglyLinkedList(const SinglyLinkedList other) : head_(nullptr), size_(0) { Node* cur other.head_; while (cur) { pushBack(cur-data); cur cur-next; } } SinglyLinkedList operator(const SinglyLinkedList other) { if (this ! other) { clear(); Node* cur other.head_; while (cur) { pushBack(cur-data); cur cur-next; } } return *this; } void pushFront(int val) { Node* node new Node(val); node-next head_; head_ node; size_; } void pushBack(int val) { Node* node new Node(val); if (head_ nullptr) { head_ node; } else { Node* cur head_; while (cur-next) { cur cur-next; } cur-next node; } size_; } bool insert(int pos, int val) { if (pos 0 || pos size_) { return false; } if (pos 0) { pushFront(val); return true; } Node* cur head_; for (int i 0; i pos - 1; i) { cur cur-next; } Node* node new Node(val); node-next cur-next; cur-next node; size_; return true; } bool remove(int val) { if (head_ nullptr) { return false; } Node* prev nullptr; Node* cur head_; while (cur) { if (cur-data val) { if (prev nullptr) { head_ cur-next; } else { prev-next cur-next; } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; } bool removeAt(int pos) { if (pos 0 || pos size_ || head_ nullptr) { return false; } Node* toDelete head_; if (pos 0) { head_ head_-next; } else { Node* prev head_; for (int i 0; i pos - 1; i) { prev prev-next; } toDelete prev-next; prev-next toDelete-next; } delete toDelete; --size_; return true; } bool contains(int val) const { Node* cur head_; while (cur) { if (cur-data val) { return true; } cur cur-next; } return false; } void reverse() { Node* prev nullptr; Node* cur head_; while (cur) { Node* next cur-next; cur-next prev; prev cur; cur next; } head_ prev; } void clear() { Node* cur head_; while (cur) { Node* next cur-next; delete cur; cur next; } head_ nullptr; size_ 0; } void print() const { Node* cur head_; while (cur) { std::cout cur-data - ; cur cur-next; } std::cout nullptr std::endl; } int getSize() const { return size_; } bool empty() const { return head_ nullptr; } private: Node* head_; int size_; }; int main() { SinglyLinkedList list; list.pushBack(3); list.pushBack(5); list.pushBack(7); list.print(); // 3 - 5 - 7 - nullptr list.pushFront(1); list.print(); // 1 - 3 - 5 - 7 - nullptr list.insert(2, 100); list.print(); // 1 - 3 - 100 - 5 - 7 - nullptr list.remove(3); list.print(); // 1 - 100 - 5 - 7 - nullptr list.reverse(); list.print(); // 7 - 5 - 100 - 1 - nullptr SinglyLinkedList copy(list); copy.removeAt(1); copy.print(); // 7 - 100 - 1 - nullptr SinglyLinkedList assigned; assigned list; assigned.print(); // 7 - 5 - 100 - 1 - nullptr std::cout size of list: list.getSize() std::endl; // 4 std::cout contains 100: (list.contains(100) ? yes : no) std::endl; // yes return 0; }3.2 测试用例与运行输出上面的main函数妥妥是一份简单的冒烟测试。我特意让用例覆盖了这么几个点尾插和头插的混合顺序是否正确、中间位置插入是否接对了链、删除一个中间节点后链条是否完整、反转后是不是完全倒序、拷贝构造出来的链表是不是独立内存copy.removeAt(1)不会影响list、赋值运算符能否正确重建。运行输出我标在代码的注释里了完整的输出如下3 - 5 - 7 - nullptr 1 - 3 - 5 - 7 - nullptr 1 - 3 - 100 - 5 - 7 - nullptr 1 - 100 - 5 - 7 - nullptr 7 - 5 - 100 - 1 - nullptr 7 - 100 - 1 - nullptr 7 - 5 - 100 - 1 - nullptr size of list: 4 contains 100: yes如果你跑出来和这个不一致恭喜你发现了最好的学习机会——先不要急着往下读按我后面第三节的内容去排查一遍。3.3 复杂度对照不同操作的账本学链表必须建立复杂度直觉不然你永远不知道该在什么场景用它。我整理了一个简洁的对照表并同时列出std::vector作为对比这样选型的时候一眼就能看明白。操作单链表本实现std::vector说明头插O(1)O(n)链表优势区vector需要搬移全部元素尾插O(n)无尾指针O(1)均摊高频尾插建议给链表加tail_尾指针按下标访问O(n)O(1)vector绝对优势链表只能遍历按值删除O(n)O(n)都需要先查找链表删除本身O(1)空间每个节点多一个指针可能有多余容量链表在频繁插删场景下内存利用率更高你发现没有链表真正的优势场景是“在已知位置频繁插入删除”比如LRU缓存的淘汰逻辑、就绪队列的动态调度这时候数组类的连续存储根本扛不住频繁搬移。理解了这个取舍面试时被问到“链表和数组的区别”你就能说出结构化答案而不是只背概念。4. 常见问题与调试心得4.1 段错误和多发的空指针问题写链表代码最熟悉的一个英文单词可能就是Segmentation fault了我之前也说过这类问题九成是空指针或者悬空指针解引用。举几个我实际带人过程中反复出现的例子。第一个remove遍历时没有判断链表为空直接取head_-data空链表上来就崩。第二个print函数把循环条件写成while (cur-next)而不是while (cur)结果最后一个节点永远打印不到虽然不崩但结果是错的。第三个clear里先delete cur再去访问cur-next这是典型的悬空指针前面已经强调过了。排查这类问题的思路我建议大家不要到处乱写printf看值而是学会用调试器。在VS里打断点监视窗口里直接看head_、cur这个指针的值一步步单步执行看哪一步开始不对Linux下用gdbp cur打印指针p *cur看节点内容观察next是否指向了一个明显不合理的地址。养成这个习惯之后你的调试效率比靠猜快一个量级。4.2 内存泄漏和检测工具漏写析构函数或者某个分支忘了delete在Windows或Linux的命令行小demo里看不出来但放到服务端程序或者游戏主循环里就是灾难内存占用只会一路往上走直到进程被系统杀掉。这个账必须用工具来算。Linux下我是这么做的valgrind --leak-checkfull ./list_demo跑完之后重点看最后的LEAK SUMMARY如果有什么definitely lost的行它还会告诉你丢失的字节数和对应的调用栈。一个很有效的训练方法是先把析构函数注释掉运行一次看valgrind报出多少节点泄漏再把析构函数恢复再跑一次直到清零。这个对比能让你对“每个new都必须配对delete”建立肌肉记忆。Windows下VS调试器配合_CrtDumpMemoryLeaks也有内存泄漏报告或者用Dr. Memory这个开源工具图形界面对新手更友好。4.3 边界条件自测清单我在教别人的时候经常说一句话链表代码写出来不算本事边界条件全过才算。下面这张表是我自己写链表必跑的用例你也可以打印出来写完代码一条条对着过。场景期望行为空链表调用remove返回false不崩溃删除恰好是头节点head_正确变成原第二个节点删除恰好是尾节点前驱的next变成nullptr链表只有一个节点删除它head_变成nullptrsize_变成0insert到负数下标返回false链表不变insert到下标等于链表长度等效于尾插成功拷贝一个空链表得到空链表析构不异常reverse空链表/单节点链表链表不变连续多次remove同一个不存在的值每次返回falsesize_不变我见过太多人平时操作一切正常一到“单节点删除”、“空链表反转”这种边上就翻车。其实面试官最爱捅的就是这几个地方你把这张表跑熟了心态上就先赢了一半。4.4 继续扩展的方向如果这个版本的实现你已经能独立写出来、并跑通所有边界条件了我建议趁热打铁做三个小升级每个都能让你对指针的理解再上一个台阶。第一改成带哨兵头节点的版本。哨兵节点不存数据永远站在链表最前面好处是删除、插入时不再需要专门处理“头部为空/头部就是目标”这种分支代码会简洁很多。第二改成循环链表。头节点的next指向尾节点遍历终止条件从nullptr变成“回到起点”这个转换非常考验对指针链接的理解。第三加入tail_尾指针让尾插变成O(1)同时比较一下删除尾节点时维护尾指针带来的额外复杂度。这三个练完你再去碰双向链表、二叉树这些结构会发现里面的套路都是相通的。最后说一点个人体会。链表这东西看一百遍PPT都不如亲手敲一遍、再亲手调一遍错。我见过最快的成长方式就是把自己写的源码故意改坏几个地方然后用调试器把这些bug一个个揪出来。你错过一次“先delete再访问next”你一辈子都不会再犯。源码我给你了自测清单也给你了剩下的就是打开编辑器把代码敲进指关节里。 C++单链表实现源码全解析：设计思路、内存管理与边界调试
单链表这东西说简单也简单说容易翻车那也是真的容易翻车。C面试八股里它是常客考研408数据结构第一课也是它真正写底层引擎、网络库、游戏组件的时候链表节点的变形更是到处都是。这篇文章我不想再讲那些烂大街的“概念图示”而是直接给你一套完整可编译的C单链表实现源码从设计思路到每一个操作为什么这么写再到最容易崩的边界全部拆开讲清楚。不管你是刚学指针的新手还是准备面试想快速复习的老手照着这份源码敲一遍再对照我后面列的问题自查比你死记十遍定义都管用。1. 设计思路与方案选型1.1 标准库都有链表了为什么还要手写有人说C标准库不是有std::forward_list吗单链表现成的还自己造什么轮子。这话分两头说。工程上能用标准库我当然用标准库但问题是单链表这个数据结构几乎是所有高阶数据结构的基石你要是连它的指针链接关系都没亲手捋过后面学二叉树、图、跳表、LRU缓存的时候全都是一笔糊涂账。面试官让你手写一个链表的反转你不是不会STL你是不理解指针指向谁、谁应该指向谁这就暴露基本功了。另一个容易被忽略的原因是std::forward_list的接口设计得非常“别扭”它只有push_front、emplace_after、splice_after这些很多新手拿到手根本不知道怎么用更别说改造成一个能配合内存池、自定义分配器的底层结构了。真正面向底层的代码往往需要你自己定义节点布局、控制内存生命周期这时候拿标准容器硬套反而费劲。手写一个单链表不是为了重复造轮子是为了让你拥有“在需要的时候能徒手造轮子”的能力。1.2 节点结构和类接口怎么设计更顺手先说节点。我用的还是经典的struct Node里面就两个成员一个是数据域一个是next指针。为什么用struct不用class因为节点是一个纯数据载体它不需要封装、不需要私有成员struct默认public成员语义上更简洁直接。构造函数我写了初始化列表并且加了explicit防止出现隐式类型转换带来的意外。你可能会觉得这是小题大做但代码规范这东西越小的细节越能看出一个程序员的习惯。再谈链表类。我对外暴露的操作包括头插、尾插、按位置插入、按值删除、按位置删除、查找、反转、打印、清空、获取大小。这些基本覆盖了日常绝大多数使用场景。类内部我保留了一个size_成员很多教材的实现是不维护这个的遍历一遍就能算出来但我还是建议维护。有了它带下标的插入删除可以直接做范围检查getSize()可以做到O(1)成本只是每次插入删除时改一下计数器几乎可以忽略不计。这是典型的“用一点空间换代码简洁度”的思路。1.3 裸指针还是智能指针别被“现代C”带偏我知道现在的风气是猛推智能指针一个unique_ptr下去内存都自动释放了多香。但具体到单链表这个场景我建议你第一遍老老实实用裸指针配合手工析构理由有两个。第一unique_ptrNode存next指针会让节点变成递归持有结构链表一旦很长析构时容易因为递归展开过深导致栈溢出你需要特地去改成循环释放这比自己管理裸指针还绕。第二智能指针的get、reset写满代码之后指针的指向语义被隐藏了新手反而看不明白到底谁指向谁学不到东西。至于shared_ptr单链表这种单一归属权的结构用不上多个对象共享同一个节点你一删除链表另一个持有者就拿着悬空指针隐患更大。我的结论很朴素学单链表阶段就该用裸指针把内存管理的每一步都看清楚。等你把析构写对、把拷贝构造写好再回头看智能指针实现理解就深了。这不是拒绝现代C这是训练基本功的必经阶段。2. 核心操作实现解析2.1 构造、析构、拷贝先把内存账算明白一个链表类如果内存管理没搞定后面写再多功能都是虚的。我按三个问题来说怎么建立、怎么销毁、怎么复制。默认构造很简单头指针置空size置0。空链表不需要任何头节点占位这也是单链表和循环链表的一个区别。析构函数直接调clear()从头节点开始遍历每一步都必须先保存cur-next然后delete cur。为什么必须这么干因为你一旦释放掉当前节点它里面的next指针就悬空了再访问就属于未定义行为程序可能当场崩也可能隔了好久才出错这种问题最难查。所以正确顺序永远是先记下后路再动手拆。拷贝构造和赋值运算符是最多新手翻车的地方。C编译器默认生成的拷贝构造是浅拷贝两个链表对象点同一个头节点运行起来看着好像没问题直到其中一个析构了另一个访问那块已释放的内存——恭喜你拿到了一个野指针。我的做法是深拷贝遍历源链表的每个节点逐个pushBack到新链表形成完全独立的内存结构。赋值运算符多了一步自赋值判断先clear()自己再重建这样反复赋值也不会崩。2.2 插入操作指针变更顺序差一步就全乱头插pushFront是整个链表里最容易让人想当然的操作。新节点入链第一步必须是newNode-next head_把新节点的next指向当前头节点第二步才是head_ newNode。这个顺序反了会发生什么head_先指向了新节点原链表头就找不到了你的链表直接丢掉了一大串节点。别看教科书写了无数遍实际写代码的时候真有人犯这个错原因就是没理解“指针是联系不是本体”这件事。尾插pushBack的逻辑分支在空链表和非空链表之间。空链表直接让head_指向新节点非空链表从头遍历到最后一个节点把它的next接到新节点上。如果不维护尾指针尾插就是O(n)的这是单链表的天然代价。后面我会说如果你高频尾插可以考虑增加tail_尾指针这是后话。按位置插入insert(pos, val)我的下标约定从0开始允许插入到等于链表长度的位置等效尾插。这里我偷了个懒pos 0的情况直接调用pushFront省去了单独处理头部的麻烦。其他情况先移动到pos-1位置的节点此时它一定存在新节点接在它后面就行。这个写法把“头部特殊分支”抹平了不少代码也更容易读对。2.3 删除操作前驱指针一旦弄丢链表就断了删除节点是单链表里产生bug的重灾区核心原因在于这是一个只能“往后看”的数据结构你想摘掉当前节点必须知道它前面那个节点是谁。遍历的时候你一路顺着next走当前节点的前驱悄悄就从手里溜走了。所以删除操作的核心就是额外维护一个prev指针跟着cur同步移动。按值删除remove(val)的逻辑我拆成了两步。遍历找到匹配节点后先判断prev是否为空为空说明删的就是头节点直接把head_移到cur-next不为空的话让prev-next cur-next。重新接好链条之后再delete cur--size_。这里最容易漏掉的就是头部那个if分支很多人只写了prev-next cur-next一测试发现删除头节点时链表纹丝不动就是没处理prev nullptr的情况。按位置删除removeAt(pos)的思路类似只是多一个前置条件pos必须落在合法区间内。有了size_这个检查写起来非常顺。删除头节点时用临时指针toDelete head_head_ head_-next其他位置则走到pos-1处找到前驱再摘除目标节点。无论哪种情况记得把toDelete释放掉。2.4 反转链表三个指针画一遍就通了链表反转是面试高频题也是检验指针理解的经典题目。我的实现用的是迭代三指针不新建任何节点原地把next方向全部掉头空间复杂度O(1)。逻辑我推演给你看以1 - 100 - 5 - 7 - nullptr这个链表为例这是上面删除3之后的实际链表。第一轮循环开始前prev nullptrcur指向1。进入循环先用next cur-next把100保存下来然后让cur-next prev也就是1的next变成nullptr再把prev移到1cur移到100。第二轮next保存5cur-next指向1链表方向从100 - 5变成100 - 1prev变成100cur变成5。这样一路推进最后一轮cur指向7时next nullptr7-next 5prev 7cur nullptr循环结束。最后把head_ prev链表就成了7 - 5 - 100 - 1 - nullptr。这个推演过程建议你自己在纸上画一遍。我看到太多人背代码背了忘忘了背根因就是不理解这三指针的交接过程。画一遍之后你会彻底明白反转的本质就是逐个把节点的next指针从“指向后一个”改成“指向前一个”。3. 完整源码与测试3.1 完整可编译源码下面是完整的实现我把它放在一个list_demo.cpp里环境只要有支持C11的编译器就行VS2019、GCC 8、Clang都可以。源码里面包含了深拷贝、赋值运算符、增删查改、反转、打印你直接复制到本地编译就能跑。#include iostream struct Node { int data; Node* next; explicit Node(int val) : data(val), next(nullptr) {} }; class SinglyLinkedList { public: SinglyLinkedList() : head_(nullptr), size_(0) {} ~SinglyLinkedList() { clear(); } SinglyLinkedList(const SinglyLinkedList other) : head_(nullptr), size_(0) { Node* cur other.head_; while (cur) { pushBack(cur-data); cur cur-next; } } SinglyLinkedList operator(const SinglyLinkedList other) { if (this ! other) { clear(); Node* cur other.head_; while (cur) { pushBack(cur-data); cur cur-next; } } return *this; } void pushFront(int val) { Node* node new Node(val); node-next head_; head_ node; size_; } void pushBack(int val) { Node* node new Node(val); if (head_ nullptr) { head_ node; } else { Node* cur head_; while (cur-next) { cur cur-next; } cur-next node; } size_; } bool insert(int pos, int val) { if (pos 0 || pos size_) { return false; } if (pos 0) { pushFront(val); return true; } Node* cur head_; for (int i 0; i pos - 1; i) { cur cur-next; } Node* node new Node(val); node-next cur-next; cur-next node; size_; return true; } bool remove(int val) { if (head_ nullptr) { return false; } Node* prev nullptr; Node* cur head_; while (cur) { if (cur-data val) { if (prev nullptr) { head_ cur-next; } else { prev-next cur-next; } delete cur; --size_; return true; } prev cur; cur cur-next; } return false; } bool removeAt(int pos) { if (pos 0 || pos size_ || head_ nullptr) { return false; } Node* toDelete head_; if (pos 0) { head_ head_-next; } else { Node* prev head_; for (int i 0; i pos - 1; i) { prev prev-next; } toDelete prev-next; prev-next toDelete-next; } delete toDelete; --size_; return true; } bool contains(int val) const { Node* cur head_; while (cur) { if (cur-data val) { return true; } cur cur-next; } return false; } void reverse() { Node* prev nullptr; Node* cur head_; while (cur) { Node* next cur-next; cur-next prev; prev cur; cur next; } head_ prev; } void clear() { Node* cur head_; while (cur) { Node* next cur-next; delete cur; cur next; } head_ nullptr; size_ 0; } void print() const { Node* cur head_; while (cur) { std::cout cur-data - ; cur cur-next; } std::cout nullptr std::endl; } int getSize() const { return size_; } bool empty() const { return head_ nullptr; } private: Node* head_; int size_; }; int main() { SinglyLinkedList list; list.pushBack(3); list.pushBack(5); list.pushBack(7); list.print(); // 3 - 5 - 7 - nullptr list.pushFront(1); list.print(); // 1 - 3 - 5 - 7 - nullptr list.insert(2, 100); list.print(); // 1 - 3 - 100 - 5 - 7 - nullptr list.remove(3); list.print(); // 1 - 100 - 5 - 7 - nullptr list.reverse(); list.print(); // 7 - 5 - 100 - 1 - nullptr SinglyLinkedList copy(list); copy.removeAt(1); copy.print(); // 7 - 100 - 1 - nullptr SinglyLinkedList assigned; assigned list; assigned.print(); // 7 - 5 - 100 - 1 - nullptr std::cout size of list: list.getSize() std::endl; // 4 std::cout contains 100: (list.contains(100) ? yes : no) std::endl; // yes return 0; }3.2 测试用例与运行输出上面的main函数妥妥是一份简单的冒烟测试。我特意让用例覆盖了这么几个点尾插和头插的混合顺序是否正确、中间位置插入是否接对了链、删除一个中间节点后链条是否完整、反转后是不是完全倒序、拷贝构造出来的链表是不是独立内存copy.removeAt(1)不会影响list、赋值运算符能否正确重建。运行输出我标在代码的注释里了完整的输出如下3 - 5 - 7 - nullptr 1 - 3 - 5 - 7 - nullptr 1 - 3 - 100 - 5 - 7 - nullptr 1 - 100 - 5 - 7 - nullptr 7 - 5 - 100 - 1 - nullptr 7 - 100 - 1 - nullptr 7 - 5 - 100 - 1 - nullptr size of list: 4 contains 100: yes如果你跑出来和这个不一致恭喜你发现了最好的学习机会——先不要急着往下读按我后面第三节的内容去排查一遍。3.3 复杂度对照不同操作的账本学链表必须建立复杂度直觉不然你永远不知道该在什么场景用它。我整理了一个简洁的对照表并同时列出std::vector作为对比这样选型的时候一眼就能看明白。操作单链表本实现std::vector说明头插O(1)O(n)链表优势区vector需要搬移全部元素尾插O(n)无尾指针O(1)均摊高频尾插建议给链表加tail_尾指针按下标访问O(n)O(1)vector绝对优势链表只能遍历按值删除O(n)O(n)都需要先查找链表删除本身O(1)空间每个节点多一个指针可能有多余容量链表在频繁插删场景下内存利用率更高你发现没有链表真正的优势场景是“在已知位置频繁插入删除”比如LRU缓存的淘汰逻辑、就绪队列的动态调度这时候数组类的连续存储根本扛不住频繁搬移。理解了这个取舍面试时被问到“链表和数组的区别”你就能说出结构化答案而不是只背概念。4. 常见问题与调试心得4.1 段错误和多发的空指针问题写链表代码最熟悉的一个英文单词可能就是Segmentation fault了我之前也说过这类问题九成是空指针或者悬空指针解引用。举几个我实际带人过程中反复出现的例子。第一个remove遍历时没有判断链表为空直接取head_-data空链表上来就崩。第二个print函数把循环条件写成while (cur-next)而不是while (cur)结果最后一个节点永远打印不到虽然不崩但结果是错的。第三个clear里先delete cur再去访问cur-next这是典型的悬空指针前面已经强调过了。排查这类问题的思路我建议大家不要到处乱写printf看值而是学会用调试器。在VS里打断点监视窗口里直接看head_、cur这个指针的值一步步单步执行看哪一步开始不对Linux下用gdbp cur打印指针p *cur看节点内容观察next是否指向了一个明显不合理的地址。养成这个习惯之后你的调试效率比靠猜快一个量级。4.2 内存泄漏和检测工具漏写析构函数或者某个分支忘了delete在Windows或Linux的命令行小demo里看不出来但放到服务端程序或者游戏主循环里就是灾难内存占用只会一路往上走直到进程被系统杀掉。这个账必须用工具来算。Linux下我是这么做的valgrind --leak-checkfull ./list_demo跑完之后重点看最后的LEAK SUMMARY如果有什么definitely lost的行它还会告诉你丢失的字节数和对应的调用栈。一个很有效的训练方法是先把析构函数注释掉运行一次看valgrind报出多少节点泄漏再把析构函数恢复再跑一次直到清零。这个对比能让你对“每个new都必须配对delete”建立肌肉记忆。Windows下VS调试器配合_CrtDumpMemoryLeaks也有内存泄漏报告或者用Dr. Memory这个开源工具图形界面对新手更友好。4.3 边界条件自测清单我在教别人的时候经常说一句话链表代码写出来不算本事边界条件全过才算。下面这张表是我自己写链表必跑的用例你也可以打印出来写完代码一条条对着过。场景期望行为空链表调用remove返回false不崩溃删除恰好是头节点head_正确变成原第二个节点删除恰好是尾节点前驱的next变成nullptr链表只有一个节点删除它head_变成nullptrsize_变成0insert到负数下标返回false链表不变insert到下标等于链表长度等效于尾插成功拷贝一个空链表得到空链表析构不异常reverse空链表/单节点链表链表不变连续多次remove同一个不存在的值每次返回falsesize_不变我见过太多人平时操作一切正常一到“单节点删除”、“空链表反转”这种边上就翻车。其实面试官最爱捅的就是这几个地方你把这张表跑熟了心态上就先赢了一半。4.4 继续扩展的方向如果这个版本的实现你已经能独立写出来、并跑通所有边界条件了我建议趁热打铁做三个小升级每个都能让你对指针的理解再上一个台阶。第一改成带哨兵头节点的版本。哨兵节点不存数据永远站在链表最前面好处是删除、插入时不再需要专门处理“头部为空/头部就是目标”这种分支代码会简洁很多。第二改成循环链表。头节点的next指向尾节点遍历终止条件从nullptr变成“回到起点”这个转换非常考验对指针链接的理解。第三加入tail_尾指针让尾插变成O(1)同时比较一下删除尾节点时维护尾指针带来的额外复杂度。这三个练完你再去碰双向链表、二叉树这些结构会发现里面的套路都是相通的。最后说一点个人体会。链表这东西看一百遍PPT都不如亲手敲一遍、再亲手调一遍错。我见过最快的成长方式就是把自己写的源码故意改坏几个地方然后用调试器把这些bug一个个揪出来。你错过一次“先delete再访问next”你一辈子都不会再犯。源码我给你了自测清单也给你了剩下的就是打开编辑器把代码敲进指关节里。