数组与链表

📍 开学排座位——两种不同的占座方式

新学期开学，你们班要安排座位。老师有两种方案：

方案一（数组式）： 教室里有 50 个座位排成一排，每个座位固定编号 1 到 50。你只要说出座位号，就能直接走到那个座位——“第 37 号座位”，走过去坐下。

方案二（链表式）： 老师说：“张三，你坐第一排第一个。李四，你坐在张三后面。王五，你坐在李四后面……”每个人只知道自己后面是谁。你想找第 37 个人——得从第一个人开始，一个一个往后数。

这就是数组和链表最本质的区别：

• 数组（Array） ——连续排列，知道编号就能直接定位
• 链表（Linked List） ——链条串联，要找人必须顺着链走

这两种存储方式是几乎所有数据结构的”乐高积木”——理解了它们，你就理解了后续一切数据结构的基础。

---

🏢 数组——连续内存，随机访问

什么是数组？

数组是 一段连续的内存空间，每个元素大小相同，按顺序排列。

arr = [10, 20, 30, 40, 50]
# 内存中：| 10 | 20 | 30 | 40 | 50 |
# 地址：   100  104  108  112  116  （假设每个 int 占 4 字节）

随机访问——数组的”超能力”

数组最强大的能力是 随机访问（Random Access）：给定下标，直接定位到对应元素。

arr[3]  # 直接取到 40

原理是下面这个公式：

arr[i] 的地址 = 数组起始地址 + i × 每个元素的大小

🧮 计算过程：arr 的起始地址是 100，每个 int 占 4 字节。arr[3] = 100 + 3 × 4 = 112 → 直接从地址 112 读取数据。一次乘法 + 一次加法，就是全部成本。不管数组是一万个元素还是一百万个。

这就是为什么数组访问是 O(1) 的——常数时间，和数组大小无关。

数组的插入和删除——代价高昂

arr = [10, 20, 30, 40, 50]

# 在位置 1 插入 15
# 需要把 20, 30, 40, 50 全部往后移一位
arr.insert(1, 15)
# arr → [10, 15, 20, 30, 40, 50]

插入/删除的”昂贵”在于：为了保持连续性和顺序，后面的元素必须全部移动。

• 在末尾插入/删除：O(1)——不需要移动
• 在开头插入/删除：O(n)——全部要移动
• 平均情况：O(n)

适用场景

✅ 适合	❌ 不适合
频繁按下标访问（arr[i]）	频繁在中间插入/删除
数据大小已知、变化不大	数据规模经常变化
需要缓存友好的场景（连续内存）	需要灵活分配内存

---

🔗 链表——指针串联，灵活插拔

什么是链表？

链表的每个元素是一个 节点（Node） ，每个节点包含数据和指向下一个节点的 指针（Pointer）。

class ListNode:
    def __init__(self, val):
        self.val = val      # 数据
        self.next = None     # 指向下一个节点

# 创建链表：10 → 20 → 30 → 40 → 50
head = ListNode(10)
head.next = ListNode(20)
head.next.next = ListNode(30)
head.next.next.next = ListNode(40)
head.next.next.next.next = ListNode(50)

内存布局（分散的）：
地址 200: [10 | 指向 350]  →  地址 350: [20 | 指向 180]  →  地址 180: [30 | None]

关键区别：数组在内存里是挨着坐的，链表在内存里分散坐，通过指针串联。

链表的插入和删除——“拆链重接”

# 在 20 和 30 之间插入 25
# 1. 创建新节点 25
# 2. 让 25 指向 30
# 3. 让 20 指向 25
new_node = ListNode(25)
new_node.next = node20.next   # 25 → 30
node20.next = new_node        # 20 → 25

插入/删除只需要修改相邻节点的指针——不需要移动任何数据。这就是链表插入/删除 O(1) 的原因。

🧩 类比：寻宝游戏

数组 = 电影院座位——你知道 15 排 7 座在哪，直接走过去。但要插一个新座位？你得把后面所有人的座位往后挪。

