这已经是我啃数据结构的第五天了。前面四天从数组、顺序表、栈、队列一路过来都是“连续存储”的线性结构今天终于跳到链表这一跳让我意识到数据结构真正的分水岭到了。第五天安排的是手写链表、用链表实现双端队列顺带把空间复杂度这个老熟人拉出来重新算了一笔账。如果你也在学数据结构不管是期末复习、考研刷题还是单纯想补补内功这篇笔记应该能帮你省下不少试错的时间。我会把今天踩过的坑还有从《李春葆数据结构》和“王道”考研书里摘出来的关键点都揉在一起讲。1. 今天学什么链表为什么是数据结构的分水岭1.1 前四天的内容只是“热身”第一天到第四天我们处理的基本都是顺序存储结构。数组最简单逻辑和物理都是连续的访问第i个元素直接用下标算地址时间复杂度O(1)。到了顺序表本质还是数组只是包了一层动态扩容和增删改查的接口。栈和队列呢其实是操作受限的线性表栈只在一端进出队列一头进另一头出底层的存储还是连续数组。这些结构有个通病插入和删除如果要保持元素的相对顺序不变就得搬移大量元素。比如在顺序表中间插入一个数平均要移动n/2个元素时间复杂度O(n)。数组扩容也很麻烦通常要新开一块更大的内存把原数据拷贝过去这个过程会浪费时间和临时空间。所以连续存储适合“读多写少”的场景但如果你要频繁在中间插入删除它就变得很笨重。链表恰恰是用来解决“动态插入删除”这个痛点的。它不要求物理连续每个元素单独申请内存通过指针把各个离散的内存块串起来。第五天学完我对“逻辑结构”和“物理结构”这两个抽象概念才算真正有了体感。链表就是一个典型的逻辑连续但物理不连续的结构而之前学的数组是逻辑物理都连续。1.2 链表要解决的核心痛点链表引入了一个新概念节点Node。一个节点包含两部分一部分是数据域另一部分是指针域。指针域存的是下一个节点的地址这样一来每个节点不需要挨在一起也能通过指针找到彼此。这个设计带来几个直接好处。第一插入删除不再需要移动数据只要修改目标位置前后节点的指针指向就行时间复杂度降到O(1)。第二空间是按需分配的需要用多少节点就申请多少不会像数组那样预先分配一整块导致内部碎片。第三可以让多个链表共享同一个节点或者用指针构造出树、图这种更复杂的结构。但代价也很明显。每个节点都要额外存一个指针这是额外的空间开销。更麻烦的是链表不支持随机访问想找第k个节点必须从头开始一节一节跳过去时间复杂度O(n)。所以链表不是“更好”的顺序表它和数组各有各的适用场景。今天我自己的体会是动手实现一遍链表的增删改查比盯着PPT看十遍都有用。因为只有亲自写出Bug你才会真正记住指针操作的那些致命细节。2. 手写链表从结构定义到节点操作2.1 链表节点结构和内存布局先看C语言版的定义这是数据结构教材最常用的写法typedef struct Node { int data; // 数据域这里先拿整型做例子 struct Node* next; // 指针域指向下一个节点 } Node;用Python写就更直观了因为类对象天然就是这种引用结构class Node: def __init__(self, data): self.data data self.next None有的教材会给链表加一个头节点或者叫哨兵节点。头节点的data域不存有效数据或者存链表长度它的next指向第一个真正的元素节点。加头节点的好处是统一空表和非空表的操作插入删除不需要特殊处理“头部”情况。但要注意头节点在空间复杂度分析里属于“额外开销”不过通常忽略不计。我自己的理解是链表的内存布局就像一列火车每一节车厢是一个节点车厢之间的挂钩就是指针。火车可以拖着车厢到处跑但车厢本身不需要都停在同一个车库。链表里每个节点都是单独malloc出来的它们的内存地址散落在堆区的各个位置是next指针把这份“散装”数据串成了逻辑上的序列。这里有个很容易忽略的细节节点的声明里指针指向的是“下一个节点结构体”不是指向下一个data字段。因为在C语言里只有知道了结构体的完整类型才能通过指针访问它的成员。所以写struct Node* next而不是int* next。这个一开始会绕但写多了就懂了。2.2 头插法与尾插法两种构建方式的差异构建链表有两种常见方式头插法和尾插法。它们的代码差异很小但生成的链表元素顺序完全相反。头插法每次把新节点插在头节点之后。核心逻辑是新节点的next指向当前第一个节点然后头节点的next指向新节点。代码长这样void insertHead(Node* head, int data) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data data; newNode-next head-next; head-next newNode; }注意这里有个顺序问题必须先“新节点的next指向旧第一个节点”再“头节点指向新节点”。如果反过来先让head-next指向newNode那原来的第一个节点就找不到了链表直接断掉。这个顺序我第一天写的时候就搞反过调试到怀疑人生。尾插法需要维护一个尾指针tail新节点插在链表的尾巴上。逻辑是tail的next指向新节点然后tail移动到新节点。每次都要用malloc创建新节点所以没有找尾巴的遍历开销前提是tail指针一直保持更新。void insertTail(Node* head, Node** tail, int data) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-data data; newNode-next NULL; (*tail)-next newNode; *tail newNode; }这里用了二级指针是因为尾指针本身要被修改。如果你不理解二级指针就用返回值把新tail带回外面也是一种办法。最笨但稳妥的办法是用一个遍历找到尾节点再插入但每次插入都是O(n)性能差。实际写代码时头插法适合用来构建逆序序列尾插法适合保持输入顺序。比如从键盘读一串数想原样存进链表就必须用尾插法如果只想快速建链不在乎顺序那头插更快因为它不需要维护尾指针。2.3 链表的遍历、插入、删除指针操作的经典陷阱遍历链表的动作很简单从第一个节点开始用cur cur-next一路走直到cur为NULL。但这里藏着最常见的空指针陷阱。比如在删除节点时你找到了前驱节点pre要删掉pre-next。你得先保存一下被删节点的下一个节点不然链接就断了。正确写法Node* toDelete pre-next; pre-next toDelete-next; free(toDelete);这段代码的意图是让前驱节点pre的next直接跳过toDelete指向toDelete的下一个节点然后释放掉toDelete所占的内存。很多初学者写成free(pre-next); pre-next pre-next-next;想想看free之后你还能访问pre-next-next吗不能因为内存已经释放了这是悬垂指针。必须先记录后继节点再释放当前节点。还有按值删除和按下标删除的区别。按值删除要遍历找到第一个匹配的节点时间复杂度O(n)按下标删除同样要遍历到指定位置。删除头节点和删除中间节点的处理方式不同虽然带头节点能统一但在代码里仍需判断“待删除节点是否为空”。我自己给链表写测试用例时习惯在每个关键操作之后打印链表长度和内容看看结构是否符合预期。如果只是打印next指针地址很难看出逻辑错误。建议用节点值来验证比如构造一个递增序列[1,2,3,4,5]然后删除第3个期待输出[1,2,4,5]。有了标准输入输出调试一下就看明白了。3. 双端队列用链表实现一个“可两边操作”的队列3.1 双端队列的应用场景双端队列Deque是队列的扩展“Double Ended Queue”的意思就是两端都可以入队出队。它不像普通队列那样只能尾部进头部出也不像栈那样只能单端进单端出。双端队列允许你在头部和尾部都执行插入和删除。这个结构在真实场景里很常见。最经典的是滑动窗口最大值问题很多算法题用双端队列维护窗口内的候选值窗口右边进、左边出两端都要操作。还有一个例子是撤销操作文本编辑器的撤销历史可以用双端队列来管理用户撤销很多步之后又想“前进”这时需要从尾部重新加入历史同时限制队列长度。任务调度里也常见某些高优先级任务可以从头部插队普通任务从尾部入队。从数据结构学习的角度双端队列是一个很好的“合体”练习它既可以基于数组实现也可以基于链表实现。用链表实现时我们恰好能把单链表升级成双向链表因为双向链表天然支持头部和尾部的高效操作。3.2 基于双向链表的实现思路要用链表实现双端队列单链表其实已经能做了头部插入、头部删除自然没问题尾部插入如果维护tail指针也可以但尾部删除就麻烦了需要找到tail的前驱而单链表找前驱必须从头遍历效率O(n)。所以实现真正的双端队列推荐用双向链表。双向链表的每个节点有两个指针prev指向前一个节点next指向后一个节点。定义长这样typedef struct DNode { int data; struct DNode* prev; struct DNode* next; } DNode;为了统一操作我们给双向链表加一个头哨兵和一个尾哨兵这两个哨兵节点不存数据只是方便处理边界情况。头哨兵的next指向第一个有效节点尾哨兵的prev指向最后一个有效节点初始时两个哨兵互相指向对方表示空队列。这样一来在头部插入新节点就拆成四步新节点的next指向当前第一个有效节点新节点的prev指向头哨兵头哨兵原本的next节点的prev指向新节点头哨兵的next指向新节点。在尾部插入对称同理。删除头部节点则反过来。这些操作的共同点是只需要修改相邻节点的指针与队列元素个数无关所以时间复杂度都是O(1)。写到这我要强调一下手写双向链表容易在指针调换顺序上栽跟头。我通常先用纸画节点框标清楚当前状态和希望的状态再翻译成代码。很多教材也在反复强调“先读后写”的原则先把所有需要读取的旧指针保存到临时变量里再去修改。比如删除节点时先把待删除节点的前驱和后继记录好再调整指针最后free。3.3 对比循环数组实现的优劣双端队列也可以使用循环数组来实现。所谓循环数组就是逻辑上把数组首尾相接用下标取模来移动头尾指针。比如size8tail当前在7插入新元素时tail (tail 1) % 8下标回到0。这种实现的内存连续cache友好访问速度快而且不需要每个节点存指针空间开销小。但问题在于数组容量固定满了以后需要扩容扩容意味着把旧数组元素搬到新数组耗时O(n)而且需要拷贝。链表实现的双端队列反过来每个节点需要两个指针空间开销大节点在堆里离散分布缓存不友好。但它没有扩容问题需要多少节点就动态申请多少插入删除也真正是O(1)。实际工程里C标准库的std::deque用的是分段连续数组Java的ArrayDeque用的是循环数组它们都很少用链表实现核心原因就是链表节点分散内存访问局部性差性能在大量数据时不如数组。不过我们学习数据结构并不是为了“标准库用什么我们就用什么”而是要理解每种结构背后的取舍。用双向链表实现一遍双端队列能帮你把“哨兵节点”“双向指针维护”这些硬核技能练扎实之后再去理解高级的缓存优化结构会容易得多。4. 空间复杂度分析链表真的“省空间”吗4.1 先分清时间复杂度和空间复杂度学数据结构时我们经常说某个操作时间复杂度是O(1)还是O(n)。空间复杂度呢说的是算法在运行过程中额外占用的内存量级一般用输入规模n的函数来表达。比如顺序表开辟一个大小为n的数组那空间复杂度就是O(n)。如果只是用几个临时变量空间复杂度就是O(1)。对于链表本身空间复杂度主要取决于节点数量和数据量。这里有个容易被忽略的点一个链表要存储n个整数除了n个int数据本身还要存n个指针。在64位系统上指针通常是8字节而int只有4字节。所以只算数据的话需要4n字节算上指针就变成12n字节空间占用是原来的3倍。这不是理论上的“常数级”而是系数问题在实际场景里影响很大。我在学习时看到很多考研题目爱比较“数组和链表谁更省空间”标准答案往往是“链表不一定省甚至更费”。因为数组一次性申请n个数据空间最多浪费一些空闲未用的槽位链表每个节点都带指针即便数据量小指针开销也固定。但从动态分配的角度看数组必须预分配一段连续地址有时找不到足够大的连续空间而链表可以用零散内存这一点在某些受限环境下反而是优势。4.2 链表 vs 数组空间开销的量化对比我们做一个简单的量化。假设存储n个int每个int占4字节每个指针占8字节链表节点结构体在C语言里因为内存对齐实际可能占16字节数据4字节填充4字节指针8字节。如果数组也要预留一些空间比如容量是当前元素的1.5倍那每个元素的有效空间是6字节。相比之下链表每个节点16字节是数组的2.7倍左右。如果数据本身很大比如是个结构体占256字节那么指针的额外开销占的比例就小了链表相对数组的反而不那么浪费。再看操作的空间开销。用链表做反转迭代法只需要几个临时指针变量空间O(1)递归法会占用函数调用栈递归深度n空间O(n)。数组反转同样可以用临时变量O(1)。但数组扩容时数组内元素要搬移到新数组旧数组没释放之前新旧数组共存那一刻的峰值空间可能接近2n这也要纳入空间复杂度的考虑。空间复杂度分析不能只看理论还要看实际分配器的行为。malloc一个节点操作系统和C运行时库会在内存块头部附加一些元数据小对象分配多了额外元数据的开销可能比数据本身还大。所以“链表比数组省空间”这种说法在工程里通常不成立。更准确的说法是链表用“空间换灵活性”它用额外指针换来了动态插入删除和任意内存碎片场景下的可行性。4.3 递归深度与空间复杂度的关系链表相关的算法里递归特别容易让人忽略空间复杂度。拿反转链表举例递归解法非常简洁Node* reverseList(Node* head) { if (head NULL || head-next NULL) { return head; } Node* newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }每次递归调用都要在调用栈上保存一层上下文包括参数head以及返回地址。链表有n个节点递归深度就是n所以空间复杂度O(n)。如果链表有几百万个节点递归版本很可能栈溢出。迭代版本用三个指针逐个翻转空间O(1)适用性更强。很多面试官喜欢先让你写递归再问你能不能优化成迭代考的就是空间复杂度意识。学到这里我建议你做一个动作把所有常用链表操作的时间复杂度和空间复杂度整理成一张表包括查找、插入、删除、反转、合并、找中点。这样期末复习和面试前看一遍比重新啃整本书效率高很多。5. 踩坑实录与学习工具建议5.1 常见错误速查表今天写链表和双端队列我集中踩了好几个坑。趁热打铁整理成一张速查表你在调试代码时可以直接对照常见错误后果排查思路malloc之后忘记检查返回值内存分配失败时操作空指针每次malloc后if(Node NULL)报错退出插入节点时先改头指针再改新节点next丢失原链表第一个节点的引用造成断链坚持“先连后继再改前驱”的顺序删除节点时先free再访问节点的next访问已释放内存产生悬垂指针先用临时变量保存后继节点再free当前节点尾插法忘记更新tail指针后续插入总插在同一个节点后插完立即让tail newNode双向链表删除时没修改前驱的next和后继的prev链表前后指针指向不一致遍历产生环先记录prev和next再分别更新递归反转链表深度过大栈溢出 / 运行超时改用迭代法空间O(1)混淆链表长度和节点下标越界访问或漏掉最后一个节点用辅助函数printList随时验证我自己还犯过一个很隐蔽的错误在C语言里把两个节点结构体直接赋值比如*a *b结果指针字段也被复制了导致b和a的next指向同一个节点后续修改a的next会意外影响b。遇到这种诡异问题第一反应应该是检查浅拷贝和深拷贝的区别。5.2 参考资料怎么选、怎么用数据结构教材里我觉得《大话数据结构》最适合入门它用大量漫画和生活例子解释各种结构比如皇帝妃子排队这种梗虽然有点搞怪但能让不怕抽象的新手先建立直觉。李春葆老师的《数据结构》教材更严谨代码和习题非常规范考研和计算机学科常会用到。第五版配套有学习指导和勘误如果你用的是这本教材记得把勘误汇总打印出来里面有一些印刷错误和习题答案修正不看会踩坑。“王道考研”系列是另一条路线特别适合需要应对笔试的人群。它把知识点按考点整理每一章都配有习题和解题套路比如链表和栈的对比它会给一个很精练的表格。这些书我都翻过建议不要贪多选一本主教材用于系统学习选一本习题集用于刷题巩固再配合一个在线调试工具就够了。实际动手时我推荐用LeetCode或力扣的链表专项题列表。第一题从小题做起比如“反转链表”“合并两个有序链表”“删除链表的倒数第N个节点”。刷题不是目的目的是让你通过正确答案验证自己的实现逻辑。每道题提交前我会在本地把链表打印出来确认符合预期再提交。5.3 把学习笔记转成实验报告和期末复习材料很多学校的数据结构课要求交实验报告我今天这套链表和双端队列实现可以直接扩展成实验报告。报告我习惯分五个部分实验目的、需求分析、设计与实现、测试分析、总结心得。其中“设计与实现”必须包含数据结构定义和核心函数的伪代码配合一两张手绘的节点图老师会觉得你真的理解了。如果你是期末复习或考研一个很有效的方法是“按主题总结复杂度表”。比如每种线性结构顺序表、单链表、双向链表、循环链表、栈、队列、双端队列的时间复杂度访问、查找、插入、删除各列一列。再标注空间复杂度。然后把每一个结构的“适用场景”写在旁边。这份表格就是你的绝杀复习资料。我自己有一个习惯学完当天把代码重新抄一遍不看书遇到卡住的地方回头看。第二遍往往会发现第一遍理解不到位的地方特别是指针的更新顺序。这比单纯看别人的代码记忆深刻得多。数据结构不是看会的一定是写会的。写在最后的一点体会学完链表的这一天我最大的转变是从“怕指针”变成“理解指针就是在做引用记账”。无论是单链表、双向链表还是双端队列核心都是管理好节点之间的指向关系。我发现一个很实用的技巧在纸上画盒子模型每个节点画成两格一格存data一格存next箭头。执行每一步操作时先画出旧状态再画出新状态然后写下哪几根箭头需要改变方向。写代码的时候照着图改指针基本不会出错。这个方法对我自己很管用推荐你也试试。接下来的day06我打算进入排序算法和查找算法。学完链表和队列再回头学时最简单的冒泡、选择、插入排序你会发现数组和链表的区别在排序里更是体现得淋漓尽致。数据结构这条路没有捷径但每往后走一天能看懂的东西都会多一层。今天先到这下次接着聊。