链表这玩意儿几乎是每个写C的人绕不过去的一道坎。不管是大学里的《数据结构》课还是面试时候的常考题甚至是你工作后维护的某个老项目里它都可能冷不丁地冒出来。我当年第一次手写链表的时候也是被那个-next绕得晕头转向debug到怀疑人生。但后来真正吃透了才发现这东西就像骑自行车会了就是会了而且它背后藏着C里最核心的“内存管理”、“指针操作”和“抽象思维”。这篇东西不是给你念课本我想用实际写代码的方式把单链表和双链表从定义到实现再到那些教科书里不写的“坑”一次性和你聊透。不管你是刚学C的萌新还是想复习一下的老手看完照着敲一遍不敢说你就成大神了但至少面试聊到链表心里能有点底。1. 链表到底是个啥从数组的“痛点”说起聊链表之前得先看看它存在的意义。你可能用过C里的vector或者原生数组这俩本质上都是连续内存空间。连续内存的好处是访问速度快array[5]那直接就是基地址加偏移量一步到位。但坏处也很致命插入和删除操作太难受了。想象一下你有一排占座的椅子中间走了个人你要把后面的人一个一个往前挪一格这就是数组的“删除”。你要是想插队到中间那后面所有兄弟都得往后挪。这在数据量小的时候没啥但如果是十万条数据每插一条都挪一次性能直接就崩了。链表的思路完全反着来。它不要求大家整整齐齐坐一排而是每个元素节点自己随便找地方坐然后用一根线指针把前后的人串起来。你只需要记住第一个节点在哪通过它的指针就能找到第二个第二个的指针找到第三个以此类推。这样做的好处就是插入删除快想在中间插个人只需要扯断前后两根线重新接上就行时间复杂度O(1)。不用挪动任何其他节点。内存分配灵活每个节点可以在堆上单独申请不用一次性申请一整块大内存内存利用率高。当然缺点也有不能随机访问你想找第10个节点得从第1个开始一个个沿着指针走时间复杂度O(n)。而数组是O(1)。额外内存开销每个节点除了存数据还得存一个指针算是一种空间换时间的取舍。这里有的朋友可能会说“那我用vector不就行了它能动态扩容啊。”vector确实是动态数组但它扩容的本质是重新分配一大块内存然后把旧数据拷贝/移动过去。在频繁插入删除的场景下它和链表比还是弟弟。所以没有银弹只有合适的场景。2. 手撕单链表从定义到核心操作先搞最简单的单链表。每个节点就两个部分数据域存数据和指针域存下一个节点的地址。按惯例我们用一个结构体来表示节点。2.1 节点定义与基本框架#include iostream // 定义单链表节点 struct ListNode { int val; // 数据域先拿int练手 ListNode* next; // 指针域指向下一个节点 // 构造函数方便初始化 explicit ListNode(int x) : val(x), next(nullptr) {} };这一小段代码是把链表世界的地基打好了。注意那个explicit关键字这是好习惯防止编译器偷偷用int隐式构造一个临时节点。然后next一定要初始化为nullptr否则它会变成一个野指针指向随机内存地址到时候你访问它程序崩了你都不知道去哪哭。接下来我们需要一个“头”指针它像一个引路牌指向链表第一个节点。整个链表的活动基本都靠这个头指针带路。为了方便管理我习惯封装一个LinkedList类把对节点的操作都收拢到一起不然面对一堆裸指针写操作很容易乱套。class LinkedList { public: LinkedList() : head_(nullptr) {} // 析构释放所有节点内存防止内存泄漏 ~LinkedList() { ListNode* cur head_; while (cur) { ListNode* next cur-next; delete cur; cur next; } head_ nullptr; } // 这里后续会补充各种操作头插、尾插、删除、反转等 private: ListNode* head_; };2.2 插入节点头插法 vs 尾插法插入是链表最基础的操作。面试或者做题的时候头插法用得特别多因为它写起来简洁效率高。头插法新节点插到头部成为新的头节点。void insertFront(int val) { ListNode* newNode new ListNode(val); newNode-next head_; head_ newNode; }思路很简单画个图就是新节点先把它的next指到现在的头节点然后更新头指针为newNode。顺序不能搞反你要是先把head_指到newNode那原来的链表就找不到了直接造成内存泄漏。尾插法新节点插到尾部。这个是大多数人的第一直觉但写起来确实麻烦一点因为你需要从头遍历到最后一个节点。void insertTail(int val) { ListNode* newNode new ListNode(val); if (!head_) { head_ newNode; return; } ListNode* cur head_; while (cur-next) { // 找到最后一个节点 cur cur-next; } cur-next newNode; }在空链表head_是nullptr的情况下要判断一下。这个代码有个值得优化的点如果你经常要尾插可以维护一个tail_指针这样尾插就是O(1)了。当然了我们这是教学代码先保证逻辑清晰性能优化后面再说。2.3 删除节点核心是“引用”思想删除节点是链表操作里戏最多的地方因为你要处理“连接”的关系。我见过很多新手写删除喜欢通过节点指针本身去删除结果发现删着删着指针丢了。其实核心思路就一句话让前一个节点直接绕过要删除的节点。这里我们用之前的prev指针法void removeNode(int val) { // 处理头节点就是要删的情况 if (head_ ! nullptr head_-val val) { ListNode* tmp head_; head_ head_-next; delete tmp; return; } ListNode* prev head_; ListNode* cur head_ ? head_-next : nullptr; while (cur cur-val ! val) { prev cur; cur cur-next; } if (cur) { prev-next cur-next; delete cur; } }这里要注意几点第一个return不能少因为如果头节点被删了整个链表的“地基”就变了必须得更新。其次prev指针要记得在遍历过程中跟随cur同步更新否则你光是cur往前走等找到目标节点了你却不知道它的前一个节点是谁那就麻烦了。如果你觉得写prev太啰嗦还有一个进阶写法用二级指针或指针的引用。我看很多高手喜欢用ListNode** cur head_这样就可以直接把头节点和普通节点统一处理了void removeNodeAdvanced(int val) { ListNode** cur head_; while (*cur (*cur)-val ! val) { cur ((*cur)-next); } if (*cur) { ListNode* tmp *cur; *cur (*cur)-next; delete tmp; } }这个写法初看很反直觉但一旦想明白cur存储的是“某个节点next指针的地址”而head_本身也是头节点next指针的替身两者结构上是一样的代码马上就简洁多了。这个技巧在面试中很加分也能帮你加深对指针本质的理解。2.4 反转链表面试高频思路要会画图反转单链表这题力扣上属于“必须滚瓜烂熟”的级别。我见过无数人背代码结果一让画图就露馅。咱不背咱画图。核心需要一个prev前一个节点、cur当前节点、next后一个节点三个指针。思路是把cur的next指向prev然后三个指针集体往前挪一步直到cur为空。ListNode* reverse() { ListNode* prev nullptr; ListNode* cur head_; while (cur) { ListNode* next cur-next; // 先保存下一个不然断了线就找不到了 cur-next prev; // 反向操作 prev cur; // 更新 prev cur next; // 更新 cur } head_ prev; // 最后 prev 就是新的头节点 return head_; }这个next保存的时机特别关键。你想想你要是不提前保存next在执行完cur-next prev这条语句后cur-next就指向别的地方了你再也找不到原来的下一个节点了链表就断了。我当年学的时候就是因为这一步没想透debug到深夜。3. 双链表加了回头路思路完全不同单链表有个硬伤只能从前往后走。你要是想找某个节点的前一个节点对不起从头再来吧。双链表就是解决这个问题的它每个节点有两个指针next后继和prev前驱。3.1 双链表节点定义与初始化struct DListNode { int val; DListNode* prev; DListNode* next; explicit DListNode(int x) : val(x), prev(nullptr), next(nullptr) {} }; // 为了方便操作我们同样封装一个类这里把头尾都维护上 class DoublyLinkedList { public: DoublyLinkedList() : head_(nullptr), tail_(nullptr), size_(0) {} ~DoublyLinkedList() { DListNode* cur head_; while (cur) { DListNode* next cur-next; delete cur; cur next; } head_ tail_ nullptr; size_ 0; } private: DListNode* head_; DListNode* tail_; int size_; };这边我直接维护了tail_就是吸取了单链表尾插法的教训。既然双链表每个节点都有双向指针那么维护一头一尾会让很多操作变得简单。3.2 双链表的插入别把线扯乱了双链表的插入比单链表要“讲究”因为你要改的指针变多了。不少人写双链表插入链表被改得七零八落。我用一个简单的“在末尾插入”来演示怎么理清思路void insertTail(int val) { DListNode* newNode new DListNode(val); if (!head_) { head_ tail_ newNode; size_; return; } // 关键步骤先连新节点的两条线 newNode-prev tail_; newNode-next nullptr; // 再改老节点的两条线 tail_-next newNode; tail_ newNode; size_; }这里有个小经验改指针的时候先处理新节点的指针因为它不干扰旧结构再处理旧节点的指针。顺序建议是固定的。写双链表最怕的是什么呢是忘记更新tail_或者size_。尤其是size_很多人写的时候图省事不维护结果后面要查长度或者判断边界又得从头遍历那维护这两个指针的意义就没了。3.3 双链表的删除与单链表对比双链表删除的好处是你不一定需要prev指针了因为当前节点自带prev。void removeNode(int val) { DListNode* cur head_; while (cur cur-val ! val) { cur cur-next; } if (!cur) return; // 没找到 // 如果删的是头节点 if (cur head_) { head_ cur-next; if (head_) head_-prev nullptr; } else { cur-prev-next cur-next; } // 如果删的是尾节点 if (cur tail_) { tail_ cur-prev; if (tail_) tail_-next nullptr; } else { cur-next-prev cur-prev; } delete cur; size_--; }写这个的时候我脑子里会一直保持着“头和尾是特殊节点”的意识。你可以看到我没有直接在循环里维护prev而是靠cur-prev去操作这就是双链表的便利之处。4. 避坑指南关于内存、调试和边界条件代码写完只是第一步链表要跑起来不出bug还得看下面这些坑你有没有提前填好。4.1 内存管理的几个“原则”C的链表难点之一就是手动管理内存。你new出来的节点必须得delete掉。下面几条原则是我吃了不少亏总结出来的谁new谁负责delete在封装好的链表类里就是类负责销毁所有节点。先断开再删除删除一个节点先确保它前后节点的线都接好了再把它孤立出来delete。否则你会把其他节点的指针指向一块被释放的内存野指针那是比内存泄漏还要恐怖的问题。delete指针对不是对指针你delete p之后p本身还是个地址值悬垂指针一定要养成习惯及时置空比如delete p; p nullptr;。4.2 调试链表的“土办法”打印大法很多人拿到链表bug喜欢伏案冥想。我建议新手别冥想直接打印。写一个简单的遍历打印函数每一轮操作之后打一遍看输出顺序和预期是不是一样。这种方法虽然“土”但定位指针问题效率极高。void printList() { ListNode* cur head_; std::cout list: ; while (cur) { std::cout cur-val ; cur cur-next; } std::cout std::endl; }实际上等你经验丰富了会使用assert去检查条件或者用带-fsanitizeaddress之类的工具去检测内存错误。但调试初期打印就是最强工具。4.3 常见边界条件速查链表这玩意儿80%的bug都出在边界。每次写完操作默认过一遍这个检测清单链表为空时操作是否安全会不会解引用空指针只有一个节点时操作是否安全头尾指针是否需要同时更新操作的是头部/尾部节点时特殊处理了吗在while循环里指针是否可能跑过头变成了nullptr这四条如果你能每次都自己问一遍刷LeetCode链表题的时候写错率会下降一半。5. 循环链表和进阶实战思路单双链表的基本操作搞定后你完全可以去看循环链表了。循环链表说白了就是把最后一个节点的next不再指向nullptr而是指回头节点。说难不难但你要注意判断结束的条件从“是不是nullptr”变成了“是不是又回到了头节点”。如果判断不准很容易死循环CPU直接跑满。热词里常出现的“单链表的基本操作实验”、“C结构体链表基本语法”都是这个范畴的。所以我不再铺开讲循环链表而是给你一个我认为更有价值的进阶思路使用哨兵节点Dummy Node。哨兵节点就是链表头部放一个“假”节点它不存储有效数据。这样做的好处是头节点永远存在那么头插、头删、遍历就不需要特判“头节点是不是空”了代码逻辑会统一很多非常适合含有大量边界操作的算法题和工程代码。比如说你要删除所有值为val的节点如果带头节点可以直接跑统一逻辑ListNode* removeElements(ListNode* head, int val) { ListNode dummy(0); dummy.next head; ListNode* cur dummy; while (cur-next) { if (cur-next-val val) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; } else { cur cur-next; } } return dummy.next; }这个dummy是写在栈上的不需要new所以不需要delete但是要注意它的析构不会影响链表的其他节点。这种思路在LeetCode题目里出现的频率极高你可以自己尝试用哨兵节点去重写一遍单链表的删除逻辑对比一下代码的优雅程度。6. 聊聊STLC里现成的链表容器作业也写了面试题也刷了最后咱们还是得回归工程现实。C标准库其实早就帮你把链表封装好了就是std::list双向链表和std::forward_list单向链表。很多刚入门的同学会问“明明有现成的容器我为什么还要自己造轮子”我的看法是懂原理才能更好地用工具。你知道了std::list底层是双向链表你就明白为什么它支持push_front、push_back且插入删除都是O(1)复杂度。你知道了它是非连续内存你就明白为什么它没有operator[]不能直接下标访问。你知道了链表的节点是动态分配的你就明白为什么std::list在大量小元素场景下时间和空间的开销可能比std::vector更大。所以说自己手写一遍单双链表不是为了让你在工作中去裸写而是为了让你在看std::list文档时能心领神会在排查性能问题时能判断出瓶颈到底在哪。聊到这链表的实现、操作、注意事项也算是摸了一遍底。我个人在实际操作中最大的体会是链表这种数据结构光看是绝对学不会的。你必须在编译器里头铁地敲一遍敲完又删删完又改改完又崩崩完再查你才会真正跟指针和解。如果你在照着上面的代码敲的时候发现哪里编译不过或者运行时候报段错误不用慌用我上文说的打印大法一步步打出来看一次不行就两次。这个东西过了这道坎以后你在看的任何复杂数据结构都不会再觉得是一座翻不过去的山了。最后多一句嘴如果你用的是VS Code写C记得把tasks.json里的编译器参数加一个-Wall -g编译时能多给你一些警告提示调链表bug的时候这些提示能帮你少踩很多坑。