数组与链表基础

这是面试中最基础的数据结构题。面试官不只是想看你会不会写代码，而是想理解你为什么这么设计。

面试考察点

面试官通过这道题想考察：
1. 你是否理解计算机内存模型
2. 你是否能说清楚时间复杂度的本质
3. 你是否能根据场景选择合适的数据结构
4. 你是否能回答"为什么"的追问

---

一、数组

1.1 什么是数组？（入门级解释）

想象一个整齐排列的储物柜，每个柜子大小相同，编号连续。

内存中的数组就像一排编好号的储物柜：

柜子编号:  0    1    2    3    4    5    6    7
存储内容: [100] [200] [300] [400] [500] [600] [700] [800]
          ↑                              ↑
        首地址                        随机访问任意位置

特点：
- 每个柜子（存储单元）大小相同
- 柜子紧紧挨在一起（内存连续）
- 知道编号，就能直接打开柜子（随机访问）

1.2 为什么数组访问是 O(1)？（面试必问）

面试官的追问："为什么数组可以根据下标直接访问任意元素？"

这是考察你是否理解计算机内存模型。

回答要点：

1. 数组在内存中是连续存放的

2. 假设：
   - 数组起始地址是：0x1000（内存地址）
   - 每个 int 占 4 个字节
   - 访问 arr[3]

3. 计算过程：
   第3个元素的地址 = 起始地址 + 3 × 每个元素大小
                 = 0x1000 + 3 × 4
                 = 0x1000 + 12
                 = 0x100C

4. CPU 执行：
   MOV EAX, [0x100C]  // 直接从地址 0x100C 取数据

关键点：CPU 可以通过一个简单的数学计算，直接得到任意元素的地址，不需要从头开始找。这就是 O(1) 的本质。

面试官追问：CPU 怎么知道地址是 0x100C？

回答：因为数组的地址计算是硬件级支持的指令。
      现代 CPU 有专门的 "基址寄存器 + 偏移量" 指令，
      一个时钟周期就能完成计算。

1.3 为什么数组插入/删除是 O(n)？

面试官的追问："数组不是可以随机访问吗？那插入一个元素为什么还要移动？"

插入元素到 index = 2 的位置：

插入前: [A] [B] [C] [D] [E] [F]
                 ↑
               插入 X

步骤：
1. 把 C, D, E, F 都往后移一位     ← 这步是 O(n)
2. 把 X 放到空出来的位置

删除元素同理，需要把后面的元素往前移。

关键理解：数组是"紧密排列"的，中间不能有空隙！

时间复杂度总结：

1.4 什么是 CPU 缓存？为什么数组访问快？（进阶问题）

面试官追问："你说数组访问快，到底快在哪里？"

这是考察你是否了解计算机体系结构。

CPU 执行计算时，需要从内存读取数据。

问题：CPU 和内存速度差距巨大！
      CPU 纳秒级执行    内存微秒级读取
      速度差距：100-1000 倍

解决方案：引入 CPU Cache（缓存）

工作原理：
┌─────────────┐      ┌─────────────┐      ┌─────────┐
│    CPU      │ ←──→ │   L1 Cache  │ ←──→ │  内存   │
│  (寄存器)   │      │   L2 Cache  │      │         │
└─────────────┘      └─────────────┘      └─────────┘

预取（Prefetch）：CPU 发现你在读连续的内存，
                  会"猜"你下一个也要读，
                  提前把数据从内存拉到缓存。

这就是数组的优势：
- 访问 arr[0] 时，CPU 可能已经顺便把 arr[1], arr[2] 拉进缓存了
- 访问 arr[1] 时，可能直接从缓存读，不需要访问内存
- 链表？因为不连续，CPU 无法预取，每次都可能要访问内存

1.5 JavaScript 数组的真相（面试加分项）

面试官追问："JavaScript 的数组也是连续内存吗？"

大多数语言中，数组确实是连续内存。
但 JavaScript 的数组有些特殊：

1. 基本类型数组（如 Int32Array）是真正的连续内存

2. 普通 JS 数组（[]）实际上是哈希表！
   - 这就是为什么 JS 数组可以混合类型
   - 这也是为什么 JS 数组访问理论上不是真正的 O(1)

面试加分回答：
"JavaScript 的 Array 是动态类型语言特性，
 在 V8 引擎中，小数组用连续内存，
 大数组或混合类型会用哈希表实现。"

---

二、链表

2.1 什么是链表？（入门级解释）

想象一个寻宝游戏：

宝物 A → 下一个宝物在 "北京市朝阳区..."
宝物 B → 下一个宝物在 "上海市浦东新区..."
宝物 C → 下一个宝物在 "广州市天河区..."
宝物 D → 找不到下一个了（null）

这就是链表：
- 每个宝物有"内容"（数据）
- 每个宝物有"线索"（指针）
- 知道第一个，就能一个一个找到所有宝物

内存中的链表（不连续）：

链表节点：
┌────────┬────────┐
│  数据   │  下一个 │
│   10   │  addr2 │
└────────┴────────┘

实际内存布局（地址随机）：
addr1: [10 | addr2] ──→ addr5: [30 | addr3] ──→ addr8: [50 | null]
   ↑                         ↑                        ↑
  head                      node2                    node3

对比数组（连续）：
addr1: [10] [20] [30] [40] [50]
        0    1    2    3    4

2.2 为什么链表插入/删除是 O(1)？（面试必问）

面试官的追问："你说链表插入快，到底怎么快的？"

在节点 P 后面插入新节点 Q：

1 → 2 → 3 → 4 → 5
          ↑
        在这里插入 X

