线性表与链表增删改查全解析：从顺序表到单向链表的核心原理与手写实现

上个月面完那家公司的二面之后，我把面试官问过的题目列了一个清单，发现一个扎心的事实：十道题里有六道绕不开“链表”这两个字。虽然刷题平台上的题解看得懂，可真要我当场手写一个链表的插入删除，我却总在边界条件上卡壳。空指针、改错连接顺序、遍历越界……这些坑踩一次就够。痛定思痛，我给自己定了一个“数据结构七天打卡”计划，Day1的任务就是把最基础的线性表彻底搞明白，尤其是链表的增删改查。

这篇笔记就是Day1的完整记录。它写给三类人：刚刚开始接触数据结构的学生、正在准备笔面试的求职者、以及想快速回顾基础概念的开发者。如果你之前也跟我一样，把链表的代码背了就忘，那这篇应该能帮你把逻辑真正立起来。

1. 为什么要从“线性结构”开始学数据结构

1.1 数据结构的“最小闭环”

很多人学数据结构一开始就扑向二叉树、图，结果被指针和递归搞得怀疑人生。我个人的建议是：先老老实实把线性结构吃透。为什么？因为线性结构是数据结构的“最小闭环”——存储、遍历、插入、删除、查找这些最核心的动作，都能在线性表上完整地过一遍，而且逻辑足够直观，不容易上来就劝退。

数据结构本质上回答两件事：数据怎么组织，组织好了之后怎么操作。组织方式决定操作的代价。就好比你要管理一堆书：全部摞在一个箱子里，找某本书只能翻；在每本书上写好编号并按顺序排好，查找就快；但如果经常要在中间加一本书或抽掉一本，排序存放又会很麻烦。线性表就是这种“一维书架”的抽象。

学完线性表，你手里就有了“组织数据”和“评估代价”这两套基本动作。后面不论是学树、图还是哈希表，本质上都逃不开这套思维。这也是我为什么把Day1定为线性表的原因——它是整个数据结构的起点，也是面试手写代码时出现频率最高的基础题型。

1.2 线性表两大阵营：顺序表vs链表

线性表有两种主流的实现方式：顺序表和链表。

顺序表用一段连续的存储空间来存放数据，我们平时用的数组就是它的典型代表。优点是按下标访问的时间复杂度是O(1)，CPU缓存友好；缺点是插入和删除要移动大量元素，平均O(n)。因为数据在内存里是挨着放的，要插一个进来，后面的所有元素都得往后挪一步。

链表则用一组不连续的内存节点串起来，每个节点除了存数据，还要存“下一个节点在哪”。插入和删除的时候只需要修改指针，不需要移动数据本身，所以平均O(1)；但查找某个位置要沿着指针一个个走，是O(n)。

这两者没有绝对优劣，只有适不适合当前的场景。这个表我记在笔记第一页，之后做题选数据结构的时候会经常用：

1.3 一个生活类比帮你建立链表直觉

我跟完全零基础的朋友解释链表时经常用一个类比：传话游戏。一群人排成一排，每个人只知道“我后面那个人是谁”。现在要在中间某个位置插一个新人，只需要让前面那个人把手指向后改为指向新人，新人指向原来的下一个人就行，后面的人完全不用动。这个“只改指针、不动位置”的思想，就是链表的核心。

顺序表则是另一幅画面：像电影院座位，每个人都固定在某个编号上。要往中间插一个人，后面的所有人都得站起来挪一个位置。直观感受一下，这个成本就高多了。

把这两个画面在脑子里立起来，再看后面的增删改查代码，你会觉得每个操作都是在做“谁指向谁”的连线题，而不是在背晦涩的语法。

2. 链表的核心原理与第一版代码

2.1 节点到底是个什么东西

链表的基本单元叫节点。每个节点有两部分：数据域和指针域。数据域存放真正的数据，指针域存放下一个节点的地址。在Python里，这个“地址”就是引用；在C/C++里就是指针。

我们之所以先学单向链表，是因为它是理解一切动态数据结构的地基——双向链表只是多了一个prev指针，循环链表只是尾节点next指向头节点，树和图本质上也是一堆节点加上不同的指针指向关系。地基打稳了，后面全是变体。

用Python定义节点类，最简洁的写法是这样：

class ListNode: def __init__(self, val=0, next=None): 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已经是None，None没有.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 = None，C节点以及之后的所有节点就全从链表里断开了，再也找不回来。

4.3 验证链表正确性的土办法

写完链表操作怎么验证？除了单测框架，我推荐两个土办法，但都特别好用。

第一个是遍历打印。写一个traverse方法，从头走到尾打印每个节点的值。插入3个节点就应打印出3个值，删除1个节点就应少1个值，顺序对不对一眼就看出来。这是我日常调试链表的第一检查工具。

第二个是画图走查。拿纸笔，用一个“1 -> 5 -> 9”的三节点链表模拟一次中间插入和一次中间删除，把每一步的next指向变化写出来，再对照代码逐行看。这招虽然费时间，但对理解指针关系极其有效，尤其是处理复杂一点的中间插入时，画三分钟图能省半小时debug时间。

这两个土办法看起来不够“高科技”，但应对链表这级复杂度绰绰有余。真正写链表出错，从来不是逻辑复杂，而是基础动作没练透。

5. 面试与自测阶段的延伸思考

5.1 复杂度对比表：什么时候用链表

学了增删改查之后，一定要回到复杂度这个根本问题上来。我把顺序表和链表的操作复杂度画成一张表，贴在笔记里反复看：

这张表能帮你做题时做决策：频繁在头部插入删除，选链表；频繁按下标随机访问，选顺序表；频繁在尾部追加，顺序表更合适，但要注意扩容问题。当然，还有“双向链表”“循环链表”这些变体，会让尾插变成O(1)，那部分留给Day2。

5.2 从单向到双向、循环：Day2的预告

单向链表的增删改查，说到底核心就是一句话：通过前驱节点改变指针指向。

一旦这句话搞明白了，Day2该学什么就很清晰：

• 双向链表解决“往前找”的问题，每个节点多一个prev指针，删除某个节点时不用再费劲找前驱；
• 循环链表解决“最后一个节点还要回到开头”的问题，尾节点的next指向头节点，遍历时要注意死循环；
• 栈和队列这两种受限线性表，本质上就是“插入删除位置被锁死”的线性表，栈只在一端操作，队列一端进另一端出；
• 再往后，链式二叉树不过是“每个节点有两个孩子指针”的扩展，理解了链表的节点思想，树的概念也会更容易接受。

我打算按这个顺序继续往下打卡。如果你也在学数据结构，建议你也把“为什么需要它”放在“它的代码怎么写”前面——理解了动机，代码只是翻译。

最后记录一下今天的真实感受：一开始我以为链表难在代码，后来发现难在想象。那些next的箭头，不在纸上画过一遍，永远只是抽象概念。

今天这个Day1把基础概念和增删改查过完，我已经能很顺地写出一份不带bug的链表操作实现了。最大的收获不是代码本身，而是建立了一种意识：每次改指针前先问自己，如果链表为空怎么办，如果指针指向None怎么办，如果顺序反了是不是会丢节点。带着这种意识去写，报错会少很多。

下一篇我打算用C语言再实现一遍，把内存管理的细节也补上，顺便把双向链表和循环链表一起收拾掉。如果你也对数据结构打卡感兴趣，可以从链表的一个简单实现开始，亲手画一遍图，跑一遍代码。这条路刚开始看起来很长，但只要第一天不放弃，后面会越来越顺。