Day 006 — 列表（List）图解

用图理解列表的底层机制和操作原理

1. 列表的内存结构

Python 列表 = 动态数组（不是链表！）
═════════════════════════════════════

列表对象 lst = [10, 20, 30, 40, 50]

┌────────────────────────────────────────┐
│            PyListObject                │
├────────────────────────────────────────┤
│  ob_refcnt: 1                          │
│  ob_type: &PyList_Type                 │
│                                        │
│  ob_size: 5         ← 实际元素个数      │
│  allocated: 8       ← 已分配容量        │
│                                        │
│  ob_item: ──────→ ┌─────┬─────┐       │
│                    │ [0] │  ·──┼──→ int(10) │
│                    ├─────┼─────┤       │
│                    │ [1] │  ·──┼──→ int(20) │
│                    ├─────┼─────┤       │
│                    │ [2] │  ·──┼──→ int(30) │
│                    ├─────┼─────┤       │
│                    │ [3] │  ·──┼──→ int(40) │
│                    ├─────┼─────┤       │
│                    │ [4] │  ·──┼──→ int(50) │
│                    ├─────┼─────┤       │
│                    │ [5] │     │ (未使用)    │
│                    ├─────┼─────┤       │
│                    │ [6] │     │ (未使用)    │
│                    ├─────┼─────┤       │
│                    │ [7] │     │ (未使用)    │
│                    └─────┴─────┘       │
└────────────────────────────────────────┘

关键特点：
1. ob_item 指向一个连续的 PyObject* 指针数组
2. allocated > ob_size  → 预留空间，减少 realloc
3. 每个元素存储的是 "指向实际对象的指针"，而非值本身

2. 索引与寻址原理

随机访问 O(1) 的原理
══════════════════════

列表内存地址 = 连续数组

假设 ob_item 指向的指针数组起始地址为 0x1000
每个指针占 8 字节（64位系统）

元素地址计算公式：
    element_addr = base_addr + index * element_size

访问 lst[3]：
    base_addr = 0x1000
    index = 3
    element_size = 8

    0x1000 + 3 * 8 = 0x1018

    → 直接读取地址 0x1018 处的指针值
    → 得到 int(40) 对象的地址

这就是 O(1) 的原因：
CPU 直接计算地址 → 一次内存读取 → 搞定！
不需要遍历任何东西。

3. Append 扩容流程

flowchart TD
    A[调用 lst.append\(x\)] --> B{容量够吗？<br/>ob_size < allocated?}
    B -->|是| C[在 ob_item[ob_size] 处<br/>存储 x 的指针]
    C --> D[ob_size += 1]
    D --> E[✅ 真正的 O\(1\)]

    B -->|否| F[申请新内存<br/>new_alloc = ob_size * 1.125 + α]
    F --> G[复制旧指针数组<br/>到新内存]
    G --> H[释放旧内存]
    H --> I[更新 ob_item<br/>指向新内存]
    I --> J[更新 allocated]
    J --> C

扩容示例

逐步扩容演示（从空列表开始）
════════════════════════════

初始: ob_size=0, allocated=0

append(1):
  → 扩容到 4 个位置
  → 写入索引 0
  → ob_size=1, allocated=4
  ┌───┬───┬───┬───┐
  │ 1 │   │   │   │
  └───┴───┴───┴───┘

append(2), append(3), append(4):
  → 直接写入，不需要扩容
  → ob_size=4, allocated=4
  ┌───┬───┬───┬───┐
  │ 1 │ 2 │ 3 │ 4 │
  └───┴───┴───┴───┘

append(5):
  → 容量满了，扩容！
  → new_alloc = 4 + (4>>3) + 3 = 8
  → 复制旧数据，写入索引 4
  → ob_size=5, allocated=8
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
  │ 1 │ 2 │ 3 │ 4 │ 5 │   │   │   │
  └───┴───┴───┴───┴───┴───┴───┴───┘

结论：大部分 append 是 O(1)，
只有少数需要扩容时才是 O(n)，
均摊下来 ≈ O(1) 🎉

4. 切片操作的内存视角

lst[2:5] 的内存操作
════════════════════

lst = [10, 20, 30, 40, 50, 60, 70]
索引:   0   1   2   3   4   5   6

