很多人第一次接触单链表都会有同一种感觉书上画的那几个方框和箭头乍一看明明白白可真要自己从零写一遍从建链、遍历、插入到逆序每一步都藏着让你头皮发麻的细节。我当年学数据结构就是栽在“明白了原理”和“写出了能用”之间的那道坎上。上面也经常被刚开始学单链表的同学追问头插尾插怎么选、不带头结点到底怎么处理、指定位置插入为什么总是把链表搞断、用 Python 写逆序为什么和别人思路对不上。今天就把单链表这件事从头到尾掰开揉碎讲清楚背后的内存逻辑以及每行代码到底在干什么。这篇内容是写给两类人看的一类是正在学数据结构、被作业和考试折腾的在校学生另一类是自己刷题写算法、总感觉链表边界条件处理不好的自学者。我会用 Python 为主来写代码因为 Python 对初学者最友好、最能看清楚“引用”和“对象”之间的关系但其中的原理和易错点是语言无关的。你完全可以把这套思路平移到 C、Java、Go 里。下面我们从最根本的问题开始。1. 先搞清楚为什么数组做不到单链表却可以1.1 数组的三大软肋在理解单链表之前得先明白它到底解决了什么问题。很多人觉得链表比数组“高级”其实它不高级它只是换了一种存储思路。数组的本质是一块连续的内存空间下标就是偏移量。这种方式让随机访问极其高效但代价也很大。第一数组的长度一旦确定就很难改变。你开一个int arr[100]存到第 101 个元素怎么办只能重新开一个更大的数组把旧数据全部复制过去。这个操作的时间复杂度是 O(n)而且会带来临时的大内存消耗。Python 的 list 虽然号称“动态数组”背后其实也是这个套路只是替你自动扩容了底层依然要搬元素。第二在中间插入或者删除一个元素代价非常惨重。比如一个数组有 10000 个元素你想在第 5000 个位置插入一个新元素那么从第 5000 个到第 10000 个元素全部都要往后挪一格极端情况下就是 O(n) 次移动。删除也是一样后面的元素要往前补位。第三数组要求一整块连续内存。如果你的程序里有很多碎片化的内存块每个块都很小那么即便加起来总量足够也没办法给一个大数组用。这个问题在 C/C 这类直接管理内存的语言里尤其明显叫“外部碎片”。1.2 手拉手排队单链表的结构直觉单链表的思路完全反着来我不要求节点在内存里挨着每个节点可以散落在内存的任意角落然后让前一个节点记住后一个节点的位置用这种“记住下一个在哪”的方式把整个序列串起来。你可以想象一群小朋友手拉手排队。每个小朋友只需要记住两件事自己是谁数据以及后面拉着谁下一个节点的位置。队伍能不能走通不取决于大家站得密不密集只取决于有没有人把手松开。所谓“单”链表就是每个孩子只拉着后面一个孩子的手你只能从队头开始一个接一个地往队尾走想回头不行因为没有人记住前面的孩子是谁。这个直觉很快就引出一个关键性质链表的插入和删除只需要修改相邻节点之间的“牵手关系”其他节点完全不用动。中间插一个新同学只需要让前面的同学改拉新同学再让新同学拉原来的下一位其他所有人的手都不用松开。这比数组整体搬移的成本低太多。但也因为这种结构你失去了一样东西随机访问。数组你说arr[5]就能直接跳到第五个元素因为你知道起始地址一加偏移就到了。链表里的第五个元素在哪不知道必须从第一个开始顺着 next 一个个数过去。这一下就把访问某个节点的时间复杂度从 O(1) 拉到了 O(n)。所以说链表不是万能的它是用“访问慢”换来了“插入删除灵活”这一进一出就是数据结构里最经典的权衡。2. 单链表的积木怎么搭节点、指针域以及要不要带头结点2.1 一个节点身上必须有的两样东西单链表的基本单元是节点Node。每个节点必须包含两部分一部分存数据另一部分存“下一个节点在哪”。这两样缺一不可。数据域根据自己的需求随便定可以是整数、字符串、对象链接域就是指向下一个节点的引用在 Python 里就是一个普通属性。用代码定义一个节点类就这么简单class Node: def __init__(self, data): self.data data # 数据域 self.next None # 指针域初始指向空为什么初始next要设为None因为一个新节点刚造出来的时候它后面还没有接任何东西。每个链表的最后一个节点它的next也必须是None这是链表的“终止符”。判断一个链表走到头了靠的就是这个None。我在给学生讲的时候常说None就是链表的句号没有句号的链表是危险的遍历时会直接越界或者死循环。2.2 Python 里的“指针”到底指什么很多人学过 C 语言再看 Python 链表会犯迷糊Python 没有指针啊怎么写链表其实 Python 的对象引用机制本质上就是一个自动管理的指针。你写node_a.next node_b做的事情就是让node_a的next属性“指向”node_b那个对象。你可以用id()函数来验证a Node(1) b Node(2) a.next b print(id(a.next), id(b)) # 输出完全一样这说明a.next和b引用的是同一个内存对象。你通过a.next.data和b.data访问到的也是同一份数据。这就是链表的底层逻辑靠“引用”串起对象而不是靠物理上挨着。也正因为 Python 的引用是自动管理的你不需要像 C 语言那样手动malloc和free。节点没人引用的时候垃圾回收器会自动回收它。这对于理解链表是好事也是坏事好处是你不用纠结内存释放的时机坏处是你会因此忽略“断开引用”这件事的重要性。比如delete一个节点在 C 里你要手动free在 Python 里你只要让这个节点不再被任何变量引用它就自动被回收了。后面讲清空链表时这个区别很关键。2.3 带不带头结点差别有多大这是教材里最容易绕晕人的概念也是考试最爱考的地方。所谓“头结点”是指链表最前面额外加的一个哨兵节点它不存实际数据或者说不参与业务数据作用就是让所有操作统一。而“头指针”才是真正指向链表中第一个有效节点的变量。区分一下不带头结点的单链表head直接指向第一个数据节点。链表为空时head None。所有针对第一个节点的操作都要单独处理因为第一个节点没有前驱。带头结点的单链表head指向哨兵节点哨兵节点的next才指向第一个有效数据节点。链表为空时head.next None。因为哨兵节点永远存在所以链表中任何有效节点的删除和插入都有统一的前驱处理方式不需要特判“这是不是第一个节点”。这两者的差距一句话总结带头结点是拿一个“不存数据的空头头”换代码的简洁和统一不带头结点是省一个节点但每个边界操作都要多写 if。用不带头结点的方式删除第一个节点你需要写if head is None: return if pos 0: head head.next # 特殊处理头节点而带头结点时因为哨兵节点永远是第一个删除“第一个有效节点”对代码来说就是“删除哨兵节点的后继”跟删除第 N 个节点没有任何区别不需要那个pos 0的分支。很多教科书默认用不带头结点的写法因为它更贴近“指针直接指向节点”的底层概念但实际工程里带头结点的写法更不容易出错。下面我的代码示例采用不带头结点来演示因为这类写法对理解边界条件训练最充分但我会专门标注哪些地方是边界特判方便你以后切换到带头结点时能对应上。3. 建链的三种姿势头插、尾插、指定位置插入3.1 头插法新节点永远站在最前面头插法顾名思义每次新节点都插在链表的头部成为新的第一个元素。它的核心就两行def insert_head(self, data): node Node(data) node.next self.head self.head node这段代码的顺序非常重要。正确做法是先把新节点的next接到原来的头节点上再把head指针移动指向新节点。这个顺序一旦写反后果是什么如果你先执行self.head node原来的头节点就没人指向了你再想拿到它只能通过node.next但如果此刻你还没写node.next self.head旧的头节点就彻底丢了链表断成了两截其中一截变成垃圾。我见过太多人在这里栽跟头。记一句口诀先接后断先让新节点拉住老节点再让 head 指向新节点。头插法有一个很直观的特点如果你依次插入 1、2、3最后链表里存的顺序是 3、2、1和插入顺序正好相反。你可以用这个特点来做链表的“反转”后面讲逆序的时候还会用到这个思路。3.2 尾插法让链表保持输入顺序头插法有个麻烦顺序和输入反了。如果我们想按照 1、2、3 的顺序把数据存进去就需要尾插法。最简单的尾插是每次从head开始从头遍历找到最后一个节点然后在它后面接上新节点。刚学的时候这样写确实直观def insert_tail_simple(self, data): node Node(data) if self.head is None: self.head node return cur self.head while cur.next is not None: cur cur.next cur.next node注意这里必须判空链表为空时要插的节点就是第一个节点直接让head指向它。这个判断漏了空链表上执行cur.next会直接抛AttributeError。一个容易犯的错是写成while cur is not None而不是while cur.next is not None。前者会让循环停在最后一个节点的后面也就是cur变成None你回来再操作cur.next node就直接报错了。你要找的是“最后一个节点”判断标准是“这个节点的 next 是 None”而不是“这个节点是 None”。这种每次从头遍历的尾插法插入 n 个节点的时间是 O(12...n) O(n²)。数据量小无所谓数据量大就不划算了。更常见的做法是维护一个尾指针tail始终指向最后一个节点插入时直接在tail后面追加然后更新tail。这样插入就变成了 O(1)。不过这时你还要额外维护 tail 在删除等操作里的正确性工程上一旦忘了更新 tailbug 就冒出来了。初学者先用从头遍历的版本理解逻辑然后再去优化这是比较稳妥的学习路径。3.3 在指定位置插入先找前驱再动手“在指定位置插入”是所有插入操作里最综合的也是热搜词里出现频率很高的一个点。因为这里几乎涵盖了链表所有的边界情况。插入操作分三步走移动到要插入位置的前一个节点前驱。让新节点的next指向前驱原来的后继。让前驱的next指向新节点。核心代码def insert_at(self, pos, data): if pos 0: raise ValueError(位置不能为负数) node Node(data) # 插入到头部 if pos 0: node.next self.head self.head node return # 找到前驱节点 pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None: raise IndexError(位置超出链表长度) # 核心三步node.next 先指向后继pre.next 再指向 node node.next pre.next pre.next node这里同样要注意顺序问题。为什么必须先执行node.next pre.next再执行pre.next node因为pre.next里存的还是原来的后继节点你要让新节点接上它必须先把“后悔”拿到。一旦你先写了pre.next node原来的后继节点就只剩下node.next这一条路可以找回可这时候node.next还是None整个链表又断了。先接后断这个顺序在链表操作里是铁律插入如此后面讲删除时思路正好反过来。另外还要注意“移动几步”这个细节。要在位置pos0 为起点插入你要找到的是下标pos-1的节点。第一个节点下标是 0它的前驱是head不带头结点时插入头部是特例。写循环时从head开始向后移动pos-1次恰好停在pos-1号节点上。很多初学同学循环次数多写了或少写了插出来位置总差一位。我的习惯是先想清楚 push 前驱的下标再算循环次数最后拿一个只有两三个节点的链表手动走一遍循环验证自己写的代码。4. 表的基本操作实验查找、删除、清空一次跑通4.1 查找节点按值和按下标查找操作是链表里最暴露“链式结构”弱点的功能。数组按下标是 O(1)链表按下标必须从头走最坏情况 O(n)。代码很简单但这里我想聊的是它的“遍历模板”这几乎是所有链表操作的地基cur self.head while cur is not None: # 处理 cur 这个节点 cur cur.next按值查找第一个匹配的节点下标def find(self, val): cur self.head idx 0 while cur is not None: if cur.data val: return idx cur cur.next idx 1 return -1按下标返回节点def get(self, index): cur self.head i 0 while cur is not None and i index: cur cur.next i 1 if cur is None: return None return cur.data这个模板你一定要背到像呼吸一样自然。后面写逆序、写环检测、写两两交换节点全部都是在这个模板上做变形。4.2 删除节点指针域绕行删除一个节点本质上是让它的前驱“绕过”它直接指向它的后继。在链表的语境里被删除的节点本身可以不用去动等没人引用它之后垃圾回收会处理。def delete_at(self, pos): if self.head is None: return False if pos 0: self.head self.head.next return True pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None or pre.next is None: return False pre.next pre.next.next return True你看删除的核心只有一行pre.next pre.next.next。它把pre的下一个节点要被删除的节点直接从链表中跳过去了。这里最容易被忽略的是删除头节点要特判。因为头节点没有前驱不能走pre.next pre.next.next这条路只能直接让head head.next。这个问题在不带头结点的链表里必须单独处理。还有一点删除时返回False有两种情况一种是链表本来就空另一种是你要删的位置超出了链表长度。初学者写if pre.next is None经常漏掉结果要删除的节点不存在时代码老老实实跑到了pre.next pre.next.next但因为pre.next已经是None这一行直接抛异常。写边界条件从“最坏情况”开始推空链表、删头节点、删尾节点、位置超长把这四种情况都过一遍这个删除函数才算是能用的。4.3 清空链表不是把整个对象扔掉清空和删除单个节点的思路不一样。删除单个节点只是把某一个节点摘下来清空是要把链表里所有节点全部释放掉。在 Python 里最直接的做法是def clear(self): self.head None你可能觉得这也太简单了但这里藏着理解引用机制的关键self.head是链表唯一的外部入口。一旦你把它设为None从head出发的整条链就“够不着”了。所有节点都只被链表内部的前驱节点引用前驱不可达了后面的节点自然也不可达垃圾回收器会沿着引用链把它们全部回收。所以这一行确实能清空。但在教学场景和很多底层语言的实验里我们还会写更保险的“逐步断开”版本def clear(self): cur self.head while cur is not None: nxt cur.next # 先保存下一个节点否则断开当前节点后找不到下一个 cur.next None # 断开当前节点对下一个节点的引用 cur nxt self.head None这个版本在 C/C 里是必须的因为你得一个一个把节点free掉。在 Python 里它的意义更多在于当你手里还持有某个局部变量指向链表中某个节点时你只把head设为None那个节点不会立刻被回收因为它还被你的局部变量引用着它会带着它后面那一串节点继续存活。如果你想彻底释放整条链就得先遍历一遍把每个节点的next都断开再让外部引用失效。这就是“清空”这个操作背后真正的细节。4.4 一份可以直接跑的完整实验代码说了这么多把上面所有操作整合成一个完整可运行的实验代码建议直接复制到自己的环境里跑一遍边跑边打印每步结果class Node: def __init__(self, data): self.data data self.next None class SingleLinkedList: def __init__(self): self.head None def is_empty(self): return self.head is None def insert_head(self, data): node Node(data) node.next self.head self.head node def insert_tail(self, data): node Node(data) if self.head is None: self.head node return cur self.head while cur.next is not None: cur cur.next cur.next node def insert_at(self, pos, data): if pos 0: raise ValueError(位置不能为负数) node Node(data) if pos 0: node.next self.head self.head node return pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None: raise IndexError(位置超出链表长度) node.next pre.next pre.next node def delete_at(self, pos): if self.head is None: return False if pos 0: self.head self.head.next return True pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None or pre.next is None: return False pre.next pre.next.next return True def get(self, index): cur self.head i 0 while cur is not None and i index: cur cur.next i 1 return cur.data if cur is not None else None def find(self, val): cur self.head idx 0 while cur is not None: if cur.data val: return idx cur cur.next idx 1 return -1 def clear(self): self.head None def show(self): cur self.head out [] while cur is not None: out.append(str(cur.data)) cur cur.next print( - .join(out) if out else 空链表)我建议你在这个类上做两组小实验。第一组依次insert_tail(1)、insert_tail(2)、insert_tail(3)然后show()观察输出是不是1 - 2 - 3再insert_at(1, 99)观察是不是1 - 99 - 2 - 3。第二组试试空链表上delete_at(0)、超长位置上insert_at(5, 0)观察异常和返回值的表现。能把这两组实验跑明白单链表最基本的操作就过关了。5. 单链表逆序把每个节点的“箭头”掉头5.1 就地逆置的三指针法单链表逆序是教科书里最经典的进阶操作也是面试官最喜欢“抠细节”的题目。它的本质不是建一条新链表而是把原有每个节点的next方向调转让原来指向下一个的指针反过来指向上一个。很多人第一反应是新建一个链表遍历旧链表用头插法把每个节点插到新链表头部。这个思路没有错但它新建了一条链表空间复杂度是 O(n)面试官通常希望你做“就地逆置”也就是说不开新链表只改动原链表的指针方向空间复杂度做到 O(1)。就地逆置的标准写法是三指针法。需要三个指针prev、cur、nxt。prev初始为Nonecur初始为head。循环里做的事情用一句话说就是先用nxt保存cur的下一个节点再把cur.next掉头指向prev然后三个指针整体往后挪一位。def reverse(self): prev None cur self.head while cur is not None: nxt cur.next # 关键第一步保存后继 cur.next prev # 关键第二步掉头 prev cur # 关键第三步prev 前进 cur nxt # 关键第四步cur 前进 self.head prev # 循环结束时prev 指向原链表的尾节点作为新头很多第一次写这段代码的人会问为什么非要nxt cur.next直接cur.next prev不行吗不行因为cur.next prev执行完之后cur和旧链表后面那部分就断开了你手里的cur已经完全失去了通往后继的路。如果不提前把后继记在nxt里cur就再也找不到下一个节点了循环根本没法继续。所以在修改指针之前先保存后继这是所有链表变更操作的通用心法和前面讲的插入必须先接后断是同一个道理。一步一步看它怎么工作。假设链表是1 - 2 - 3 - None刚开始prevNone、cur1第一轮nxt21.nextNoneprev1cur2。此时链表被拆开了1成了新链表的尾部。第二轮nxt32.next1prev2cur3。第三轮nxtNone3.next2prev3curNone。循环结束self.head prev 3链表变成3 - 2 - 1 - None。时间复杂度 O(n)空间复杂度 O(1)所有操作都在原节点上完成。5.2 递归写法另一种思路递归也是一种很优雅的写法虽然它不满足 O(1) 空间递归栈会消耗 O(n) 空间但作为理解递归和链表结构相结合的练习题非常有价值。思路是先递归逆转当前节点之后的整条子链表再把当前节点接到子链表末端的后面。def reverse_recursive(self, node): if node is None or node.next is None: return node new_head self.reverse_recursive(node.next) # 此时 node.next 已经指向逆转后子链表的尾节点让这个尾节点指向 node node.next.next node node.next None # 防止成环 return new_head调用方式self.head self.reverse_recursive(self.head)。解释一下这里的两行关键操作。假设链表是1 - 2 - 3 - None递归进入1后先递归处理2 - 3处理完返回的新头是3此时子链表已经变成3 - 2并且2.next仍然指向原来的3实际上是环状的处境需要处理。回到处理1的层node是1node.next是2node.next.next就是2.next此刻它正好是子链表逆转后的“尾节点”2所以把2.next指向1也就是node.next.next node。再把1.next置为None整个链表变成3 - 2 - 1。这里有个必须断开node.next的原因如果不把1.next置为None1和2之间还保留原来的正向链接同时2又指向1这就形成了一个长度为 2 的环遍历会死循环。记住链表逆序本质上是在改箭头改完之后原来的正箭头要清掉不然就成环了。5.3 循环单链表的小补充热搜词里还有“循环单链表”这里简单提一下因为它和单链表的逆序、遍历边界直接相关。循环单链表就是把尾节点的next从None改回指向头节点这样整条链就变成了一个环。它的好处是你从任何一个节点出发都能走完整条链某些场景如约瑟夫环、轮转调度非常合适。但代价也很明显遍历的终止条件变了。普通单链表判断cur is None就结束循环链表里要判断cur.next is head或者cur is head才能结束一不小心就会死循环。用三指针法给循环链表逆序思路大体相同但最后要把新的尾节点也就是原来的头节点的next重新指回新的头节点换句话说既要改完每条边的方向还要保证尾接头的闭环关系不被破坏。我个人的建议是循环单链表先不要急着逆序先把普通单链表的逆序练到滚瓜烂熟再说两者在指针操作上的复杂度不是一个量级。6. 数组还是单链表从复杂度和真实工程场景做选择6.1 复杂度对比不能只看表面初学者经常背结论数组访问 O(1)、插入删除 O(n)链表访问 O(n)、插入删除 O(1)。这个结论对但只对了一半它忽略了一个重要前提链表插入删除的前提是你已经拿到了前驱节点。如果你要从头去找那个插入位置先花 O(n) 遍历再花 O(1) 改指针总复杂度依然是 O(n)。所以真正公平的比较是这样一张表操作数组单链表按下标随机访问O(1)O(n)按值查找O(n)O(n)在已知前驱处插入/删除O(n)需要搬移O(1)在头部插入/删除O(n)搬移全部元素O(1)在尾部插入O(1)动态数组均摊O(1)需维护尾指针或 O(n)需要遍历内存分配方式连续大块分散小块CPU 缓存友好度高低头插头删这个场景是单链表的绝对主场。数组要想在头部插入所有元素集体后移成本极高链表只需要 O(1) 改一下头指针。很多需要频繁在头部增删的数据结构比如用链表实现的栈、某些队列变体都会充分利用这个特性。6.2 真实工程里常见的单链表应用了解了复杂度之后你会惊讶地发现真实工程里单链表“裸用”的场合并没有想象中那么多但它作为基础组件藏在大量高级数据结构里。第一个经典应用是哈希表的链地址法。哈希冲突时多个键值对落到同一个桶里桶里放的就是一条链表。插入新键值对时直接头插O(1) 完成。Java 的 HashMap 在冲突较少时用的就是链表只是到了阈值才转红黑树。第二个经典应用是图的邻接表。一张有 n 个顶点的图可以用 n 条链表来存储出边每个顶点的链表里依次存放它所有的邻居节点。因为一个顶点的邻居数量是不确定的用链表天然支持动态增长比固定大小数组灵活得多。第三个是 LRU 缓存。完整的 LRU 一般用哈希表 双向链表但如果你只做简化版单链表也可以模拟“最近最少使用”的淘汰顺序每次访问一个节点就把对应元素移动到链表头部淘汰时删掉尾节点。虽然哈希表查不到节点位置会让移动变 O(n)但对理解“移动到头最近使用删除尾部淘汰最久”这个思想很有帮助。6.3 什么时候别用单链表单链表不是银弹选错场景会被性能按在地上摩擦。如果你需要频繁按下标随机访问比如写一个通过索引读数据的列表那必须用数组或动态数组。链表访问第 n 个节点要一步步走过去n 稍微大一点就肉眼可见地卡顿。如果你经常要从后往前遍历单链表直接劝退因为你根本没有向前走的指针只能每次从头走这种场景得用双向链表。还有个反直觉的点数组在“读多写少”并且容量可预估时性能反而比链表好很多。链表节点在内存里东一个西一个CPU 访问时要不断跳转缓存命中率低数组是连续内存遍历时 CPU 可以预取速度飞快。这也是为什么很多语言的标准库在实现动态数组如 Python list、C vector时宁愿频繁搬移元素也不轻易改用链表来当默认容器。工程里“内存连续”带来的速度优势很多时候比“插入删除 O(1)”更值钱。所以选择单链表的铁律大概是这三条你无法预估数据量、你需要频繁在头部插入删除、你不依赖随机下标访问。满足这三点单链表就是合理选择否则先用数组再说。最后分享一个我调试链表时的必做小事每写完一个操作立刻在主程序里调用show()把整个链表打出来对照自己的手绘图检查。链表这个数据结构的 bug 绝大多数出在“引用指向哪里”上而眼睛看代码不容易看出来打印一出来就原形毕露了。尤其是逆序操作我强烈建议你找一个 length 正好是 3 的链表每一步循环都打印一次prev.data、cur.data、nxt.data和当前链表形态把三轮迭代完整走一遍。把这个过程亲手走通之后单链表这门课的地基你就真的打扎实了。
单链表从原理到代码实现：建链、插入、删除与逆序全解析
很多人第一次接触单链表都会有同一种感觉书上画的那几个方框和箭头乍一看明明白白可真要自己从零写一遍从建链、遍历、插入到逆序每一步都藏着让你头皮发麻的细节。我当年学数据结构就是栽在“明白了原理”和“写出了能用”之间的那道坎上。上面也经常被刚开始学单链表的同学追问头插尾插怎么选、不带头结点到底怎么处理、指定位置插入为什么总是把链表搞断、用 Python 写逆序为什么和别人思路对不上。今天就把单链表这件事从头到尾掰开揉碎讲清楚背后的内存逻辑以及每行代码到底在干什么。这篇内容是写给两类人看的一类是正在学数据结构、被作业和考试折腾的在校学生另一类是自己刷题写算法、总感觉链表边界条件处理不好的自学者。我会用 Python 为主来写代码因为 Python 对初学者最友好、最能看清楚“引用”和“对象”之间的关系但其中的原理和易错点是语言无关的。你完全可以把这套思路平移到 C、Java、Go 里。下面我们从最根本的问题开始。1. 先搞清楚为什么数组做不到单链表却可以1.1 数组的三大软肋在理解单链表之前得先明白它到底解决了什么问题。很多人觉得链表比数组“高级”其实它不高级它只是换了一种存储思路。数组的本质是一块连续的内存空间下标就是偏移量。这种方式让随机访问极其高效但代价也很大。第一数组的长度一旦确定就很难改变。你开一个int arr[100]存到第 101 个元素怎么办只能重新开一个更大的数组把旧数据全部复制过去。这个操作的时间复杂度是 O(n)而且会带来临时的大内存消耗。Python 的 list 虽然号称“动态数组”背后其实也是这个套路只是替你自动扩容了底层依然要搬元素。第二在中间插入或者删除一个元素代价非常惨重。比如一个数组有 10000 个元素你想在第 5000 个位置插入一个新元素那么从第 5000 个到第 10000 个元素全部都要往后挪一格极端情况下就是 O(n) 次移动。删除也是一样后面的元素要往前补位。第三数组要求一整块连续内存。如果你的程序里有很多碎片化的内存块每个块都很小那么即便加起来总量足够也没办法给一个大数组用。这个问题在 C/C 这类直接管理内存的语言里尤其明显叫“外部碎片”。1.2 手拉手排队单链表的结构直觉单链表的思路完全反着来我不要求节点在内存里挨着每个节点可以散落在内存的任意角落然后让前一个节点记住后一个节点的位置用这种“记住下一个在哪”的方式把整个序列串起来。你可以想象一群小朋友手拉手排队。每个小朋友只需要记住两件事自己是谁数据以及后面拉着谁下一个节点的位置。队伍能不能走通不取决于大家站得密不密集只取决于有没有人把手松开。所谓“单”链表就是每个孩子只拉着后面一个孩子的手你只能从队头开始一个接一个地往队尾走想回头不行因为没有人记住前面的孩子是谁。这个直觉很快就引出一个关键性质链表的插入和删除只需要修改相邻节点之间的“牵手关系”其他节点完全不用动。中间插一个新同学只需要让前面的同学改拉新同学再让新同学拉原来的下一位其他所有人的手都不用松开。这比数组整体搬移的成本低太多。但也因为这种结构你失去了一样东西随机访问。数组你说arr[5]就能直接跳到第五个元素因为你知道起始地址一加偏移就到了。链表里的第五个元素在哪不知道必须从第一个开始顺着 next 一个个数过去。这一下就把访问某个节点的时间复杂度从 O(1) 拉到了 O(n)。所以说链表不是万能的它是用“访问慢”换来了“插入删除灵活”这一进一出就是数据结构里最经典的权衡。2. 单链表的积木怎么搭节点、指针域以及要不要带头结点2.1 一个节点身上必须有的两样东西单链表的基本单元是节点Node。每个节点必须包含两部分一部分存数据另一部分存“下一个节点在哪”。这两样缺一不可。数据域根据自己的需求随便定可以是整数、字符串、对象链接域就是指向下一个节点的引用在 Python 里就是一个普通属性。用代码定义一个节点类就这么简单class Node: def __init__(self, data): self.data data # 数据域 self.next None # 指针域初始指向空为什么初始next要设为None因为一个新节点刚造出来的时候它后面还没有接任何东西。每个链表的最后一个节点它的next也必须是None这是链表的“终止符”。判断一个链表走到头了靠的就是这个None。我在给学生讲的时候常说None就是链表的句号没有句号的链表是危险的遍历时会直接越界或者死循环。2.2 Python 里的“指针”到底指什么很多人学过 C 语言再看 Python 链表会犯迷糊Python 没有指针啊怎么写链表其实 Python 的对象引用机制本质上就是一个自动管理的指针。你写node_a.next node_b做的事情就是让node_a的next属性“指向”node_b那个对象。你可以用id()函数来验证a Node(1) b Node(2) a.next b print(id(a.next), id(b)) # 输出完全一样这说明a.next和b引用的是同一个内存对象。你通过a.next.data和b.data访问到的也是同一份数据。这就是链表的底层逻辑靠“引用”串起对象而不是靠物理上挨着。也正因为 Python 的引用是自动管理的你不需要像 C 语言那样手动malloc和free。节点没人引用的时候垃圾回收器会自动回收它。这对于理解链表是好事也是坏事好处是你不用纠结内存释放的时机坏处是你会因此忽略“断开引用”这件事的重要性。比如delete一个节点在 C 里你要手动free在 Python 里你只要让这个节点不再被任何变量引用它就自动被回收了。后面讲清空链表时这个区别很关键。2.3 带不带头结点差别有多大这是教材里最容易绕晕人的概念也是考试最爱考的地方。所谓“头结点”是指链表最前面额外加的一个哨兵节点它不存实际数据或者说不参与业务数据作用就是让所有操作统一。而“头指针”才是真正指向链表中第一个有效节点的变量。区分一下不带头结点的单链表head直接指向第一个数据节点。链表为空时head None。所有针对第一个节点的操作都要单独处理因为第一个节点没有前驱。带头结点的单链表head指向哨兵节点哨兵节点的next才指向第一个有效数据节点。链表为空时head.next None。因为哨兵节点永远存在所以链表中任何有效节点的删除和插入都有统一的前驱处理方式不需要特判“这是不是第一个节点”。这两者的差距一句话总结带头结点是拿一个“不存数据的空头头”换代码的简洁和统一不带头结点是省一个节点但每个边界操作都要多写 if。用不带头结点的方式删除第一个节点你需要写if head is None: return if pos 0: head head.next # 特殊处理头节点而带头结点时因为哨兵节点永远是第一个删除“第一个有效节点”对代码来说就是“删除哨兵节点的后继”跟删除第 N 个节点没有任何区别不需要那个pos 0的分支。很多教科书默认用不带头结点的写法因为它更贴近“指针直接指向节点”的底层概念但实际工程里带头结点的写法更不容易出错。下面我的代码示例采用不带头结点来演示因为这类写法对理解边界条件训练最充分但我会专门标注哪些地方是边界特判方便你以后切换到带头结点时能对应上。3. 建链的三种姿势头插、尾插、指定位置插入3.1 头插法新节点永远站在最前面头插法顾名思义每次新节点都插在链表的头部成为新的第一个元素。它的核心就两行def insert_head(self, data): node Node(data) node.next self.head self.head node这段代码的顺序非常重要。正确做法是先把新节点的next接到原来的头节点上再把head指针移动指向新节点。这个顺序一旦写反后果是什么如果你先执行self.head node原来的头节点就没人指向了你再想拿到它只能通过node.next但如果此刻你还没写node.next self.head旧的头节点就彻底丢了链表断成了两截其中一截变成垃圾。我见过太多人在这里栽跟头。记一句口诀先接后断先让新节点拉住老节点再让 head 指向新节点。头插法有一个很直观的特点如果你依次插入 1、2、3最后链表里存的顺序是 3、2、1和插入顺序正好相反。你可以用这个特点来做链表的“反转”后面讲逆序的时候还会用到这个思路。3.2 尾插法让链表保持输入顺序头插法有个麻烦顺序和输入反了。如果我们想按照 1、2、3 的顺序把数据存进去就需要尾插法。最简单的尾插是每次从head开始从头遍历找到最后一个节点然后在它后面接上新节点。刚学的时候这样写确实直观def insert_tail_simple(self, data): node Node(data) if self.head is None: self.head node return cur self.head while cur.next is not None: cur cur.next cur.next node注意这里必须判空链表为空时要插的节点就是第一个节点直接让head指向它。这个判断漏了空链表上执行cur.next会直接抛AttributeError。一个容易犯的错是写成while cur is not None而不是while cur.next is not None。前者会让循环停在最后一个节点的后面也就是cur变成None你回来再操作cur.next node就直接报错了。你要找的是“最后一个节点”判断标准是“这个节点的 next 是 None”而不是“这个节点是 None”。这种每次从头遍历的尾插法插入 n 个节点的时间是 O(12...n) O(n²)。数据量小无所谓数据量大就不划算了。更常见的做法是维护一个尾指针tail始终指向最后一个节点插入时直接在tail后面追加然后更新tail。这样插入就变成了 O(1)。不过这时你还要额外维护 tail 在删除等操作里的正确性工程上一旦忘了更新 tailbug 就冒出来了。初学者先用从头遍历的版本理解逻辑然后再去优化这是比较稳妥的学习路径。3.3 在指定位置插入先找前驱再动手“在指定位置插入”是所有插入操作里最综合的也是热搜词里出现频率很高的一个点。因为这里几乎涵盖了链表所有的边界情况。插入操作分三步走移动到要插入位置的前一个节点前驱。让新节点的next指向前驱原来的后继。让前驱的next指向新节点。核心代码def insert_at(self, pos, data): if pos 0: raise ValueError(位置不能为负数) node Node(data) # 插入到头部 if pos 0: node.next self.head self.head node return # 找到前驱节点 pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None: raise IndexError(位置超出链表长度) # 核心三步node.next 先指向后继pre.next 再指向 node node.next pre.next pre.next node这里同样要注意顺序问题。为什么必须先执行node.next pre.next再执行pre.next node因为pre.next里存的还是原来的后继节点你要让新节点接上它必须先把“后悔”拿到。一旦你先写了pre.next node原来的后继节点就只剩下node.next这一条路可以找回可这时候node.next还是None整个链表又断了。先接后断这个顺序在链表操作里是铁律插入如此后面讲删除时思路正好反过来。另外还要注意“移动几步”这个细节。要在位置pos0 为起点插入你要找到的是下标pos-1的节点。第一个节点下标是 0它的前驱是head不带头结点时插入头部是特例。写循环时从head开始向后移动pos-1次恰好停在pos-1号节点上。很多初学同学循环次数多写了或少写了插出来位置总差一位。我的习惯是先想清楚 push 前驱的下标再算循环次数最后拿一个只有两三个节点的链表手动走一遍循环验证自己写的代码。4. 表的基本操作实验查找、删除、清空一次跑通4.1 查找节点按值和按下标查找操作是链表里最暴露“链式结构”弱点的功能。数组按下标是 O(1)链表按下标必须从头走最坏情况 O(n)。代码很简单但这里我想聊的是它的“遍历模板”这几乎是所有链表操作的地基cur self.head while cur is not None: # 处理 cur 这个节点 cur cur.next按值查找第一个匹配的节点下标def find(self, val): cur self.head idx 0 while cur is not None: if cur.data val: return idx cur cur.next idx 1 return -1按下标返回节点def get(self, index): cur self.head i 0 while cur is not None and i index: cur cur.next i 1 if cur is None: return None return cur.data这个模板你一定要背到像呼吸一样自然。后面写逆序、写环检测、写两两交换节点全部都是在这个模板上做变形。4.2 删除节点指针域绕行删除一个节点本质上是让它的前驱“绕过”它直接指向它的后继。在链表的语境里被删除的节点本身可以不用去动等没人引用它之后垃圾回收会处理。def delete_at(self, pos): if self.head is None: return False if pos 0: self.head self.head.next return True pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None or pre.next is None: return False pre.next pre.next.next return True你看删除的核心只有一行pre.next pre.next.next。它把pre的下一个节点要被删除的节点直接从链表中跳过去了。这里最容易被忽略的是删除头节点要特判。因为头节点没有前驱不能走pre.next pre.next.next这条路只能直接让head head.next。这个问题在不带头结点的链表里必须单独处理。还有一点删除时返回False有两种情况一种是链表本来就空另一种是你要删的位置超出了链表长度。初学者写if pre.next is None经常漏掉结果要删除的节点不存在时代码老老实实跑到了pre.next pre.next.next但因为pre.next已经是None这一行直接抛异常。写边界条件从“最坏情况”开始推空链表、删头节点、删尾节点、位置超长把这四种情况都过一遍这个删除函数才算是能用的。4.3 清空链表不是把整个对象扔掉清空和删除单个节点的思路不一样。删除单个节点只是把某一个节点摘下来清空是要把链表里所有节点全部释放掉。在 Python 里最直接的做法是def clear(self): self.head None你可能觉得这也太简单了但这里藏着理解引用机制的关键self.head是链表唯一的外部入口。一旦你把它设为None从head出发的整条链就“够不着”了。所有节点都只被链表内部的前驱节点引用前驱不可达了后面的节点自然也不可达垃圾回收器会沿着引用链把它们全部回收。所以这一行确实能清空。但在教学场景和很多底层语言的实验里我们还会写更保险的“逐步断开”版本def clear(self): cur self.head while cur is not None: nxt cur.next # 先保存下一个节点否则断开当前节点后找不到下一个 cur.next None # 断开当前节点对下一个节点的引用 cur nxt self.head None这个版本在 C/C 里是必须的因为你得一个一个把节点free掉。在 Python 里它的意义更多在于当你手里还持有某个局部变量指向链表中某个节点时你只把head设为None那个节点不会立刻被回收因为它还被你的局部变量引用着它会带着它后面那一串节点继续存活。如果你想彻底释放整条链就得先遍历一遍把每个节点的next都断开再让外部引用失效。这就是“清空”这个操作背后真正的细节。4.4 一份可以直接跑的完整实验代码说了这么多把上面所有操作整合成一个完整可运行的实验代码建议直接复制到自己的环境里跑一遍边跑边打印每步结果class Node: def __init__(self, data): self.data data self.next None class SingleLinkedList: def __init__(self): self.head None def is_empty(self): return self.head is None def insert_head(self, data): node Node(data) node.next self.head self.head node def insert_tail(self, data): node Node(data) if self.head is None: self.head node return cur self.head while cur.next is not None: cur cur.next cur.next node def insert_at(self, pos, data): if pos 0: raise ValueError(位置不能为负数) node Node(data) if pos 0: node.next self.head self.head node return pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None: raise IndexError(位置超出链表长度) node.next pre.next pre.next node def delete_at(self, pos): if self.head is None: return False if pos 0: self.head self.head.next return True pre self.head i 0 while i pos - 1 and pre is not None: pre pre.next i 1 if pre is None or pre.next is None: return False pre.next pre.next.next return True def get(self, index): cur self.head i 0 while cur is not None and i index: cur cur.next i 1 return cur.data if cur is not None else None def find(self, val): cur self.head idx 0 while cur is not None: if cur.data val: return idx cur cur.next idx 1 return -1 def clear(self): self.head None def show(self): cur self.head out [] while cur is not None: out.append(str(cur.data)) cur cur.next print( - .join(out) if out else 空链表)我建议你在这个类上做两组小实验。第一组依次insert_tail(1)、insert_tail(2)、insert_tail(3)然后show()观察输出是不是1 - 2 - 3再insert_at(1, 99)观察是不是1 - 99 - 2 - 3。第二组试试空链表上delete_at(0)、超长位置上insert_at(5, 0)观察异常和返回值的表现。能把这两组实验跑明白单链表最基本的操作就过关了。5. 单链表逆序把每个节点的“箭头”掉头5.1 就地逆置的三指针法单链表逆序是教科书里最经典的进阶操作也是面试官最喜欢“抠细节”的题目。它的本质不是建一条新链表而是把原有每个节点的next方向调转让原来指向下一个的指针反过来指向上一个。很多人第一反应是新建一个链表遍历旧链表用头插法把每个节点插到新链表头部。这个思路没有错但它新建了一条链表空间复杂度是 O(n)面试官通常希望你做“就地逆置”也就是说不开新链表只改动原链表的指针方向空间复杂度做到 O(1)。就地逆置的标准写法是三指针法。需要三个指针prev、cur、nxt。prev初始为Nonecur初始为head。循环里做的事情用一句话说就是先用nxt保存cur的下一个节点再把cur.next掉头指向prev然后三个指针整体往后挪一位。def reverse(self): prev None cur self.head while cur is not None: nxt cur.next # 关键第一步保存后继 cur.next prev # 关键第二步掉头 prev cur # 关键第三步prev 前进 cur nxt # 关键第四步cur 前进 self.head prev # 循环结束时prev 指向原链表的尾节点作为新头很多第一次写这段代码的人会问为什么非要nxt cur.next直接cur.next prev不行吗不行因为cur.next prev执行完之后cur和旧链表后面那部分就断开了你手里的cur已经完全失去了通往后继的路。如果不提前把后继记在nxt里cur就再也找不到下一个节点了循环根本没法继续。所以在修改指针之前先保存后继这是所有链表变更操作的通用心法和前面讲的插入必须先接后断是同一个道理。一步一步看它怎么工作。假设链表是1 - 2 - 3 - None刚开始prevNone、cur1第一轮nxt21.nextNoneprev1cur2。此时链表被拆开了1成了新链表的尾部。第二轮nxt32.next1prev2cur3。第三轮nxtNone3.next2prev3curNone。循环结束self.head prev 3链表变成3 - 2 - 1 - None。时间复杂度 O(n)空间复杂度 O(1)所有操作都在原节点上完成。5.2 递归写法另一种思路递归也是一种很优雅的写法虽然它不满足 O(1) 空间递归栈会消耗 O(n) 空间但作为理解递归和链表结构相结合的练习题非常有价值。思路是先递归逆转当前节点之后的整条子链表再把当前节点接到子链表末端的后面。def reverse_recursive(self, node): if node is None or node.next is None: return node new_head self.reverse_recursive(node.next) # 此时 node.next 已经指向逆转后子链表的尾节点让这个尾节点指向 node node.next.next node node.next None # 防止成环 return new_head调用方式self.head self.reverse_recursive(self.head)。解释一下这里的两行关键操作。假设链表是1 - 2 - 3 - None递归进入1后先递归处理2 - 3处理完返回的新头是3此时子链表已经变成3 - 2并且2.next仍然指向原来的3实际上是环状的处境需要处理。回到处理1的层node是1node.next是2node.next.next就是2.next此刻它正好是子链表逆转后的“尾节点”2所以把2.next指向1也就是node.next.next node。再把1.next置为None整个链表变成3 - 2 - 1。这里有个必须断开node.next的原因如果不把1.next置为None1和2之间还保留原来的正向链接同时2又指向1这就形成了一个长度为 2 的环遍历会死循环。记住链表逆序本质上是在改箭头改完之后原来的正箭头要清掉不然就成环了。5.3 循环单链表的小补充热搜词里还有“循环单链表”这里简单提一下因为它和单链表的逆序、遍历边界直接相关。循环单链表就是把尾节点的next从None改回指向头节点这样整条链就变成了一个环。它的好处是你从任何一个节点出发都能走完整条链某些场景如约瑟夫环、轮转调度非常合适。但代价也很明显遍历的终止条件变了。普通单链表判断cur is None就结束循环链表里要判断cur.next is head或者cur is head才能结束一不小心就会死循环。用三指针法给循环链表逆序思路大体相同但最后要把新的尾节点也就是原来的头节点的next重新指回新的头节点换句话说既要改完每条边的方向还要保证尾接头的闭环关系不被破坏。我个人的建议是循环单链表先不要急着逆序先把普通单链表的逆序练到滚瓜烂熟再说两者在指针操作上的复杂度不是一个量级。6. 数组还是单链表从复杂度和真实工程场景做选择6.1 复杂度对比不能只看表面初学者经常背结论数组访问 O(1)、插入删除 O(n)链表访问 O(n)、插入删除 O(1)。这个结论对但只对了一半它忽略了一个重要前提链表插入删除的前提是你已经拿到了前驱节点。如果你要从头去找那个插入位置先花 O(n) 遍历再花 O(1) 改指针总复杂度依然是 O(n)。所以真正公平的比较是这样一张表操作数组单链表按下标随机访问O(1)O(n)按值查找O(n)O(n)在已知前驱处插入/删除O(n)需要搬移O(1)在头部插入/删除O(n)搬移全部元素O(1)在尾部插入O(1)动态数组均摊O(1)需维护尾指针或 O(n)需要遍历内存分配方式连续大块分散小块CPU 缓存友好度高低头插头删这个场景是单链表的绝对主场。数组要想在头部插入所有元素集体后移成本极高链表只需要 O(1) 改一下头指针。很多需要频繁在头部增删的数据结构比如用链表实现的栈、某些队列变体都会充分利用这个特性。6.2 真实工程里常见的单链表应用了解了复杂度之后你会惊讶地发现真实工程里单链表“裸用”的场合并没有想象中那么多但它作为基础组件藏在大量高级数据结构里。第一个经典应用是哈希表的链地址法。哈希冲突时多个键值对落到同一个桶里桶里放的就是一条链表。插入新键值对时直接头插O(1) 完成。Java 的 HashMap 在冲突较少时用的就是链表只是到了阈值才转红黑树。第二个经典应用是图的邻接表。一张有 n 个顶点的图可以用 n 条链表来存储出边每个顶点的链表里依次存放它所有的邻居节点。因为一个顶点的邻居数量是不确定的用链表天然支持动态增长比固定大小数组灵活得多。第三个是 LRU 缓存。完整的 LRU 一般用哈希表 双向链表但如果你只做简化版单链表也可以模拟“最近最少使用”的淘汰顺序每次访问一个节点就把对应元素移动到链表头部淘汰时删掉尾节点。虽然哈希表查不到节点位置会让移动变 O(n)但对理解“移动到头最近使用删除尾部淘汰最久”这个思想很有帮助。6.3 什么时候别用单链表单链表不是银弹选错场景会被性能按在地上摩擦。如果你需要频繁按下标随机访问比如写一个通过索引读数据的列表那必须用数组或动态数组。链表访问第 n 个节点要一步步走过去n 稍微大一点就肉眼可见地卡顿。如果你经常要从后往前遍历单链表直接劝退因为你根本没有向前走的指针只能每次从头走这种场景得用双向链表。还有个反直觉的点数组在“读多写少”并且容量可预估时性能反而比链表好很多。链表节点在内存里东一个西一个CPU 访问时要不断跳转缓存命中率低数组是连续内存遍历时 CPU 可以预取速度飞快。这也是为什么很多语言的标准库在实现动态数组如 Python list、C vector时宁愿频繁搬移元素也不轻易改用链表来当默认容器。工程里“内存连续”带来的速度优势很多时候比“插入删除 O(1)”更值钱。所以选择单链表的铁律大概是这三条你无法预估数据量、你需要频繁在头部插入删除、你不依赖随机下标访问。满足这三点单链表就是合理选择否则先用数组再说。最后分享一个我调试链表时的必做小事每写完一个操作立刻在主程序里调用show()把整个链表打出来对照自己的手绘图检查。链表这个数据结构的 bug 绝大多数出在“引用指向哪里”上而眼睛看代码不容易看出来打印一出来就原形毕露了。尤其是逆序操作我强烈建议你找一个 length 正好是 3 的链表每一步循环都打印一次prev.data、cur.data、nxt.data和当前链表形态把三轮迭代完整走一遍。把这个过程亲手走通之后单链表这门课的地基你就真的打扎实了。
