Theory · Data Structure · Array & Linked List
顺序存储 vs 链式存储：寻址公式 · 动态数组均摊扩容 · 双指针 · 反转与判环 —— 一切线性结构的起点
连续内存 + 寻址公式 → O(1) 随机访问；动态数组用均摊扩容换长度自由
分散节点 + 指针 → O(1) 已知位置插删；代价是缓存不友好与 O(n) 定位
绝大多数场景数组赢——缓存局部性是现代 CPU 的一等公民
Why It Matters
① 取第 5 万条（翻页要显示它）；② 在第 5 万条后面插一条（用户新建）。听起来都是小事——但数据在内存里只有两种摆法，而每种摆法只擅长其中一个。这就是本 deck 全部矛盾的来源。
10 万条排成一条连续的内存带。取第 5 万条：拿公式算一下地址就到了，跟总共多少条无关；中间插一条：它后面的5 万条要全部往后挪一格。
每条待办单独占一小块内存，块里存一个"下一条在哪"的地址。中间插一条：改两个地址就完事；取第 5 万条：只能从第 1 条顺着路条走 5 万步。
摆法 A 就是数组，摆法 B 就是链表。后面所有线性容器——栈、队列、哈希表的桶、LRU——都是在这两块地基上加工出来的，所以它们必须先讲。
| 操作 | 挨着放（数组） | 分开放（链表） |
|---|---|---|
| 取第 k 条 | 一次计算到位 | 顺着走 k 步 |
| 中间插一条 | 挪动后面 n−k 条 | 改两个地址 |
| 末尾追加 | 通常直接写（偶尔搬家） | 改一个地址 |
| 整体顺序扫一遍 | 快：数据挨着，缓存顺带预取 | 慢：每跳一次都可能等主存 |
Prerequisites & Glossary
| 术语 | 一句话理解（细节后面展开） |
|---|---|
| 内存地址 address | 内存里每个字节的门牌号，用 0x1000 这样的十六进制数表示 |
| 连续内存 contiguous | 一段门牌号挨着的内存；数组就住在这样一段里 |
| 下标 index | 元素在数组里的第几号位（从 0 数），本身不是地址 |
| 寻址公式 | 由下标算出地址的算式：地址 = 起点 + 下标 × 每个元素多大 |
| 节点 node | 链表里的一小块内存：装一个值 + 一个"下一个在哪"的地址 |
| 指针 pointer | 值就是一个内存地址的变量；节点里的 next 就是指针 |
| 缓存行 cache line | CPU 从内存搬数据的最小单位，通常 64 字节——一次搬来一整块 |
| 均摊 amortized | 把偶发的大开销摊到多次操作上算平均，得到的"每次成本" |
| 容量 capacity | 已经申请好的格子数（cap），区别于已经用了几格（len） |
| 哨兵 sentinel / dummy | 特意加在头部的假节点，用来消灭"头节点特殊处理"的边界代码 |
复杂度分析 → O(1) / O(n) 怎么读，"均摊"到底摊的是什么
Go slice 底层 → 本 deck 的 Go 例子都以它为准（想深挖再去）
两种结构的唯一区别是："下一个元素在哪"这个问题怎么回答。
· 数组用「算」——地址可以由下标推导出来，所以能一步跳到任意位置；
· 链表用「存」——地址写在上一个节点里，所以必须一步一步走过去。
动态数组 = 数组 + "格子不够就换更大的一段连续内存"；双向链表 = 节点里多存一个"上一个在哪"；循环链表 = 最后一个的 next 指回第一个；跳表 = 给链表补几层索引，让它也能"跳"。
Two Ways Of Lining Up
把开场那两种摆法画出来就是下面两排：上排"挨着放"＝数组（地址靠算），下排"分开放"＝链表（地址靠存）。
Array · Contiguous Memory
addr(a[i]) = base + i × size——不依赖 i-1 的地址，也不需要任何遍历，所以下标访问是严格 O(1)、与数组长度无关。
① CPU 缓存预取：cache line 通常 64B，读 a[0] 时 a[1..7] 已顺带进缓存，顺序扫描近似免费；② 指针算术通用：多维数组、切片、字符串底层全是它。
中间插入/删除要整体搬移 O(n)；扩容要另找一块更大的连续内存并整体搬迁——这就是动态数组和均摊分析的故事（复杂度 deck）。
静态：长度编译期固定（Go 的 [N]T 是值类型，赋值即拷贝）；动态：长度运行期可变，本质是"结构体包着底层数组"（下一页 Go slice 视角）。
| 操作 | 复杂度 | 原因 |
|---|---|---|
| 下标访问 a[i] | O(1) | 寻址公式直接算 |
| 线性查找 | O(n) | 逐个比较 |
| 尾部追加 | 均摊 O(1) | 偶发扩容搬迁 |
| 中间插入/删除 | O(n) | 整体搬移保顺序 |
| 头插 | O(n) | 全体右移 |
Dynamic Array · Amortized Growth
所有语言的动态数组（Go slice / C++ vector / Java ArrayList / Python list）都是同一个抽象：指向底层数组的指针 + len（已用）+ cap（已分配）。len<cap 时追加零成本；len==cap 时触发扩容。
翻倍或 1.5 倍 → n 次追加总搬迁 < 2n~3n → 均摊 O(1)（证明见 复杂度 deck）。固定增量扩容是均摊 O(n)——面试的反面教材题。
删除到 1/4 才缩到 1/2（hysteresis 滞回）：如果"一半就缩、满了就扩"，在临界大小反复 push/pop 会触发 thrashing 抖动——每次操作都 O(n)。Java HashMap、vector 的 shrink 都留了缓冲带。
已知规模时先 make([]T, 0, n) / new ArrayList(n)，n 次 append 从"均摊 O(1) + 多次分配"变成"严格 O(1) + 一次分配"。高性能代码的肌肉记忆。
| 语言 | 扩容策略 | 备注 |
|---|---|---|
| Go slice | <256 翻倍；≥256 渐进 ≈1.25× | roundupsize 按内存规格对齐，实际 cap 常与直觉不符 |
| C++ vector | 1.5×（libc++/MSVC）或 2×（libstdc++） | 标准只保证几何级数，具体倍率看实现 |
| Java ArrayList | 1.5×（oldCap + oldCap≫1） | grow() 里位运算右移一位 |
| Python list | ≈1.125× 带超额预算 | listresize 的增长模式 new_allocated ≈ size + size/8 |
Go Slice · Header + Backing Array
Array Patterns · LeetCode
| 套路 | 适用信号 | 代表题 |
|---|---|---|
| 对撞双指针 | 有序 + 两端向中间收缩 | 两数之和 II(167)、盛水(11)、反转字符串(344) |
| 快慢同向指针 | 原地读写分离、去保留 | 删除重复项(26)、移动零(283)、移除元素(27) |
| 滑动窗口 | 连续子数组/子串 + 单调性 | 无重复最长子串(3)、长度最小子数组(209) |
| 前缀和 | 区间和/计数查询多次 | 区域和检索(303)、和为K的子数组(560) |
| 差分 | 区间批量加减后一次汇总 | 航班预订(1109)、拼车(1094) |
// 快慢指针：原地删除有序数组重复项 (LC 26) func removeDuplicates(a []int) int { slow := 1 for fast := 1; fast < len(a); fast++ { if a[fast] != a[slow-1] { a[slow] = a[fast] // slow 只写不读 slow++ } } return slow }
// 前缀和：pre[i] = a[0..i-1] 之和 (LC 303) func preSum(a []int) []int { pre := make([]int, len(a)+1) for i, v := range a { pre[i+1] = pre[i] + v } return pre // sum[i..j] = pre[j+1]-pre[i] }
Linked List · Pointer Chasing
Operations · Sentinel Trick
插入/删除在已知位置指针处是 O(1)；但删除单链表节点需要前驱——找到前驱本身要 O(n)。双链表自带 prev 才做到"拿到节点就 O(1) 自删"。
删头、头插、删到空——链表题 80% 的 bug 在头节点特判。dummy 哨兵节点统一了"头和中间"：在 dummy 后面做操作，永远不用单独处理头，返回 dummy.Next。
头插 O(1) · 尾插 O(1)（带尾指针）/ O(n)（不带）· 查找 O(n) · 删给定节点 O(n)（找前驱）/ O(1)（换值法，见 QA10）。
每节点多付 1~2 个指针（8~16B）；节点分散导致分配开销与碎片；Go 里 type Node struct{ Val int; Next *Node } 逃逸到堆，GC 压力比连续数组大。
// dummy 哨兵：删除链表所有 val 节点 (LC 203) func removeElements(head *ListNode, val int) *ListNode { dummy := &ListNode{Next: head} cur := dummy for cur.Next != nil { if cur.Next.Val == val { cur.Next = cur.Next.Next // 跳过即删除 } else { cur = cur.Next } } return dummy.Next // 头被删也不怕 }
Reverse · Fast & Slow Pointers
// 反转链表 · 三指针迭代 (LC 206) func reverseList(head *ListNode) *ListNode { var prev *ListNode cur := head for cur != nil { next := cur.Next // 1. 先存后继 cur.Next = prev // 2. 掉头 prev = cur // 3. 双双前进 cur = next } return prev // 新头 } // 递归版：reverse(head) = 接在已反转的 // head.Next 之后；时间 O(n)、栈深 O(n)—— // 长链表在 Go 里会栈溢出，首选迭代。
中点(LC 876)：slow 一步 fast 两步，fast 到尾时 slow 在中点（偶数个返回第二个中点，方便断链）。
判环(LC 141)：环内 fast 相对 slow 每轮近 1 步，必相遇（不会跳过）。
找环入口(LC 142)：相遇后一头一 slow 同速走，再相遇即入口。
倒数第 k(LC 19)：fast 先走 k 步，再同步走。
设头到入口 a、入口到相遇点 b、环长 L：slow 走 a+b，fast 走 a+b+nL；由 fast=2×slow 得 a = (n−1)L + (L−b)——头出发的指针和相遇点出发的 slow 同速前进，恰在入口汇合。
只要相对速度与环长互质成立（速度差 1 最显然），fast 逐步逼近 slow 不存在"跳过"：每轮距离减 1，减到 0 必相遇。速度差为 2 时在偶数环长上才可能跳过——这也是判环永远用 1:2 的原因。
Pointer Gymnastics · Visualized
LeetCode Shortlist
| 套路 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 快慢同向 | 26 删除有序数组重复项 E · 283 移动零 E · 27 移除元素 E | slow 写 fast 读，读写分离 |
| 对撞指针 | 167 两数之和 II M · 11 盛最多水的容器 M · 344 反转字符串 E · 125 验证回文串 E | 两端收缩，跳过不可能组合 |
| 前缀和/差分 | 303 区域和检索 E · 560 和为 K 的子数组 M · 1109 航班预订 M | 560 还要用哈希计前缀出现次数 |
| 链表反转 | 206 反转链表 E · 92 反转链表 II M · 25 K 个一组翻转 H | 25 = 分组反转 + 组内 206 + 接回 |
| 快慢指针 | 876 中间节点 E · 141 判环 E · 142 环入口 M · 19 删倒数第 N M | 142 要会 a=(n−1)L+c 推导 |
| 合并/删除 | 21 合并有序链表 E · 203 删指定值 E · 237 删给定节点 M · 160 相交链表 E | 160 用"互换轨道"消除长度差 |
Array vs Linked List
| 维度 | 数组 / 动态数组 | 链表 |
|---|---|---|
| 内存布局 | 连续，一次分配 | 分散，每节点一次分配 |
| 随机访问 | O(1) 寻址公式 | O(n) 指针追踪 |
| 已知位置插删 | O(n) 搬移 | O(1)（单链表删需前驱） |
| 缓存局部性 | 好：64B cache line 顺带预取，顺序扫描近内存带宽 | 差：指针追踪 ~100ns 主存访问，可能逐节点 miss |
| 额外空间 | 扩容预留 ≤ 1/2（倍增） | 每节点 8~16B 指针 + 分配器开销 |
| 二分/ SIMD 友好 | 可二分、可向量化 | 均不可 |
① 需要 O(1) 自删 + 迭代器稳定：LRU（双链表+哈希）；② 频繁头尾操作：deque 内部也常用块状链；③ 函数式/不可变结构共享尾节点。Go 标准库 container/list、Java LinkedList 实战中都很少被选。
Across Languages
| 语言 | 动态数组 | 链表 | 要点 |
|---|---|---|---|
| Go | slice（header + 底层数组） | container/list（双向循环） | [N]T 是值类型；slice 语义见 slice deck |
| Java | ArrayList（1.5× 扩容） | LinkedList（双链表，也实现 Deque） | 官方推荐 ArrayDeque 做队列/栈——LinkedList 很少是对的选择 |
| C++ | std::vector（1.5×/2×） | std::list（双）· forward_list（单） | vector 是默认容器；list 只在稳定迭代器/O(1) 拼接时用 |
| Python | list（动态数组） | 无内置链表；collections.deque（块状双向） | deque 栈/队列双修；链表要手写或用第三方 |
Cheat Sheet
| 操作 | 数组 | 链表 |
|---|---|---|
| 按下标取第 k 个 | O(1) 寻址公式 | O(k) 顺着走 |
| 查找某个值 | O(n)（有序可二分 O(log n)） | O(n)，不可二分 |
| 尾部追加 | 均摊 O(1) | O(1)（带尾指针） |
| 已知位置插/删 | O(n) 搬移 | O(1)，单链表需先有前驱 |
| 头部插/删 | O(n) | O(1) |
| 额外空间 | 扩容预留 ≤ 1/2 | 每节点 8~16B 指针 |
| 默认选择 | 动态数组（slice / vector / ArrayList）——缓存友好，四门语言的默认容器 |
| 需要 O(1) 自删 | 双向链表 + 哈希：LRU 的标准结构 |
| 需要 O(1) 拼接大段 | 链表（改两个指针）；数组要整体拷贝 |
| 迭代器/元素地址必须稳定 | 链表（扩容不会搬迁节点） |
| 要二分 / 向量化 / 顺序扫 | 只能数组 |
| 快慢同向指针 | slow 只写不读，fast 负责扫——原地去重/移零 |
| 前缀和 | pre 长度 n+1，sum[i..j] = pre[j+1]-pre[i] |
| 反转链表 | 三步固定：存后继 → 掉头 → 双双前进，prev 是新头 |
| dummy 哨兵 | 结果头不确定就上 dummy，最后 return dummy.Next |
| Floyd 判环 | 1:2 速度必相遇；入口用 a=(n−1)L+c，头与相遇点同速再走 |
| cap 内 append | 子切片 append 会覆盖原切片元素；扩容后才彻底分离 |
| 缩容抖动 | "满就扩、半就缩"会在临界点反复搬迁；要留滞回缓冲带 |
| 递归反转爆栈 | 栈深 O(n)，长链表首选迭代版 |
| 改 next 前没存后继 | 断链，后面全丢；顺序永远是"先存再改" |
| LC 237 换值删 | 不能删尾节点，且删的是"值"不是那个对象 |
Interview QA · Part 1
先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的翻回上一页速查表。
连续内存 + addr = base + i×size：地址一步算出，与 n 无关。链表要沿指针走 i 步，所以是 O(i)。
len<cap 时 O(1)；写满触发扩容 O(n) 整体搬迁。倍增下 n 次 append 总代价 < 3n → 均摊 O(1)（证明见复杂度 deck 第 9/10 页）。
旧 cap <256 直接翻倍；≥256 走渐进增长（约 1.25× 平滑过渡，Go 1.18+），再经 roundupsize 按 size class 对齐——所以实际 cap 常与估算不符。详见 slice deck。
改 s2[0]：变（同一底层数组）。append：若 len<cap 仍写进原数组（覆盖 s1 的元素，最阴险）；cap 满则 growslice 新数组，之后彻底分离。判据永远是 header 里的 Data 指针指向谁。
前提是已拿到插入/删除位置的指针。单链表删除还需前驱，定位前驱要 O(n)；双链表自带 prev 才是真正"拿到节点即 O(1) 自删"。
数组顺序访问顺带把后续数据装进缓存（预取器友好）， miss 率极低；链表节点分散，指针追踪一次 ~100ns 主存延迟。省下的搬移是 memcpy（快），付出的是 cache miss（慢）。
递归深度 = 链表长度，百万节点在 Go 里直接爆栈（Go 无尾调用优化）。迭代三指针 O(1) 空间才是工程首选；递归版价值在"证明你懂指针语义"。
进环后 fast 每轮比 slow 多走 1 步，两者距离每轮减 1，从"环长"一路减到 0，不存在跳过。速度差为 2 以上时才可能跨过对方（这也是为什么判环固定用 1:2）。
Interview QA · Part 2
同样先自答再对照。这一页的题都要"结论 + 一句边界/代价"才算完整——只答结论会被继续追问。
slow 每步 1、fast 每步 2，循环条件 fast != nil && fast.Next != nil：奇数个停在正中，偶数个停在第二个中点——正好方便左断右反转（回文链表题的标准起手）。
把 next 节点的值拷进来，再删 next：node.Val = node.Next.Val; node.Next = node.Next.Next。限制：不能是尾节点（无值可换）；语义上删的是"值"不是"那个对象"。
头节点可能被删/被换/被插——有了 dummy，头与中间节点走同一套代码，返回 dummy.Next。凡是"结果头不确定"的题（删、合并、分组反转）一律 dummy 起手。
每节点多一个 prev（8B/64 位机）。换来：O(1) 自删与删前驱、O(1) 反向遍历、O(1) 在尾操作（带尾指针）。LRU 必须双链表——命中的节点要原地摘下移到头部。
双指针逐节点摘小者接入 dummy 链，O(m+n) 时间 O(1) 空间。它是归并排序的子过程——数组版归并因搬移用辅助数组，链表版天然 O(1) 空间。递归写法优雅但栈深 O(m+n)。
环形缓冲区（音频/网络包）逻辑上是循环数组；Linux 内核 list_head 是双向循环链表（非空环，省去头尾特判）；约瑟夫问题、时间轮定时器都是环语义。Go container/list 也是带头节点的双向循环。
① 每次改 next 前在纸上画箭头图；② 三个边界用例过一遍：空表、单节点、头/尾操作；③ 检查是否断链（先把 next 存下来再改）。面试官说"可以画图"时，画——那是送分提示。
Related & References
栈与队列 →（受限线性表，含单调栈）
哈希表 →（拉链法用的就是链表）
跳表 →（给链表加索引，找回 O(log n)）
堆与优先队列 →（TopK 场景对比）
LRU 缓存 →（双链表 + 哈希的正当场景）
复杂度分析 →（扩容均摊 O(1) 的证明）
二分与对撞指针 →（有序数组的黄金搭档）
排序算法 →（合并有序链表 = 归并子过程）
Go slice 底层 →（growslice 全流程）
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch10 · Elementary Data Structures | 数组/链表的形式化定义与操作代价 |
| go.dev/blog/slices · go.dev/ref/spec | Go 官方：slice 语义、共享底层数组、append 行为 |
| src/runtime/slice.go · growslice | <256 翻倍 / ≥256 渐进 1.25× / roundupsize 对齐（对照本仓库 slice deck） |
| U. Drepper · What Every Programmer Should Know About Memory | cache line / 预取 / 局部性的硬件依据 |
| LeetCode 题单（206/141/142/21/25/84 等 · 完整清单见第 11 页） | 套路与代表题解对照 |