链表 = 寻宝游戏——你拿到一张纸条写着”宝藏埋在第三棵大树下”。到了第三棵大树，树下有张纸条写着”往前走 50 步的大石头下”。你要找第 37 个地点——得一张纸条一张纸条地看。

但埋新宝藏时很方便——在任意两个地点之间加一个点，只需要改前后两张纸条上的指引就行。

链表的种类

类型	结构	特点
单向链表	A→B→C→D	只能从头往后走
双向链表	A↔B↔C↔D	可前可后，更灵活
循环链表	A→B→C→A	尾节点指向头，适合环形场景

Python 的 list 是动态数组，而 collections.deque 是双向链表的实现。

链表的访问——慢

要访问链表的第 i 个元素，必须从 head 开始，沿着指针走 i 步：

def get_node(head, index):
    current = head
    for _ in range(index):
        if not current:
            raise IndexError("越界")
        current = current.next
    return current

这就是 O(n)——随着链表变长，访问时间线性增长。

适用场景

✅ 适合	❌ 不适合
频繁在中间插入/删除	频繁按下标访问
不知道数据总量	缓存敏感的场景
实现队列、LRU 缓存等	需要频繁随机读取

---

⚔️ 数组 vs 链表——全面对比

# 数组 vs 链表的代码对比
# 场景：做一个"通讯录"，频繁添加联系人和按序号查找

# 数组方案
contacts_arr = []
contacts_arr.append("张三")  # 末尾添加 O(1)
contacts_arr.insert(0, "李四")  # 开头插入 O(n)
print(contacts_arr[2])  # 按序号查找 O(1)

# 链表方案
# 需要自己实现链表——Python 没有内置的单链表
# 末尾添加 O(n)——除非维护尾指针
# 开头插入 O(1)
# 按序号查找 O(n)

维度	数组	链表
内存	连续，一次性分配	分散，动态分配
随机访问	O(1) ⚡	O(n) 🐢
开头插入/删除	O(n) 🐢	O(1) ⚡
末尾插入/删除	O(1) ⚡	O(1)（有尾指针）
中间插入/删除	O(n) 🐢	O(1) ⚡（找到位置后）
额外内存	几乎没有	每个节点多一个指针（8 字节）
缓存利用	好（连续内存，CPU 缓存预读）	差（分散内存，缓存命中率低）

💡 内存层面的差异：数组的连续内存让 CPU 的缓存（Cache）可以”预读”相邻元素——当你访问 arr[0] 时，CPU 自动把附近的元素也加载到缓存。链表分散存储，每次访问都要从主存加载，慢很多。

这就是为什么算法复杂度相同的情况下，数组实现的算法往往比链表快——Cache Friendly（缓存友好）。

---

🎯 如何选择？

操作模式 → 推荐
──────────────────────
频繁按索引访问      → 数组
大量在中间插入删除  → 链表
实现栈（LIFO）      → 数组（末尾操作）
实现队列（FIFO）    → 链表（两端操作）
数据量小且稳定      → 数组
数据量大且变化多    → 链表

实际经验：在绝大多数情况下，数组（动态数组）是默认选择。现代编程语言的动态数组（Python 的 list、Java 的 ArrayList、C++ 的 vector）在末尾追加时性能非常好，只有在确定需要大量在中间/开头插入时才考虑链表。

---

📝 小结

概念	一句话
数组	连续内存，随机访问 O(1) ——看电影找座位
链表	节点+指针串联，插入删除 O(1) ——寻宝游戏
随机访问	直接通过下标定位到元素
指针	链表中指向下一个节点的引用
时间复杂度	O(1)=常数时间，O(n)=和规模成正比

🎯 小练习：如果你要设计一个”音乐播放器的播放列表”——用户经常添加/删除歌曲，也需要按顺序播放。你会用数组还是链表？如果用户还需要”跳到指定的第 N 首歌”呢？

为什么先学这个？ 数组和链表是所有数据结构的构建基石。理解了它们，下一步看最简单的两种”操作受限”的结构——栈与队列。