干货版《算法导论》03：动态数组 × 链表的极致平衡艺术

干货版《算法导论》03动态数组 × 链表的极致平衡艺术Bilibili 同步视频 链表 vs 动态数组天生的矛盾与互补✅ 链表Linked List✅ 动态数组Dynamic Array 关键概念什么是均摊时间复杂度Amortized 方案一双向预留空间・动态双端数组 实现逻辑⚠️ 必须注意缩容策略防抖动 方案二双动态数组拼接・零重新造轮子设计思想⚠️ 边界处理满分关键 实战硬核题单链表原地反转后半段✅ 三步绝杀思路 满分代码实现Python 性能分析 总结结构设计的终极美学Bilibili 同步视频干货版《算法导论》03动态数组 × 链表的极致平衡艺术在算法与数据结构的世界里链表与动态数组像是一对性格迥异的双子星✨—— 一个灵动善变一个沉稳高效。我们总在两端取舍要么要O (1) 两端操作要么要O (1) 随机访问却很少思考能不能二者兼得今天就带你拆解如何用极简思路打造「最坏 O (1) 查找 均摊 O (1) 两端动态操作」的究极结构再手把手搞定单链表原地反转后半段的硬核代码 链表 vs 动态数组天生的矛盾与互补先回顾两种基础结构的核心宿命✅ 链表Linked List优势头部 / 两端增删 O (1)只改指针不挪数据致命伤查找 O (n)内存离散必须从头遍历到目标位置✅ 动态数组Dynamic Array优势随机访问 O (1)地址偏移一步到位短板头部增删 O (n)要批量搬移元素成本极高 灵魂拷问有没有一种结构既能像数组一样秒查又能像链表一样两头随便插 / 删答案当然有就是我们要实现的「双向动态序列」——Dynamic Deque 关键概念什么是均摊时间复杂度Amortized很多同学对「均摊」一头雾水这里用最通俗的话讲透均摊复杂度 ≠ 平均复杂度平均对所有输入求期望均摊对同一数据结构的连续操作求总代价再平均严谨定义若一个操作均摊 O (k)则连续执行 n 次总耗时 ≤ n×k→ 哪怕单次偶尔很贵长期看依然稳如常数最经典例子Python listappend()偶尔扩容要 O (n)但 n 次插入总代价还是 O (n)→均摊 O (1)稳得一批 方案一双向预留空间・动态双端数组核心思路超简单给动态数组「前后都留空」不再只在尾部留余量 实现逻辑初始化时头部 尾部都预留线性空间头插 / 尾插直接填空位不用搬数据空间占满 / 太空整体重分配把元素挪到新数组中央用「计费法」保证每 O (n) 次廉价操作才触发一次昂贵重分配⚠️ 必须注意缩容策略防抖动只扩容不缩容 内存爆炸 频繁缩容扩容 性能抖动 安全缩容规则元素数量降到容量的 1/4 左右再缩缩完依然保留前后缓冲保证缩完后至少再经过 O (n) 次操作才需要再次调整这样就从根源避免「删一个就缩、插一个就扩」的震荡 方案二双动态数组拼接・零重新造轮子如果你不想手写新结构只想用现成动态数组如 Python list实现双端高效思路更妙用两个动态数组一正一反拼起来设计思想前半数组正常存负责尾部操作后半数组反向存负责头部操作访问时做一点下标算术即可模拟全局连续索引⚠️ 边界处理满分关键当其中一个数组变空时把另一个数组劈成两半重新分配到两个数组中恢复「前后都有缓冲」的不变量依旧满足均摊 O (1)两端操作 最坏 O (1)随机访问 实战硬核题单链表原地反转后半段题目约束拉满堪称面试高频杀招给定长度为2n的单链表禁止新建节点禁止非 O (1) 额外空间不能用数组 / 栈暂存原地修改把后 n 个节点逆序✅ 三步绝杀思路找中点走到第 n 个节点切分前后两半反转后半段指针只改 next 指向不挪数据修补首尾链接让前半段尾 → 新后半段头原后半段尾 → null 满分代码实现PythonclassListNode:def__init__(self,item):self.itemitem self.nextNoneclassLinkedList:def__init__(self):self.headNoneself.size0defreorder_students(lst:LinkedList): 反转单链表后 n 个节点总长度 2n原地、O(1) 空间 nlst.size//2ifn0:return# 1. 找到第 n 个节点 aalst.headfor_inrange(n-1):aa.next# 2. 反转 a 之后的 n 个节点ba.nextx_prev,xa,bfor_inrange(n):next_nodex.next# 先保存下家x.nextx_prev# 反转指针x_prev,xx,next_node# 3. 修补首尾a 指向新头旧头 b 指向 Nonecx_prev a.nextc b.nextNone 性能分析时间O(n)一趟遍历搞定空间O(1)只用到常数个临时变量完全满足题目所有严苛约束面试直接满分 总结结构设计的终极美学这一套内容本质是在教你数据结构设计的核心哲学空间换时间预留缓冲均摊昂贵操作不变量维护用简单规则保证结构稳定原地修改尽量复用已有节点 / 内存不造新负担最终我们得到✅最坏 O (1) 随机访问比链表强✅均摊 O (1) 两端增删比动态数组强✅原地、低空间、高性能这就是算法世界里最迷人的地方 ——不做取舍直接全都要。