知识点深化 · 数据结构 · 数组与链表
数组与链表：连续存储 vs 指针串联
数组和链表是所有数据结构的地基。数组像一排紧挨着的储物格，按下标秒取，但插中间要搬全家；链表像手拉手的队伍，随便插删，但找第几个得从头数。这一页把两种结构的内存长相、复杂度取舍和手写实现一次讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：对比"连续格子"和"指针手拉手"，搞懂为什么数组能按下标跳、链表不能。
2记复杂度表（15 分钟）
读④：背下增删查改四种操作在数组/链表下的时间复杂度。
3手画链表操作（20 分钟）
精读⑤：跟着画一遍头插、中间删、反转链表的指针变化。
4刷题纠错（15 分钟）
做⑦⑩，错题回到⑥找原因。
本课小目标学完你要能：① 画出数组与链表的内存示意图；② 说出随机访问 O(1)、中间插删 O(n) 的原因；③ 能手写链表的插入、删除、反转。
② 一图看懂：数组 vs 链表全地图
读法：中心是线性表，左数组右链表，对比存储方式、访问、插删，下方是应用与易错。
③ 本质直觉：数组是一排紧挨着的储物格，链表是手拉手的队伍
数组：内存里一整块连续格子，第 0 格地址 = 起始地址，第 i 格地址 = 起始 + i×步长。所以给 i 立刻算出地址，随机访问 O(1)。但要在中间插一个元素，后面所有格子都得往后挪一格。
链表：每个节点是个小包裹，里面装数据和一个指向下一个包裹的指针。节点在内存里东一个西一个，靠指针串起来。插删只要改指针，但想找第 k 个，只能从头顺着 next 一个一个数。
一句话：数组快在"读"，链表快在"插删（已知位置时）"。动态数组（如 Java ArrayList、Python list）是折衷：底层数组 + 满了就扩容拷贝。
为什么数组能 O(1) 随机访问地址 = base + index × size。CPU 一条加法就能算出任意元素位置，不用挨个找。链表节点散落在堆里，没有这个公式。
④ 完整体系与对比表
复杂度对比总表
| 操作 | 数组 Array | 动态数组 ArrayList | 单链表 |
|---|
| 随机访问 by index | O(1) | O(1) | O(n) |
| 头部插入 | O(n) 全搬 | O(n) | O(1) |
| 尾部插入 | O(1)（未满） | 均摊 O(1) | O(1)（有尾指针） |
| 中间插入（已知位置） | O(n) | O(n) | O(1) 改指针 |
| 按值查找 | O(n) | O(n) | O(n) |
| 空间开销 | 可能预留浪费 | 扩容拷贝 | 每节点多一个指针 |
动态数组的扩容机制
普通数组容量固定，装满就报错。动态数组（Java ArrayList、C++ vector、Python list）在装满时：① 申请一块更大的新数组（通常 1.5 或 2 倍）；② 把旧数组元素逐个拷贝过去；③ 释放旧数组；④ 把新元素放进去。
均摊分析扩容本身 O(n)，但不是每次都扩——连续 n 次插入只触发 1 次扩容，均摊后单次插入 = O(1)
链表节点定义（C/Java 类比）
class Node { int val; Node next; } 每个节点存一个数据 + 一个 next 引用。
头插法（O(1)）
Node n = new Node(x); n.next = head; head = n; —— 先把新节点 next 指向老 head，再让 head 指向新节点。顺序不能反，否则老链表全丢。
删除节点（已知前驱 prev）
prev.next = prev.next.next; —— 跳过待删节点，让前驱直接连到下下个。
反转链表（三指针）
prev=null; while(curr){ t=curr.next; curr.next=prev; prev=curr; curr=t; }
⑤ 用法场景与典型例题
例1（复杂度）在长度为 n 的数组末尾插入一个元素，平均时间复杂度？
末尾插入不搬移，直接放。
数组末尾有空位时直接写入 O(1)；但动态数组满了要扩容拷贝一次 O(n)。均摊分析下连续插入 n 次只扩容 log n 次，总拷贝量 O(n)，均摊单次 = O(1)。
例2（链表删除）已知单链表中待删节点 node（不是尾节点），如何 O(1) 删除？
拿后继节点覆盖自己。
常规删除要找前驱需 O(n)。巧法：node.val = node.next.val; node.next = node.next.next; —— 把后继的值拷到自己身上，再删掉后继。等价于删了自己。答案：O(1)（尾节点除外）。
例3（反转链表）链表 1→2→3→∅，反转后？
三指针逐个翻转 next 指向。
① prev=null, curr=1；② t=2, 1.next=null, prev=1, curr=2；③ t=3, 2.next=1, prev=2, curr=3；④ t=null, 3.next=2, prev=3, curr=null 结束。答案：3→2→1→∅，head 指向 3。
做题心法链表题画指针图！每改一次箭头就在纸上描一遍，记住"先存下一个节点再改指向"，否则 next 一丢整条链就断了。
⑥ 高频错误诊断（4 条）
错误1：链表插入顺序写反head=n; n.next=head; 是错的！先让 head 指向新节点，老 head 就找不到了。必须 n.next=head; head=n; 先存后继再改头。
错误2：以为链表随机访问快链表找第 k 个要从头数 k 步 O(n)，比数组 O(1) 慢得多。链表快的是"已知位置的插删"，不是查找。
错误3：扩容时不拷贝旧数据动态数组扩容只申请新数组不搬旧元素，旧数据全丢。必须把旧数组逐元素复制到新数组。
错误4：删除链表节点后不处理尾节点"后继覆盖法"删除要求 node 不是尾节点。尾节点没有后继可借，仍需遍历找前驱 O(n)。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 数组随机访问 | 问 a[i] 为什么 O(1) | 地址=base+i×size，一条加法算出 |
| 链表插删 | 问已知位置插删复杂度 | 改指针 O(1)，但找位置要 O(n) |
| 动态数组扩容 | 问均摊复杂度 | 连续插入只偶发扩容，均摊 O(1) |
| 反转/删除 | 手写指针操作 | 先存 next 再改指向 |
真题基础1. 数组能在 O(1) 时间访问任意下标的元素，根本原因是？
真题中档2. 在单链表中删除一个已知地址的中间节点（非尾），时间复杂度是？
真题中档3. Java ArrayList 尾部 add 操作的均摊时间复杂度是？
真题拔高4. 关于单链表反转，下列哪步最先做才不会断链？
⑧ 必背知识点卡
数组：连续内存，下标 O(1)，中间插删 O(n) 搬格子
链表：节点离散，next 指针，已知位置插删 O(1) 查找 O(n)
动态数组：满了扩 1.5~2 倍并拷贝 均摊 O(1)
头插：新节点 next=head，再 head=新节点 顺序别反
删节点：prev.next=prev.next.next 跳过它
反转：prev/curr/t 三指针，逐个反向 先存 next
选型：读多写少用数组，频繁中间插删用链表 按场景选
⑨ 应用输出：设计一个用户在线列表（头插 + 遍历）
场景：聊天室要把最新进入的用户显示在最前面，且经常删除离开的人。
① 选型：频繁头部插入与删除 → 用单链表（头插 O(1)）；若还要按用户 ID 快速查找，再配一个哈希表存 id→节点。
② 新用户进来：头插法 n.next=head; head=n;，新用户立刻排在最前。
③ 用户离开：若哈希表能拿到其前驱，prev.next=prev.next.next 一步删除；否则从头遍历。
④ 展示在线名单：从 head 顺着 next 遍历到 ∅，逐个打印昵称——天然就是"最新在前"。
⑤ 为什么不用数组：头部插入要把所有人往后挪，人一多就卡。
口述思路合上书说一遍："在线列表头部频繁增删，选链表头插；要快速删除就配哈希表存节点位置。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础1数组在内存中是否连续？
连续。这是它能按下标 O(1) 访问的前提。
基础2单链表最后一个节点的 next 指向什么？
null / ∅，表示链表结束。
基础3数组中间插入一个元素要移动多少元素？
该位置之后的所有元素，共 O(n) 个。
基础4链表每个节点额外存了什么？
一个指向下一节点的指针/引用。
基础5动态数组满了怎么办？
申请更大容量的新数组，拷贝旧元素过去。
基础6随机访问快的是数组还是链表？
数组 O(1)；链表 O(n)。
▍中档 6 题
中档7长度 100 的数组，在下标 10 处插入元素，要移动几个？
下标 10 到 99 共 90 个元素后移一位。
中档8链表头插第一步为什么是 n.next=head？
先把老链表接到新节点后面，否则老 head 丢失断链。
中档9为什么动态数组扩容选 1.5~2 倍而不是 +1？
+1 每次都要拷贝 O(n)，总复杂度 O(n²)；翻倍后均摊 O(1)。
中档10单链表找倒数第 k 个节点怎么做？
快慢指针：fast 先走 k 步，再同速走，fast 到尾时 slow 即倒数第 k。
中档11数组 vs 链表，谁缓存友好？
数组：内存连续，CPU 预取命中率高；链表节点离散，缓存容易失效。
中档12双向链表相比单链表多了什么？
多一个 prev 指向前驱，删除自身可 O(1)，但每节点多耗一个指针。
▍拔高 6 题
拔高13为什么说单链表删除尾节点仍是 O(n)？
尾节点没有后继可覆盖，必须从头遍历找前驱。
拔高14反转递归版怎么写？
reverse(head)=!head||!head.next?head:reverse(head.next); head.next.next=head; head.next=null;
拔高15判断链表有环用什么方法？
快慢指针：fast 走 2 步 slow 走 1 步，相遇则有环。
拔高16扩容时旧数组内存何时释放？
拷贝完成、引用切到新数组后，旧数组成为垃圾被回收；C/C++ 需手动 free。
拔高17顺序表和链表的选择依据是什么？
看操作模式：随机访问多/容量预知用数组；频繁头尾插删/长度未知用链表。
拔高18数组实现队列为什么要"环形"？
普通数组队头出队后前面空位浪费，环形数组取模复用空间，避免假溢出。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 数组连续下标快，链表离散指针连。② 头插先接后改头，反转先存 next 再翻。③ 扩容翻倍均摊 O(1)，缓存数组更友好。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画数组与链表内存图 | 能说出 O(1) 访问的原因 |
| 第 2 天 | 背复杂度表 + 基础 1-6 | 四种操作复杂度全对 |
| 第 3 天 | 做中档 7-12，手写头插/删除代码 | 指针顺序写不错 |
| 第 4 天 | 做拔高 13-18，推导快慢指针找环 | 能讲清相遇原理 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写反转三指针 | 不看资料全默对 |
← 返回软件技术总览