单向链表和双向链表是数据结构里最基础也最常被拿来“摸底”的知识点。面试问考试考实际工程里也到处藏着它们的影子。很多人背得下定义知道“单向有一个指针、双向有两个指针”但一让手写插入删除或者对比两者到底该用哪个就开始含糊了。我写代码这些年被链表指针搞得内存泄漏、程序崩溃也不是一回两回所以这篇文章想从一个实际写代码的角度把单向链表和双向链表的区别、核心操作、选型思路以及那些教科书上不会写的坑一次讲透。不管你是刚学数据结构的在校生还是准备面试的求职者亦或是工作中偶尔要手写底层结构的开发者这篇文章都适合你。我会用C语言为主来讲操作因为它能把指针的每一步都摊开让你看清楚Python的面向对象写法也会顺带提一下方便对比理解。1. 数组用得好好的为什么还要发明链表要理解链表先得知道它解决了数组的什么痛。数组是一片连续的内存空间最大的好处是下标访问arr[5]直接通过地址偏移就能拿到数据时间复杂度是O(1)。但连续有两个麻烦第一在数组中间插入或删除一个元素后面的所有元素都得移动位置平均时间复杂度O(n)数据量大了很伤第二数组一旦创建长度基本固定想扩容得重新分配一大块连续内存再把旧数据拷贝过去代价不低。链表就不玩这套了。它的核心思想是“不连续也照样串起来”每个节点存一份数据再存一个指向下一个节点的指针节点之间通过指针一个个连下去。你不需要一大块连续内存零散的内存块也能用插入删除只需要改指针不需要移动数据。代价是牺牲了随机访问想找第k个节点你得从头一个个跳过去平均O(n)。打个比方数组像电影院的连排座位座位号固定座位之间必须连在一起中途加个人整个一排都得挪链表像火车车厢每节车厢之间用挂钩连起来车厢不要求整齐排列可以散落在各个轨道上增加或卸下一节车厢只需要解开和挂上钩子就行但你想走到第10节车厢只能从车头一节一节走过去没法直接跳过去。链表本身也有多种形态最常见的就是本文要深入讲的单向链表和双向链表。单向链表每个节点只管往后指向前走不了双向链表每个节点多了一个指向前驱的指针前后都能走。除此之外还有循环链表、双向循环链表等变体但理解了基础两种其他都好办。在深入操作之前先把这两种结构的模样和作用在脑子里立起来单向是“一跟到底”双向是“既能往前又能回头”。后面所有操作和对比都围绕着这个根本差异展开。2. 单向链表先从最简单的链式结构动手单向链表是链式结构里最入门但也是最容易写错的一种。它每个节点只有一个next指针操作时你永远只能往下走。很多初学者觉得简单但真要独立写出完整正确的插入、删除、反转还是有不少小坑。下面我们一步一步把代码写出来重点看指针是怎么动的。2.1 结构定义与创建节点在C语言里单向链表的一个节点包含数据域和指针域指针指向下一个节点。定义如下#include stdio.h #include stdlib.h struct Node { int data; struct Node *next; // 指向下一个节点 }; // 创建并初始化一个节点 struct Node* createNode(int val) { struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); if (newNode NULL) { printf(内存分配失败\n); return NULL; } newNode-data val; newNode-next NULL; // 新节点的next先置空避免变成野指针 return newNode; }这里最容易被忽视的就是malloc之后要判断是否分配成功以及一定要把next初始化为NULL。如果next不置空那它就是个随机地址后面遍历的时候程序基本会直接崩掉。在Python里我们用类来模拟同样的结构class Node: def __init__(self, data): self.data data self.next None逻辑完全一样只是Python帮你管理了内存但指针引用的概念仍然存在。我建议学链表先用C语言写一遍因为C语言逼着你想清楚每一步的地址和赋值一旦你被malloc、free、NULL“虐”过后面用其他语言写链表会非常稳。2.2 遍历链表理解“链”是怎么走通的遍历是所有链表操作的基础。思路很简单用一个临时指针cur指向头节点每次检查它是否为空不为空就打印当前节点的数据然后把指针移动到下一个节点。void printList(struct Node* head) { struct Node* cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); }注意这里不要直接移动head。有些新手图省事直接在函数里写head head-next结果函数结束后链表真正的头节点丢了后面数据全乱。正确做法是把head赋值给cur让cur去“跑路”head留在原地。遍历的边界条件也很关键while (cur ! NULL)意味着当链表是空时直接跳过循环如果写成while (cur-next ! NULL)就会漏掉最后一个节点而且空链表会直接访问空指针崩溃。这个细节我见过不少人栽跟头面试手写链表时一定要先想清楚循环条件。2.3 插入操作头插、尾插、指定位置插插入操作是链表里的高频动作按插入位置可以分为头插、尾插和指定位置插入。三种操作的指针变动各有讲究我从最简单的头插开始。头插法把新节点放到链表最前面新节点的next指向原来的头节点然后更新链表的头指针为新节点。struct Node* insertAtHead(struct Node* head, int val) { struct Node* newNode createNode(val); newNode-next head; // 新节点指向旧头 head newNode; // 新节点成为头 return head; // 返回新的头指针给调用者 }为什么这里要返回新的head因为C语言函数参数是值传递你在函数里改head不会影响外面的实参。要改外部变量的值要么用二级指针struct Node**要么把新头返回出来让调用者赋值。两种方式都行但返回新头写法更直观也是很多教材采用的方式。尾插法需要先找到链表最后一个节点然后把它的next指向新节点。注意如果链表为空那新节点就是头节点。struct Node* insertAtTail(struct Node* head, int val) { struct Node* newNode createNode(val); if (head NULL) { head newNode; // 空链表新节点即头节点 return head; } struct Node* cur head; while (cur-next ! NULL) { cur cur-next; } cur-next newNode; return head; }尾插的时间复杂度和遍历一样是O(n)除非你额外维护一个尾指针tail否则每次都要从头走到底。所以如果频繁在尾部插入最好在结构体里同时保存head和tail两个指针。指定位置插入要在第pos个位置插入节点得先找到第pos-1个节点也就是插入位置的前驱。然后让新节点先连上前驱的后继再让前驱的next指向新节点。这两步的顺序非常关键如果反过来先把前驱的next指向新节点那原本后面的节点就丢了。// 在指定下标位置插入下标从0开始。如果位置非法直接返回原头。 struct Node* insertAtPos(struct Node* head, int val, int pos) { // 在头部插入包含空链表和pos0的情况 if (pos 0 || head NULL) { return insertAtHead(head, val); } struct Node* cur head; int count 0; // 找到第pos个位置的前驱即下标pos-1 while (cur ! NULL count pos - 1) { cur cur-next; count; } if (cur NULL) { printf(插入位置越界\n); return head; } struct Node* newNode createNode(val); newNode-next cur-next; // 先让新节点指向后继 cur-next newNode; // 再让前驱指向新节点 return head; }代码里我先判断pos 0或链表为空直接走头插这样就不用单独处理特殊情况然后循环找前驱如果链表都走完了还没到目标位置说明越界。插入时一定要先给新节点接上后路再断开前驱原来的指向这是链表插入的黄金法则。2.4 删除操作改指针绕过去别忘了free删除操作比插入更考验细节因为涉及内存释放。链表删除的核心是让被删节点的前驱直接指向被删节点的后继然后把被删节点释放掉。难点在于找到前驱。删除头节点最简单struct Node* deleteAtHead(struct Node* head) { if (head NULL) return NULL; struct Node* temp head; head head-next; // 头指针后移 free(temp); // 释放原头节点 return head; }删除指定值的节点需要遍历并时刻用一个prev指针记录当前节点的前驱struct Node* deleteByValue(struct Node* head, int val) { if (head NULL) return NULL; // 如果要删的是头节点 if (head-data val) { struct Node* temp head; head head-next; free(temp); return head; } struct Node* cur head; struct Node* prev NULL; while (cur ! NULL cur-data ! val) { prev cur; cur cur-next; } if (cur ! NULL) { prev-next cur-next; // 前驱直接跳过cur free(cur); } else { printf(未找到值为%d的节点\n, val); } return head; }删除头节点和删除中间节点要分开处理因为头节点没有前驱。也可以用一个哨兵节点或二级指针统一逻辑但初学建议先分开写思路最清晰。这里还想分享一个“偷懒”技巧如果给你一个节点指针不是头不是尾且要求O(1)删除该节点其实可以不找前驱。方法是用下一个节点的data覆盖当前节点的data然后把当前节点的next指向下下个节点最后释放下一个节点。本质上删的是“物理上的下一个节点”但值已经替换了。这招在面试题“删除链表中的节点只给待删节点指针”里非常常用但它要求待删节点不能是尾节点因为尾节点没有下一个节点可以替代。2.5 反转链表单向链表最经典的算法题反向遍历是单向链表别扭的地方只能从前向后走。所以“反转链表”几乎成了面试必考题它的解题思路也是链表指针操作中非常典型的一种。迭代法用三个指针pre、cur、next轮流往前走一步步把每个节点的next指向前驱节点。struct Node* reverseList(struct Node* head) { struct Node* pre NULL; struct Node* cur head; while (cur ! NULL) { struct Node* next cur-next; // 先保存下一个节点不然改完next就找不到了 cur-next pre; // 当前节点指向前驱 pre cur; // 前驱后移 cur next; // 当前节点后移 } return pre; // 循环结束时pre就是新的头节点 }为什么一定要先保存next因为当执行cur-next pre之后cur原来的下一个节点就断了联系如果不提前存下来后面就再也走不到原来的链表了。很多初学反转时卡在这一步画个图就明白了实质上是把链表上每一条“链节”调转方向同时整体向左挪动。反转完成后的头节点是原来的尾节点也就是循环结束后的pre。Python里实现同样逻辑几乎一样只是不用管指针类型每次赋值就是引用指向。记住这个三指针迭代模板大部分链表反转变体题比如反转前K个节点都能在此基础上改出来。2.6 查找与修改查找有两种常见需求按值查找和按下标查找。// 按值查找返回第一个匹配节点的指针找不到返回NULL struct Node* findByValue(struct Node* head, int val) { struct Node* cur head; while (cur ! NULL) { if (cur-data val) return cur; cur cur-next; } return NULL; } // 按下标查找下标从0开始越界返回NULL struct Node* findByIndex(struct Node* head, int index) { struct Node* cur head; int count 0; while (cur ! NULL) { if (count index) return cur; count; cur cur-next; } return NULL; }找到节点后修改数据就很简单node-data newVal;。这里有个经验查找操作如果经常做建议考虑哈希表等辅助结构否则链表本身只能线性扫描O(n)在数据量大的时候会很吃力。链表擅长的是“改结构”不擅长“查”这一点在选型时要记住。3. 双向链表多一个指针操作空间立刻不一样双向链表在单向链表的基础上每个节点多了一个指向“前驱”的指针。看起来只是多存了一个地址但带来的能力是质变你可以从任意节点向前走也可以在给定节点指针时O(1)删除它。不过多出来的指针也意味着插入和删除时操作步骤更多、更容易出错。3.1 结构定义C语言里双向链表节点定义struct DNode { int data; struct DNode *prev; // 指向前一个节点 struct DNode *next; // 指向后一个节点 }; // 创建双向链表节点 struct DNode* createDNode(int val) { struct DNode* n (struct DNode*)malloc(sizeof(struct DNode)); n-data val; n-prev NULL; n-next NULL; return n; }和单向链表相比只是多了一个prev指针但所有涉及指针变更的操作都要从“只考虑一个方向”变成“两个方向都要兼顾”。你可以这么理解单向链表是单行道只管往前开双向链表是双行道往前开和后视镜里的车都得留意稍不小心就擦碰。很多语言里也有类似结构比如C STL的listJava的LinkedList底层都是双向链表。它们封装的接口让使用者不用关心指针但理解底层实现仍然很重要毕竟你可能会遇到需要自定义双向链表的时候。3.2 双向链表的插入操作头插法双向链表头插要注意两点第一新节点的prev置为NULL第二如果原链表不为空要把原头节点的prev指向新节点。struct DNode* insertAtHead(struct DNode* head, int val) { struct DNode* n createDNode(val); n-next head; n-prev NULL; if (head ! NULL) { head-prev n; // 原头节点的新前驱 } head n; // 新节点成为头 return head; }尾插法先找到尾节点然后在尾节点后面挂上新节点。注意新节点的prev要指向原尾节点。struct DNode* insertAtTail(struct DNode* head, int val) { struct DNode* n createDNode(val); if (head NULL) { head n; return head; } struct DNode* cur head; while (cur-next ! NULL) { cur cur-next; } cur-next n; n-prev cur; return head; }在指定节点之后插入是双向链表的典型操作比如在节点p后面插入新节点n。这时一共要改4个指针n-next、n-prev、p-next、(p-next)-prev如果原后继存在。顺序建议先处理“连接新节点与后驱”的指针再处理“连接新节点与前驱”的指针尽量避免先修改p-next导致后面节点丢失。void insertAfter(struct DNode* p, int val) { if (p NULL) return; struct DNode* n createDNode(val); n-next p-next; // 新节点指向p的后继 n-prev p; // 新节点的前驱是p if (p-next ! NULL) { p-next-prev n; // 原后继的前驱指向新节点 } p-next n; // p的后继换成新节点 }这段代码的顺序是安全的因为先让新节点和原后继建立了联系这样即使后面处理p-next时原链表的后继已经被n“记住”了不会丢。有些人喜欢先改p-next n;然后再让n-next p-next;结果因为p-next已经变了所以n-next指向了自己链表就成环了。这类错误非常隐蔽调试时不容易发现画图是避免它的最好办法。3.3 双向链表的删除操作不需要找前驱双向链表最核心的优势体现在给定一个节点指针删除它时可以直接通过p-prev拿到前驱不需要像单向链表那样从头遍历寻找前驱因此删除复杂度是O(1)。void deleteNode(struct DNode* p) { if (p NULL) return; if (p-prev ! NULL) { p-prev-next p-next; // 前驱的next直接指向后继 } if (p-next ! NULL) { p-next-prev p-prev; // 后继的prev直接指向前驱 } free(p); }注意这个代码没有处理“如果p是头节点需要更新外部head”的情况。头节点的prev是NULL直接执行p-prev-next会崩溃所以要先判断p-prev是否存在同时如果删的是头节点外部保存head的变量需要被更新为p-next否则头指针就悬空指向一块已释放的内存了。实际工程里处理这类问题常用办法是引入一个额外的“哨兵头节点”dummy它的prev为NULLnext指向真正的第一个节点。这样即使删除链表第一个节点p-prev也永远是有效的指向dummy不用再特判头节点。这个技巧后面讲坑的时候还会再提。3.4 双向链表的遍历与回退双向链表既能正向遍历也能反向遍历。正向和单向一样反向则从尾节点开始不断移动prev指针。要反向遍历需要先拿到尾节点如果只保存了头节点那就得先正向走一遍找到尾节点。void printForward(struct DNode* head) { struct DNode* cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); } void printBackward(struct DNode* tail) { struct DNode* cur tail; while (cur ! NULL) { printf(%d - , cur-data); cur cur-prev; } printf(NULL\n); }在需要回退的场景里双向链表的优势是单向完全不能比的。比如一个编辑器的撤销/重做历史记录用户撤销到某一步又产生新操作时需要快速从当前位置回到上一步双向链表就能做得非常自然。4. 单向 vs 双向一张表看清差异以及如何选择聊完两种链表的操作我们来做一次系统对比。很多初学者纠结“到底该学哪个”“用的时候到底选哪个”其实只要把时间复杂度和内存开销放在一张表里答案就清楚了。4.1 操作复杂度对比操作单向链表双向链表通过头指针头插O(1)O(1)有尾指针时尾插O(1)O(1)给定节点后插入O(1)但通常需先找到该节点O(1)但同样需先找到该节点删除给定指针指向的节点通常O(n)需找前驱用值替换可做到O(1)但不能删尾节点O(1)直接通过prev获得前驱删除尾节点有尾指针O(n)尾指针无法向前还得从头找前驱O(1)tail-prev就是前驱向前遍历不支持O(1)步进查找指定值O(n)O(n)每个节点额外开销1个next指针1个next指针 1个prev指针这张表里最关键的差异就是删除给定节点单向链表要么老老实实O(n)找前驱要么用“偷梁换柱”的技巧来O(1)但技巧有尾巴不能删的局限双向链表则毫无压力地O(1)。尾删除同理在需要频繁删除尾节点的场景双向链表尾指针几乎是标配。4.2 指针维护复杂度多一个指针多一倍出错率从代码书写角度来看双向链表每次插入或删除需要维护的指针数量大概是单向的两倍。单向插入一个节点核心只需改2次指针新节点的next、前驱的next双向则要改4次新节点的prev和next、前驱的next、后继的prev。这不仅仅是代码量增加更重要的是出错概率。我见过很多同学写双向链表插入时不是忘了改p-next-prev就是先改了p-next导致后面的节点找不着。相比之下单向链表拼的是找前驱的耐心双向链表拼的是指针赋值的严密。如果没有很强的指针操作信心建议先在纸上画一个四节点的链表把每一步要改的指针用箭头标出来再动手写代码。4.3 实际选择建议没有一种数据结构是全能最优的选择单向还是双向取决于你的数据访问模式才是真正的答案。内存极度敏感、只需要单向遍历、插入删除集中在头部或已知前驱节点的场景用单向链表。比如哈希表的“链地址法”解决冲突时每个桶里挂的就是单链表如果冲突多可能升级为红黑树但那是另一套话题。再比如图论的邻接表存储每个顶点的出边时也会用单链表来节省内存。需要频繁删除当前节点、需要从尾到头遍历、或者每个节点被外部引用你又想O(1)删除的场景用双向链表。典型的例子是LRU缓存淘汰算法当某个key被访问后要把它移动到链表头部而缓存满了淘汰时又要删除尾节点这时双向链表哈希表是最经典的组合Java的LinkedHashMap底层就是这种思路。另外操作系统的进程调度、线程管理很多地方也用了双向链表来维护进程控制块列表。还有一个折中思路如果不得不做双向遍历但内存又不想翻倍可以考虑“异或链表”这类技巧把前驱和后继的地址异或存进一个指针里省下一个指针空间但代价是运算复杂、代码极难维护通常只在特定嵌入式场景有人用。工程实践中我建议别玩这种花活代码可读性比那点内存重要得多。5. 链表实际应用场景从数据结构课本走向真实世界很多人学完链表觉得它就是个考试概念出了校门用不上。其实链表的应用极其广泛只不过很多时候被上层语言封装成了库函数你感知不到而已。我在这里聊几个最常见的落地场景。队列和栈队列需要先进先出栈需要先进后出链表是它们的天然实现。用单向链表头尾指针就能实现一个高效队列入队从尾插出队从头删都是O(1)。栈更简单只用头插和头删连尾指针都不需要。Python的queue模块、C的stack虽然不一定底层是链表但你完全可以手写一个链表队列来理解原理。LRU缓存这几乎是双向链表最经典的教科书应用。缓存容量有限要快速判断某个key是否存在同时要记录数据的访问时间访问过的数据要提到最前面缓存满时淘汰最久没用的数据。做法是哈希表存key到链表节点的映射链表用双向链表访问一个key时先从哈希表找到链表节点如果存在把它从当前位置移到链表头部插入新key时如果满了删除尾节点并删掉哈希表里的对应项。一切操作都是O(1)关键点在于删除中间某个节点时需要O(1)能力而这正是双向链表的强项。如果换成单向链表删除中间节点就会退化到O(n)整个算法的复杂度就毁了。操作系统内核进程控制块PCB的管理、空闲内存块的追踪、文件系统的磁盘块空闲表都大量使用链表。比如Linux内核中进程列表就是一个双向链表每个进程结构体里都有list_head成员通过它把进程串起来。让进程支持向前向后遍历、快速摘除某个进程双向链表再合适不过。多项式与稀疏矩阵在数学计算里稀疏矩阵的大部分元素是0用二维数组存储会浪费大量空间。一种常见存储方式是“三元组链表”每个非零元素作为一个节点包含行号、列号和值。多项式加法也可以用链表表示每项是一个节点合并同类项就是链表的合并操作。树和图二叉树里的每个节点有left和right两个指针本质上就是一种“双向链表的分支扩展”多叉树则更像多个单向链表的组合。树的前序、中序、后序遍历很多都可以用链表的结构来理解。图的邻接表则是对每个顶点挂一个“边节点”的单链表。所以链表真的不是孤立的它是一切链式结构的地基。编辑器里的文档历史很多文本编辑器的撤销重做功能会用双链表记录编辑操作序列当前操作是链表里的一个节点撤销就是移动到前驱重做就是移动到后继。这时候如果你用单向链表撤销走到了前面就再也走不回来了除非重新遍历双向链表天生适合这种“往前走、往后回”的节奏。6. 链表操作的坑与经验实战中我是怎么排查的操作链表容易出错而且错误往往不太直观。有的是程序崩溃有的是内存泄漏有的是链表悄悄成环表现出来就是在遍历时死循环。下面这些坑基本都是我在自己写代码或者帮别人看代码时遇过的拿出来供你参考。6.1 头指针被“弄丢”的常见原因最经典的问题出现在函数里直接修改了head但在C语言里这种修改不会传回调用者。比如下面这段错误代码void wrongInsertAtHead(struct Node* head, int val) { struct Node* n createNode(val); n-next head; head n; // 只修改了形参外部head依然指向旧头 }调用结束后外面的head没有变新节点找不到了链表也等于没插入。我有次排查了半天最后发现是函数参数传值的老问题。解决办法要么用二级指针void insertAtHead(struct Node** head, int val) { struct Node* n createNode(val); n-next *head; *head n; }要么像前面代码那样返回新的head让调用方接收。如果你在写链表时发现经常丢失第一个节点先检查是不是这里出了问题。6.2 内存泄漏与悬空指针C语言里用malloc创建节点删除时忘了free会导致内存泄漏。长期运行的服务如果一直泄漏内存会一点点涨最后系统崩溃。更危险的是悬空指针free之后没有把指针置NULL并且后续还可能去访问这块内存。因为free只是把堆内存归还并不会把指针变量本身置空指针仍然保存着那块地址此时访问它就会读到随机数据或直接段错误。建议养成好习惯每次删除节点后操作变量的指针要置NULL删除整条链表时用循环逐个释放不要只释放头节点就不管了。比如void freeList(struct Node* head) { struct Node* cur head; while (cur ! NULL) { struct Node* next cur-next; // 先保存下一个节点避免释放当前后无法继续 free(cur); cur next; } }6.3 边界条件检查空链表、单节点、头尾操作链表操作里的“雷区”往往藏在边界。每次写一个操作最好在代码里主动问自己三个问题如果链表是空我的代码会执行什么如果链表只有一个节点我的代码会执行什么如果我要操作的是头节点或尾节点我的代码和操作中间节点是否一样比如在insertAtPos里如果pos等于0我们要走头插如果pos大于链表长度我们要报越界在deleteByValue里如果头节点就是目标要单独处理如果目标是尾节点此时cur-next为NULL所以prev-next cur-next就相当于置空也没问题。但如果你写删除逻辑时不判断cur ! NULL就直接访问cur-next空链表一上来就崩。我自己的办法是写代码前先在草稿纸上列出至少四组测试用例空链表、只有一个节点、两个节点删除头或删除尾、正常多节点。脑子里过了这些用例再动手能躲掉大半的崩溃。6.4 调试链表的好用工具与方法代码写出来不跑一遍谁都不敢保证是对的。链表调试最朴素也最有效的办法是写一个printList函数在每次关键操作后打印一遍链表。这比你用眼睛盯代码盯半天管用多了。我经常在插入、删除、反转之后立刻打印看到链表变成“1 - 2 - 3 - NULL”的形态就能很快定位是哪一步把链给接错了。如果怀疑有环或内存问题Linux下可以用valgrind检查内存泄漏和非法访问valgrind --leak-checkfull ./your_program它会明确告诉你哪一行发生了“invalid read”或“definitely lost”多少字节。Windows下Visual Studio的调试器也可以监视指针但配合画图更直观我会把每个节点的地址、data、next、prev写在本子上模拟程序走到哪一步改成什么样箭头画着画着问题就浮出来了。6.5 插入指针赋值顺序错误导致链表“断链”单向链表在中间插入时正确顺序是先让新节点n-next指向旧后继再让前驱的next指向新节点。反过来呢// 错误示例 cur-next n; // 先改了前驱旧后继找不到了 n-next cur-next; // 此时cur-next已经是n所以n指向了自己这个错误一旦发生链表从cur后面就断了或者你做了一个“自环”遍历时死循环。我之前帮学弟看代码他写的就是这个顺序最后链表输出“1 - 2 - 2 - 2... ”直接刷屏。解决办法除了记熟顺序还可以用一个临时变量保存next节点struct Node* oldNext cur-next; cur-next n; n-next oldNext;这样即使中间打乱了顺序只要oldNext还在链就断不了。6.6 用哨兵节点dummy head统一逻辑最后一个强烈推荐的小技巧在链表最前面加一个不存数据的哨兵节点让真实的头节点变成dummy-next。这样无论插入、删除代码里都可以避免“如果头节点为空”“如果删除的是头节点”这类特殊判断。比如删除操作写成int deleteByValueWithDummy(struct Node* dummy, int val) { struct Node* cur dummy-next; struct Node* prev dummy; while (cur ! NULL) { if (cur-data val) { prev-next cur-next; free(cur); return 1; } prev cur; cur cur-next; } return 0; }有了dummy删除头节点和删除中间节点的逻辑完全一样代码简洁很多。这个方法在面试和竞赛里很常见养成用哨兵节点的习惯能省去大量边界判断和维护头指针的烦恼。链表这块说实话不是看一遍就会的需要亲手写、亲手调。单向链表练熟后再写双向链表你能明显感觉到两种结构思维的差异单向链表要时刻想着“下一站去哪”双向链表要同时留意“前后两头的关系”。把这两种结构吃透再去看LRU缓存、操作系统的进程管理、甚至更复杂的树和图你会发现很多底层逻辑其实是相通的。后面如果再遇到链表相关的问题不妨先在纸上画一画指针走向这个习惯几乎能解决九成的链表困惑。