★ FEATURED ARTICLE 上个月面完那家公司的二面之后我把面试官问过的题目列了一个清单发现一个扎心的事实十道题里有六道绕不开“链表”这两个字。虽然刷题平台上的题解看得懂可真要我当场手写一个链表的插入删除我却总在边界条件上卡壳。空指针、改错连接顺序、遍历越界……这些坑踩一次就够。痛定思痛我给自己定了一个“数据结构七天打卡”计划Day1的任务就是把最基础的线性表彻底搞明白尤其是链表的增删改查。这篇笔记就是Day1的完整记录。它写给三类人刚刚开始接触数据结构的学生、正在准备笔面试的求职者、以及想快速回顾基础概念的开发者。如果你之前也跟我一样把链表的代码背了就忘那这篇应该能帮你把逻辑真正立起来。1. 为什么要从“线性结构”开始学数据结构1.1 数据结构的“最小闭环”很多人学数据结构一开始就扑向二叉树、图结果被指针和递归搞得怀疑人生。我个人的建议是先老老实实把线性结构吃透。为什么因为线性结构是数据结构的“最小闭环”——存储、遍历、插入、删除、查找这些最核心的动作都能在线性表上完整地过一遍而且逻辑足够直观不容易上来就劝退。数据结构本质上回答两件事数据怎么组织组织好了之后怎么操作。组织方式决定操作的代价。就好比你要管理一堆书全部摞在一个箱子里找某本书只能翻在每本书上写好编号并按顺序排好查找就快但如果经常要在中间加一本书或抽掉一本排序存放又会很麻烦。线性表就是这种“一维书架”的抽象。学完线性表你手里就有了“组织数据”和“评估代价”这两套基本动作。后面不论是学树、图还是哈希表本质上都逃不开这套思维。这也是我为什么把Day1定为线性表的原因——它是整个数据结构的起点也是面试手写代码时出现频率最高的基础题型。1.2 线性表两大阵营顺序表vs链表线性表有两种主流的实现方式顺序表和链表。顺序表用一段连续的存储空间来存放数据我们平时用的数组就是它的典型代表。优点是按下标访问的时间复杂度是O(1)CPU缓存友好缺点是插入和删除要移动大量元素平均O(n)。因为数据在内存里是挨着放的要插一个进来后面的所有元素都得往后挪一步。链表则用一组不连续的内存节点串起来每个节点除了存数据还要存“下一个节点在哪”。插入和删除的时候只需要修改指针不需要移动数据本身所以平均O(1)但查找某个位置要沿着指针一个个走是O(n)。这两者没有绝对优劣只有适不适合当前的场景。这个表我记在笔记第一页之后做题选数据结构的时候会经常用维度顺序表数组链表内存布局连续分散靠指针连接按下标访问O(1)O(n)头部插入/删除O(n)需要搬移O(1)改指针即可中间插入/删除O(n)查找O(n) 改指针O(1)额外空间基本无每个节点多存一个指针CPU缓存命中率高低节点可能散落各处1.3 一个生活类比帮你建立链表直觉我跟完全零基础的朋友解释链表时经常用一个类比传话游戏。一群人排成一排每个人只知道“我后面那个人是谁”。现在要在中间某个位置插一个新人只需要让前面那个人把手指向后改为指向新人新人指向原来的下一个人就行后面的人完全不用动。这个“只改指针、不动位置”的思想就是链表的核心。顺序表则是另一幅画面像电影院座位每个人都固定在某个编号上。要往中间插一个人后面的所有人都得站起来挪一个位置。直观感受一下这个成本就高多了。把这两个画面在脑子里立起来再看后面的增删改查代码你会觉得每个操作都是在做“谁指向谁”的连线题而不是在背晦涩的语法。2. 链表的核心原理与第一版代码2.1 节点到底是个什么东西链表的基本单元叫节点。每个节点有两部分数据域和指针域。数据域存放真正的数据指针域存放下一个节点的地址。在Python里这个“地址”就是引用在C/C里就是指针。我们之所以先学单向链表是因为它是理解一切动态数据结构的地基——双向链表只是多了一个prev指针循环链表只是尾节点next指向头节点树和图本质上也是一堆节点加上不同的指针指向关系。地基打稳了后面全是变体。用Python定义节点类最简洁的写法是这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next很多教材把这个类叫Node叫什么都行。重要的是理解next字段存的不是“下一个节点的值”而是“下一个节点整个对象”的引用。你可以通过cur.next拿到下一个节点再通过cur.next.val拿到下一个节点的数据。2.2 头指针、头节点和哨兵节点的区别写链表代码时一定会遇到三个容易混淆的概念头指针、头节点、哨兵节点。头指针是一个变量它指向链表的第一个节点。这是访问链表的唯一入口绝对不能丢。丢了链表就找不到了只能从内存中凭回忆重建。所以很多公司面试手写链表第一步都是让你创建一个head变量。头节点是链表中的第一个实际存储数据的节点。注意有些教材把“头节点”定义为不存数据的辅助节点放在真正的第一个数据节点前面这种节点通常叫“哨兵节点”或“哑节点”。哨兵节点最大的好处是空链表和非空链表的处理逻辑能被统一插入和删除不再需要单独讨论“是不是第一个节点”这种特例。我在Day1的代码里先用不带头节点的写法因为它的逻辑更赤裸更容易暴露你对指针的理解。练熟之后再引入哨兵节点你会发现自己的代码突然干净了一大截。2.3 用Python先写一个能跑的骨架我选择用Python来演示核心逻辑原因很简单Day1的重点是理解链表的增删改查本身而不是被malloc和free分心。C语言那种“手动管内存”的痛感对理解链表的内存布局确实很有帮助建议Day2再回头补C版本。先写一个最基本的链表类包含初始化、求长度、遍历打印三个方法class LinkedList: def __init__(self): self.head None # 空链表头指针指向None def size(self): 返回链表长度 count 0 cur self.head while cur: count 1 cur cur.next return count def traverse(self): 从头到尾打印所有节点值 cur self.head while cur: print(cur.val, end - ) cur cur.next print(None)注意__init__里self.head None表示空链表。之后的每次操作都要先问自己一个问题如果链表是空的这个操作还成立吗这个问题我后面吃亏了无数次后面单独开一节讲。这里的size()和traverse()都是最朴素的遍历核心思想完全一致用一个cur游标从head开始每访问一个节点就向后移动一次直到cur变成None。这个模式今天会重复见到无数次。3. 增删改查四件套从写对到写稳3.1 插入操作头插、尾插、中间插插入是链表操作里最需要想清楚的。我把它拆成三种场景来练头部插入、尾部插入、指定位置插入。头部插入的操作只有两行关键代码def insert_at_head(self, val): new_node ListNode(val) new_node.next self.head self.head new_node这里两行的顺序绝对不能颠倒。为什么因为如果先把self.head改成new_node原来的头节点就找不到了new_node.next就不知道该指向谁了链表等于断成了两截。尾部插入要先遍历到最后一个节点再让tail.next指向新节点def insert_at_tail(self, val): new_node ListNode(val) if self.head is None: # 空链表特殊处理 self.head new_node return cur self.head while cur.next: # 注意是 cur.next不是 cur cur cur.next cur.next new_node判断条件是while cur.next意味着循环结束时cur是最后一个节点——它的next本来就是None被当作“尾部”的标记。如果你写成while cur循环会一直走到cur None再加个.next就直接报AttributeError。这个细节我踩过一次记忆极其深刻。中间插入假设要在索引index的位置插入新节点def insert_at_index(self, index, val): if index 0 or index self.size(): raise IndexError(索引越界) if index 0: self.insert_at_head(val) return new_node ListNode(val) prev self.head for _ in range(index - 1): # 找到 index-1 位置的节点即前驱 prev prev.next new_node.next prev.next prev.next new_node这里最难的是“为什么要找index-1而不是index”。因为单链表每个节点只知道后面是谁不知道前面是谁。你要在index位置插入新节点就必须先控制住index-1的位置通过修改它的next来实现插入。这个“找前驱”的思维会贯穿所有链表操作。中间的连接顺序是固定的先把新节点和后一个节点连起来再改前驱的next。我建议把这句话记在脑子里先连后路再改前路。3.2 删除操作三种位置三种处理删除比插入更考验边界处理。核心思想跟插入相反找到要删节点的前驱然后让前驱的next直接指向要删节点的后继也就是prev.next target.next。如果删除的是头节点直接让head指向第二个节点即可def delete_at_head(self): if self.head is None: return self.head self.head.next删除中间节点要先找到目标节点的前驱再绕过它def delete_at_index(self, index): if index 0 or index self.size(): raise IndexError(索引越界) if index 0: self.delete_at_head() return prev self.head for _ in range(index - 1): # 找到前驱 prev prev.next prev.next prev.next.next # 跳过目标节点prev.next prev.next.next这行是删除的精华它没有显式地“删除”什么而是通过改变指针让被删节点从链表里“隔离”出去。在Python里被隔离的节点没有引用后会自动被垃圾回收不需要手动释放。但如果在C语言里这里必须先free掉被删除的节点否则就是内存泄漏。删除尾节点也属于“找到最后一个节点的前驱”这一类操作起来就是prev.next None。本质和前面对齐找到前驱改前驱的指向。3.3 查找与修改按值找和按位置改查找操作相对简单就是顺序遍历def search(self, val): cur self.head index 0 while cur: if cur.val val: return index cur cur.next index 1 return -1找到返回下标找不到返回-1。这里没什么花活就是一步步走。修改也简单先查找找到后直接给节点的val重新赋值def update(self, index, new_val): if index 0 or index self.size(): raise IndexError(索引越界) cur self.head for _ in range(index): cur cur.next cur.val new_val我想提醒一件事链表的查找代价是O(n)很多面试题表面上考“查找”其实是为了考察你是否清楚链表随机访问弱这个特性从而引导你去想快慢指针、哈希表等优化手段。Day1先把最朴素的顺序查找写顺之后再讨论优化也不迟。到这里增删改查四件套已经齐了。写完之后不要急着看下一节先把自己手里的代码跑一遍打印几次插入删除的结果确认输出和手画图一致再继续。4. 手写链表最容易翻车的几个瞬间4.1 NoneType的噩梦我在刚开始写链表的前一个小时里几乎一半报错都是AttributeError: NoneType object has no attribute next。原因就一句话试图访问None的next属性。典型场景是这样的链表有3个节点我用while cur.next is not None作为循环条件结果在某次迭代里cur已经走到第三个节点然后把cur赋值成cur.next也就是None。下一轮循环进入条件判断时cur已经是NoneNone没有.next直接炸掉。另一个典型场景是删除或插入时给的索引等于链表长度代码尝试访问一个不存在的节点。解决这个问题的核心习惯是每次操作前先判断边界。不要指望程序替你想链表代码的边界条件必须人肉写清楚。我的土办法是写每个操作之前先画一张3个节点的图把操作过程中每一步的指针指向都画出来尤其是cur会变成None的那根线。图一画出来报错率直线下降。4.2 指针连接顺序先记后路再改前路所有修改指针的操作里最反直觉的时刻就是插入时不知道该先改哪个指针。我总结了一句口诀先让新节点连好后路再改前驱的next。为什么必须这个顺序因为前驱的next一旦被改成新节点原后继就只能通过新节点去访问了。举个例子要在节点A和节点B之间插入新节点X# 正确顺序 X.next A.next # 先让X指向B保留后路 A.next X # 再让A指向X # 错误顺序 A.next X # A先把B丢了 X.next B # 但B此时已经无法从A拿到第二个版本里B节点在A.next X执行之后就暂时“断线”了虽然之后还能用变量救回来但代码逻辑已经完全混乱。链表操作最怕的就是这种“先断路再接线”的写法。删除也是这样要删掉节点B正确操作是让A的next直接指向C也就是A.next B.next。如果你先让B.next NoneC节点以及之后的所有节点就全从链表里断开了再也找不回来。4.3 验证链表正确性的土办法写完链表操作怎么验证除了单测框架我推荐两个土办法但都特别好用。第一个是遍历打印。写一个traverse方法从头走到尾打印每个节点的值。插入3个节点就应打印出3个值删除1个节点就应少1个值顺序对不对一眼就看出来。这是我日常调试链表的第一检查工具。第二个是画图走查。拿纸笔用一个“1 - 5 - 9”的三节点链表模拟一次中间插入和一次中间删除把每一步的next指向变化写出来再对照代码逐行看。这招虽然费时间但对理解指针关系极其有效尤其是处理复杂一点的中间插入时画三分钟图能省半小时debug时间。这两个土办法看起来不够“高科技”但应对链表这级复杂度绰绰有余。真正写链表出错从来不是逻辑复杂而是基础动作没练透。5. 面试与自测阶段的延伸思考5.1 复杂度对比表什么时候用链表学了增删改查之后一定要回到复杂度这个根本问题上来。我把顺序表和链表的操作复杂度画成一张表贴在笔记里反复看操作顺序表单向链表按下标访问O(1)O(n)头部插入O(n)搬移元素O(1)改指针头部删除O(n)搬移元素O(1)改指针尾部插入O(1)不考虑扩容O(n)需遍历中间插入O(n)查找O(n)改指针O(1)查找值O(n)O(n)额外空间少每个节点多一个指针这张表能帮你做题时做决策频繁在头部插入删除选链表频繁按下标随机访问选顺序表频繁在尾部追加顺序表更合适但要注意扩容问题。当然还有“双向链表”“循环链表”这些变体会让尾插变成O(1)那部分留给Day2。5.2 从单向到双向、循环Day2的预告单向链表的增删改查说到底核心就是一句话通过前驱节点改变指针指向。一旦这句话搞明白了Day2该学什么就很清晰双向链表解决“往前找”的问题每个节点多一个prev指针删除某个节点时不用再费劲找前驱循环链表解决“最后一个节点还要回到开头”的问题尾节点的next指向头节点遍历时要注意死循环栈和队列这两种受限线性表本质上就是“插入删除位置被锁死”的线性表栈只在一端操作队列一端进另一端出再往后链式二叉树不过是“每个节点有两个孩子指针”的扩展理解了链表的节点思想树的概念也会更容易接受。我打算按这个顺序继续往下打卡。如果你也在学数据结构建议你也把“为什么需要它”放在“它的代码怎么写”前面——理解了动机代码只是翻译。最后记录一下今天的真实感受一开始我以为链表难在代码后来发现难在想象。那些next的箭头不在纸上画过一遍永远只是抽象概念。今天这个Day1把基础概念和增删改查过完我已经能很顺地写出一份不带bug的链表操作实现了。最大的收获不是代码本身而是建立了一种意识每次改指针前先问自己如果链表为空怎么办如果指针指向None怎么办如果顺序反了是不是会丢节点。带着这种意识去写报错会少很多。下一篇我打算用C语言再实现一遍把内存管理的细节也补上顺便把双向链表和循环链表一起收拾掉。如果你也对数据结构打卡感兴趣可以从链表的一个简单实现开始亲手画一遍图跑一遍代码。这条路刚开始看起来很长但只要第一天不放弃后面会越来越顺。
阅读完成 · 觉得有帮助？