切片: lst[2:5]
        ↓   ↓   ↓
       30  40  50

                      原始列表
                 ┌──────────────┐
                 │ 指针数组       │
                 │ [0] → int(10) │
                 │ [1] → int(20) │
    ┌─────────── │ [2] → int(30) │ ←─┐
    │            │ [3] → int(40) │   │
    │            │ [4] → int(50) │ ←─┤
    │  新列表    │ [5] → int(60) │   │
    │ ┌──────┐   │ [6] → int(70) │   │
    │ │ [0] ─┼───┘               │   │
    │ │ [1] ─┼───────────────────┘   │
    │ │ [2] ─┼───────────────────────┘
    │ └──────┘
    └── 新列表的指针数组
        存的是指向同一个 int 对象的指针！
        （浅拷贝：复制指针，不复制对象）

重要：切片创建新列表，但元素指向相同的对象。
如果元素是可变对象（如嵌套列表），修改会影响原列表！

5. 列表推导式执行流程

[x**2 for x in range(5) if x % 2 == 0]
═════════════════════════════════════════

           ┌─────────────────────┐
           │  1. 创建空列表 result │
           └─────────┬───────────┘
                     │
                     ▼
           ┌─────────────────────┐
           │  2. for x in        │ ← 迭代器：0, 1, 2, 3, 4
           │     range(5)        │
           └─────────┬───────────┘
                     │
                     ▼
           ┌─────────────────────┐
           │  3. if x % 2 == 0   │ ← 筛选条件
           └──────┬──────┬──────┘
                  │真    │假
                  ▼     └──→ 回到步骤 2
           ┌─────────────────────┐
           │  4. x**2           │ ← 表达式求值
           └─────────┬───────────┘
                     │
                     ▼
           ┌─────────────────────┐
           │  5. result.append(  │ ← C 层面 append
           │     expression)     │
           └─────────┬───────────┘
                     │
                     ▼
                 回到步骤 2
                     │
                     ▼
           ┌─────────────────────┐
           │  6. 返回 result      │
           └─────────────────────┘

6. 列表 vs 其他数据结构的决策树

flowchart TD
    Q1["你需要什么操作?"]
    
    Q1 -->|"按索引随机访问"| Q2
    Q1 -->|"频繁在开头插入/删除"| Q3
    Q1 -->|"只需要快速入队出队"| Q4
    Q1 -->|"需要去重和集合运算"| SET[使用 set]
    Q1 -->|"键值对映射"| DICT[使用 dict]
    
    Q2 -->|"长度固定"| TUPLE[使用 tuple<br/>更轻量]
    Q2 -->|"长度变化"| LIST[使用 list<br/>动态数组 ✓]
    
    Q3 -->|"偶尔插入"| LIST[list 也还行]
    Q3 -->|"频繁插入"| DEQUE[使用 collections.deque<br/>双向链表 ✓]
    
    Q4 -->|"先进先出"| DEQUE2[使用 collections.deque<br/>queue.Queue]
    Q4 -->|"后进先出"| LIST_STACK[list 就可以<br/>append + pop O(1)]

7. 列表的常见操作复杂度

操作                │ 时间复杂度 │ 说明
───────────────────┼─────────┼──────────────────
lst[i]             │  O(1)   │ 随机访问
lst[i] = x         │  O(1)   │ 赋值（索引必须存在）
lst.append(x)      │  O(1)*  │ *均摊 O(1)，偶尔扩容
lst.pop()          │  O(1)   │ 尾部弹出
lst.pop(i)         │  O(n)   │ 弹出后元素前移
lst.insert(i, x)   │  O(n)   │ 插入后元素后移
lst.remove(x)      │  O(n)   │ 先查找 (O(n)) 再删除 (O(n))
x in lst           │  O(n)   │ 线性搜索
lst[i:j]           │  O(k)   │ k = 切片长度
lst.sort()         │  O(n log n) │ Timsort
len(lst)           │  O(1)   │ 长度缓存为 ob_size
lst.copy()         │  O(n)   │ 复制所有指针

启示：在列表开头操作（insert(0, x)、pop(0)）都是 O(n) 的。如果经常做这种操作，考虑 collections.deque。