步骤：
1. 找到节点 P（假设已经找到了）     ← O(n) 在这里！
2. Q.next = P.next                  ← 一步
3. P.next = Q                        ← 一步

核心原理：不需要移动任何节点，只需要修改几个指针！

关键点：如果你已经知道要插入的位置（指针），插入就是 O(1)。

但是！ 找位置本身是 O(n)。所以：

• 在头部插入/删除：O(1)（直接知道位置）
• 在尾部插入：如果有尾指针 O(1)，没有就是 O(n)
• 在中间插入：需要先遍历找到位置 O(n)

2.3 面试官真正想问的：你知道数组和链表的本质区别吗？

问题：如果数组插入是 O(n)，那我每次插入都重建一个数组不行吗？

回答：不行！原因：

1. 频繁分配内存代价高
   - 每次重建都要向操作系统申请内存
   - 操作系统要在浩瀚的内存中找到连续空间
   - 小内存还好，大数组可能找不到连续空间

2. 扩容成本
   - 数组满了怎么办？再建一个更大的！
   - 每次扩容通常翻倍（1 → 2 → 4 → 8...）
   - 这是典型的 "空间换时间"

3. 链表的优势是"不连续"
   - 每个节点独立，插入时单独分配
   - 可以利用零散内存
   - 插入删除不需要移动其他节点

4. 数组的优势是"连续"
   - CPU 缓存友好（预取）
   - 随机访问快
   - 内存紧凑，不浪费

2.4 链表的各种变体（考察你对数据结构的理解）

单向链表：
head → [A] → [B] → [C] → null

双向链表：
null ← [A] ←→ [B] ←→ [C] → null
      ↑
    head

循环链表（单向）：
head → [A] → [B] → [C] ─┐
    ↑                       │
    └───────────────────────┘

循环链表（双向）：
[A] ←→ [B] ←→ [C]
 ↑                 ↑
 └─────────────────┘

面试问题：你会在什么时候用双向链表？

回答：
1. 需要频繁在链表中间插入/删除
   （双向指针可以 O(1) 找到前驱）
2. 需要从尾部和头部同时遍历
3. LRU Cache 就是双向链表 + 哈希表
4. JavaScript 的 DOM 节点就是双向链表

---

三、面试真题讲解

题目1：如何检测链表中的环？

考察点：快慢指针的数学原理

这个问题经典解法是 Floyd 算法（快慢指针），
但面试官会追问："为什么慢指针走一步、快指针走两步就能相遇？"

数学证明（面试必须能推导）：

假设：
- 环的长度是 r
- 从链表头到环入口的距离是 a
- 环入口到相遇点的距离是 x

那么：
- slow 走过的距离 = a + x
- fast 走过的距离 = a + x + n*r（n >= 1，fast 可能绕了 n 圈）

因为 fast 速度是 slow 的 2 倍：
2(a + x) = a + x + n*r
a + x = n*r
a = n*r - x

关键结论：a = n*r - x

这意味着：
从链表头走到环入口的距离 a，
等于从相遇点继续走到环入口的距离（n-1圈 + 剩下的x）

所以：
1. 找到相遇点后，让 slow 回到头
2. fast 和 slow 都一次走一步
3. 再次相遇的点就是环入口

代码（简洁版）：

python复制
# 关键不是代码，而是理解原理
def detectCycle(head):
    # 1. 找到相遇点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break

    # 2. 找环入口：slow 回退到头，然后一起走
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow

题目2：反转链表

考察点：指针操作和边界条件

面试官会问：
1. 你能不用额外空间吗？
2. 你能画出反转过程吗？
3. 如果链表有环会怎样？

核心原理：

原链表：1 → 2 → 3 → 4 → 5

反转过程：
- 用三个指针：prev, curr, next
- 每一步：curr.next = prev
- 然后三个指针一起前移

动画过程：
Step 1: null ← 1    2 → 3 → 4 → 5
              ↑
            prev=curr

Step 2: null ← 1 ← 2    3 → 4 → 5
                  ↑
                prev=curr

...以此类推...

题目3：合并两个有序链表

考察点：归并排序的思想

这不是一道关于链表的题，
而是一道关于"归并排序"的题。

归并排序的核心思想：
1. 把两个有序序列合并成一个有序序列
2. 每次选最小的
3. 时间复杂度 O(n+m)

---

四、面试总结

面试官通过这道题想听到什么？

1. 基础层面：
   - 能说清数组和链表的区别
   - 能解释时间复杂度

2. 进阶层面：
   - 能解释 CPU 缓存原理
   - 能说清为什么数组访问快
   - 能解释预取和内存连续性的关系

3. 高级层面：
   - 能从场景出发选择数据结构
   - 能解释 JavaScript 数组的特殊性
   - 能推导快慢指针的数学证明

什么时候用数组？什么时候用链表？

用数组的场景：
- 需要频繁随机访问（查找）
- 数据量固定，不太需要插入删除
- 需要利用 CPU 缓存提升性能
- 示例：查找表、矩阵运算、排序好的数据

用链表的场景：
- 需要频繁插入删除（尤其是头部/中间）
- 数据量不确定，动态变化
- 不需要随机访问，只需要顺序遍历
- 示例：任务队列、历史记录、LRU Cache

一个经验法则：
"查找多、用数组；增删多、用链表"

常见追问汇总

---

相关题目

• LeetCode 206 - 反转链表 - 必刷
• LeetCode 141 - 环形链表 - 快慢指针
• LeetCode 21 - 合并两个有序链表 - 归并思想