02 数组与链表 — 连续 vs 离散

李永乐式比喻：

• 数组 = 电影院连排座位。你知道第 3 排 5 号在哪，因为座位是连续的，用公式直接算出来。
• 链表 = 寻宝游戏的线索条。每张纸条上写着"下一个线索在 XXX"，必须从头开始找。
• 扩容 = 电影院满座了，包下隔壁更大的影厅，所有人搬过去。

---

名词映射

英文	中文	本质	比喻
Array	数组	连续内存块，相同类型	电影院的联排座位
Linked List	链表	分散内存块，通过指针连接	寻宝游戏的线索链
Random Access	随机访问	直接通过下标 O(1) 找到元素	直接报座位号
Sequential Access	顺序访问	从头开始逐个遍历	顺着线索条一张张找
Node	节点	链表的基本单元（数据 + 指针）	一张线索纸条
Head	头结点	链表的入口	第一条线索

---

结构对比

---

操作复杂度对比

操作	数组	链表	为什么
查询（按下标）	O(1)	O(n)	数组直接算地址，链表必须遍历
插入（中间）	O(n)	O(1)	数组要移位，链表改指针即可
删除（中间）	O(n)	O(1)	同上
尾部追加	O(1)	O(1)	知道末尾地址的话

---

企业场景

• 数组：内存数据库（Redis）、消息队列底层存储、缓冲区（Ring Buffer）
• 链表：文件系统 FAT 表、浏览器前进后退、进程调度队列

---

AI 协作

AI 生成：
  - 实现自定义数组（含扩容机制）-- ~60 行 Python
  - 实现单向/双向链表（增删改查）-- ~80 行 Python
  - LeetCode 206 反转链表、21 合并有序链表

人类决策：
  - 业务需要频繁随机查询 -> 用数组
  - 业务需要频繁插入删除 -> 用链表
  - 内存碎片严重 -> 考虑数组（连续分配更省）