第2章 列表与动态数组理论

本章导读

列表是Python中最核心的数据结构，其底层实现为动态数组。本章从形式化角度深入分析动态数组的理论基础，包括ADT规范、扩容策略的数学证明、均摊复杂度分析，以及跳表等高级数据结构的概率分析。

学习目标

完成本章学习后，读者将能够：

• 掌握动态数组ADT的形式化规范与公理系统
• 理解动态数组扩容策略的数学原理与均摊分析
• 应用势能方法证明操作的均摊复杂度
• 掌握跳表的概率分析与期望复杂度
• 理解稀疏数组的空间-时间权衡理论

---

2.1 动态数组的形式化理论

2.1.1 动态数组ADT规范

定义 2.1（动态数组） 动态数组是一种支持随机访问、动态扩容的线性数据结构，其核心特征是在保证 $O(1)$ 随机访问的同时，支持高效的动态插入。

ADT 2.1（DynamicArray）

ADT DynamicArray[T]
  Types: DynamicArray[T]
  
  Operations:
    empty: → DynamicArray[T]
    size: DynamicArray[T] → ℕ
    capacity: DynamicArray[T] → ℕ
    get: DynamicArray[T] × ℕ → T ∪ {error}
    set: DynamicArray[T] × ℕ × T → DynamicArray[T]
    append: DynamicArray[T] × T → DynamicArray[T]
    insert: DynamicArray[T] × ℕ × T → DynamicArray[T]
    delete: DynamicArray[T] × ℕ → DynamicArray[T] ∪ {error}
  
  Axioms:
    ∀a: DynamicArray[T], ∀i: ℕ, ∀x: T
    (A1) size(empty) = 0
    (A2) capacity(empty) = c₀  (初始容量)
    (A3) size(append(a, x)) = size(a) + 1
    (A4) i < size(a) → get(append(a, x), i) = get(a, i)
    (A5) get(append(a, x), size(a)) = x
    (A6) i < size(a) → get(set(a, i, x), i) = x
    (A7) i ≠ j ∧ i < size(a) ∧ j < size(a) → get(set(a, i, x), j) = get(a, j)
    (A8) i ≤ size(a) → size(insert(a, i, x)) = size(a) + 1
    (A9) i < size(a) → delete(a, i) ≠ error
    (A10) size(a) = 0 → delete(a, 0) = error

定理 2.1（ADT一致性） 动态数组ADT的公理系统是一致的。

证明：构造具体模型。设底层存储为数组 $A[0..c-1]$，其中 $c$ 为容量，$n$ 为元素数。定义：

• $empty = (A = [], n = 0, c = c_0)$
• $get(a, i) = A[i]$ 当 $i < n$
• $set(a, i, x)$ 将 $A[i]$ 置为 $x$
• $append(a, x)$ 将 $x$ 存入 $A[n]$，$n \leftarrow n + 1$

可直接验证所有公理在该模型下成立。由模型存在性知公理系统一致。∎

2.1.2 动态数组的数学模型

定义 2.2（动态数组状态） 动态数组的状态可表示为三元组 $(A, n, c)$，其中：

• $A[0..c-1]$ 是底层存储数组
• $n \in \mathbb{N}$ 是当前元素数量，满足 $n \leq c$
• $c \in \mathbb{N}$ 是当前容量

定义 2.3（扩容因子） 扩容因子 $\alpha > 1$ 定义了容量增长比率。当 $n = c$ 时，新容量 $c' = \lfloor \alpha \cdot c \rfloor$。

定理 2.2（空间利用率） 采用扩容因子 $\alpha$ 的动态数组，空间利用率满足：

$$\frac{n}{c} \geq \frac{1}{\alpha}$$

证明：设第 $k$ 次扩容后容量为 $c_k$，元素数为 $n_k$。扩容条件为 $n_k = c_k$，扩容后 $c_{k+1} = \alpha \cdot c_k$，$n_{k+1} = n_k + 1$。

下一次扩容前，$n$ 从 $n_k$ 增长到 $c_{k+1} = \alpha \cdot c_k$。因此最小利用率出现在刚扩容后：

$$\frac{n_{k+1}}{c_{k+1}} = \frac{n_k + 1}{\alpha \cdot c_k} \approx \frac{1}{\alpha}$$

（当 $n_k$ 足够大时）∎

---

2.2 扩容策略的数学分析

2.2.1 扩容代价的形式化分析

定义 2.4（扩容代价） 第 $k$ 次扩容的代价为 $C_k = c_k$（需要复制 $c_k$ 个元素）。

定理 2.3（总扩容代价） 设初始容量为 $c_0$，扩容因子为 $\alpha$，执行 $n$ 次 append 操作后的总扩容代价为：

$$T_{total}(n) = \sum_{k=0}^{\lfloor \log_\alpha(n/c_0) \rfloor} c_0 \cdot \alpha^k = c_0 \cdot \frac{\alpha^{m+1} - 1}{\alpha - 1}$$

其中 $m = \lfloor \log_\alpha(n/c_0) \rfloor$。

证明：扩容发生在 $n = c_0, c_0\alpha, c_0\alpha^2, \ldots$ 时。设共发生 $m$ 次扩容，则：

$$c_0\alpha^m \leq n < c_0\alpha^{m+1}$$

因此 $m = \lfloor \log_\alpha(n/c_0) \rfloor$。

总代价为等比级数求和：

$$T_{total}(n) = c_0 + c_0\alpha + c_0\alpha^2 + \cdots + c_0\alpha^m = c_0 \cdot \frac{\alpha^{m+1} - 1}{\alpha - 1}$$

由于 $\alpha^{m+1} \leq \alpha \cdot n/c_0$，故 $T_{total}(n) = O(n)$。∎

推论 2.1（均摊代价） 每次 append 操作的均摊代价为 $O(1)$。

证明：由定理 2.3，$n$ 次操作总代价 $T_{total}(n) = O(n)$，因此均摊代价：

$$\hat{c} = \frac{T_{total}(n)}{n} = O(1)$$

∎

2.2.2 CPython扩容策略分析

CPython采用非标准扩容策略：

$$new_allocated = (newsize + (newsize \gg 3) + 6) \land \sim 3$$

定理 2.4（CPython扩容因子） CPython的扩容因子约为 $1.125$（即 $9/8$）。

证明：分析公式：

$$new_allocated \approx newsize + \frac{newsize}{8} + 6 = \frac{9}{8}newsize + 6$$

当 $newsize$ 足够大时，扩容因子趋近于 $9/8 = 1.125$。∎

定理 2.5（CPython策略的内存效率） 相比于 $\alpha = 2$ 的策略，CPython策略的内存浪费上限更低。

证明：设 $\alpha = 2$，空间利用率下界为 $1/2 = 50%$。

设 $\alpha = 1.125$，空间利用率下界为 $1/1.125 \approx 88.9%$。

CPython策略以略高的扩容频率换取更高的内存效率。∎

2.2.3 势能方法证明

定理 2.6（势能分析） 定义势能函数 $\Phi(D) = 2n - c$，其中 $n$ 为元素数，$c$ 为容量。则 append 操作的均摊代价为 $O(1)$。

证明：设初始状态 $\Phi(D_0) = 0$（$n = 0, c = c_0$）。

情况1：无需扩容

实际代价 $c_i = 1$（直接插入）。势能变化：

$$\Delta\Phi = \Phi(D_i) - \Phi(D_{i-1}) = 2(n+1) - c - (2n - c) = 2$$

均摊代价：

$$\hat{c}_i = c_i + \Delta\Phi = 1 + 2 = 3$$

情况2：需要扩容

设扩容前 $n = c$，扩容后 $c' = 2c$。实际代价 $c_i = n + 1$（复制 $n$ 个元素 + 插入）。

扩容前势能：$\Phi(D_{i-1}) = 2n - n = n$

扩容后势能：$\Phi(D_i) = 2(n+1) - 2n = 2$

势能变化：$\Delta\Phi = 2 - n$

均摊代价：

$$\hat{c}_i = c_i + \Delta\Phi = (n + 1) + (2 - n) = 3$$

综上，无论是否扩容，均摊代价均为常数 $3$。∎

---

2.3 时间复杂度的形式化分析

2.3.1 操作复杂度定理

定理 2.7（随机访问复杂度） 动态数组的随机访问操作 $get(a, i)$ 的时间复杂度为 $\Theta(1)$。

证明：设数组起始地址为 $base$，元素大小为 $w$。访问第 $i$ 个元素的地址计算为：

$$addr = base + i \cdot w$$

地址计算涉及一次乘法和一次加法，均为常数时间。内存访问也是常数时间。因此总时间为 $\Theta(1)$。∎

定理 2.8（插入复杂度） 在位置 $i$ 插入元素的时间复杂度为 $\Theta(n - i)$。

证明：插入操作需要将位置 $i$ 到 $n-1$ 的所有元素后移一位，共移动 $n - i$ 个元素。每个元素的移动时间为常数，因此总时间为 $\Theta(n - i)$。

特别地：

• 尾部插入（$i = n$）：$\Theta(1)$
• 头部插入（$i = 0$）：$\Theta(n)$

∎

定理 2.9（查找下界） 在无序动态数组中查找特定元素，任何确定性算法的最坏情况时间复杂度为 $\Omega(n)$。

证明：采用对抗性论证。设算法在访问少于 $n$ 个元素后声称结果。对抗者可以构造输入，使得未被访问的元素恰好是目标元素（若存在）或使得算法给出错误答案。因此算法必须访问所有 $n$ 个元素才能保证正确性。∎

2.3.2 复杂度汇总

操作	最坏情况	均摊情况	空间	说明
get(i) / set(i, x)	$\Theta(1)$	$\Theta(1)$	$O(1)$	随机访问
append(x)	$\Theta(n)$	$\Theta(1)$	$O(1)$	均摊分析
insert(i, x)	$\Theta(n)$	$\Theta(n)$	$O(1)$	需移动元素
delete(i)	$\Theta(n)$	$\Theta(n)$	$O(1)$	需移动元素
search(x)	$\Theta(n)$	$\Theta(n)$	$O(1)$	无序查找
sort()	$\Theta(n \log n)$	$\Theta(n \log n)$	$O(n)$	Timsort

---

2.4 Python列表的CPython实现

2.4.1 内存布局

CPython PyListObject 结构
┌─────────────────────────────────────────────────────────────┐
│  PyObject_VAR_HEAD                                          │
│  ├─ ob_refcnt: Py_ssize_t     │ 引用计数                    │
│  └─ ob_type: PyTypeObject*    │ 类型指针 → &PyList_Type     │
├─────────────────────────────────────────────────────────────┤
│  ob_size: Py_ssize_t          │ 当前元素数量 (len())        │
│  ob_item: PyObject**          │ 元素指针数组                │
│  allocated: Py_ssize_t        │ 已分配容量 (≥ ob_size)      │
└─────────────────────────────────────────────────────────────┘
                    │
                    ▼
         ┌───────────────────────────────────────┐
         │  ob_item[0]  [1]  [2]  ...  [n-1]     │
         │     │        │    │          │        │
         │     ▼        ▼    ▼          ▼        │
         │   PyObject  PyObject  ...  PyObject   │
         └───────────────────────────────────────┘

2.4.2 扩容策略源码分析

// CPython Objects/listobject.c (简化版)
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    Py_ssize_t new_allocated;
    size_t num_allocated_bytes;
    
    // 计算新容量
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    
    // 对齐到8字节边界
    new_allocated = (new_allocated + 3) & ~(size_t)3;
    
    // 重新分配内存
    if (new_allocated > self->allocated) {
        num_allocated_bytes = new_allocated * sizeof(PyObject*);
        self->ob_item = PyMem_Realloc(self->ob_item, num_allocated_bytes);
        self->allocated = new_allocated;
    }
    
    self->ob_size = newsize;
    return 0;
}

2.4.3 性能基准测试

import sys
import timeit
from typing import List, Callable

def analyze_capacity_growth(n: int = 100) -> List[tuple]:
    """分析列表容量增长策略"""
    result = []
    lst = []
    prev_capacity = 0
    
    for i in range(n):
        lst.append(i)
        capacity = sys.getsizeof(lst) - sys.getsizeof([])
        if capacity != prev_capacity:
            growth_rate = capacity / prev_capacity if prev_capacity > 0 else float('inf')
            result.append((len(lst), capacity, growth_rate))
            prev_capacity = capacity
    
    return result

def benchmark_operations(n: int = 100_000) -> dict:
    """操作性能基准测试"""
    results = {}
    
    results['append'] = timeit.timeit(
        'lst.append(1)',
        setup='lst = []',
        number=n
    )
    
    results['insert_head'] = timeit.timeit(
        'lst.insert(0, 1)',
        setup='lst = []',
        number=n
    )
    
    results['insert_mid'] = timeit.timeit(
        'lst.insert(len(lst)//2, 1)',
        setup=f'lst = list(range({n}))',
        number=1000
    )
    
    results['pop_tail'] = timeit.timeit(
        'lst.pop()',
        setup=f'lst = list(range({n}))',
        number=n
    )
    
    results['pop_head'] = timeit.timeit(
        'lst.pop(0)',
        setup=f'lst = list(range({n}))',
        number=n // 10
    )
    
    results['search'] = timeit.timeit(
        'n-1 in lst',
        setup=f'lst = list(range({n})); n = {n}',
        number=100
    )
    
    return results

if __name__ == '__main__':
    print("=== 容量增长分析 ===")
    for length, capacity, rate in analyze_capacity_growth(50):
        print(f"长度={length:3d}, 容量={capacity:5d}, 增长率={rate:.3f}")
    
    print("\n=== 性能基准测试 ===")
    results = benchmark_operations()
    for op, time in results.items():
        print(f"{op:15s}: {time:.6f}s")

---

2.5 列表推导式的语义与优化

2.5.1 语义形式化

定义 2.5（列表推导式） 列表推导式 $[e \mid x \leftarrow xs, p(x)]$ 的语义定义为：

$$[e \mid x \leftarrow xs, p(x)] = [e[x := v] \mid v \in xs \land p(v)]$$

其中 $e[x := v]$ 表示将表达式 $e$ 中的自由变量 $x$ 替换为 $v$。

定理 2.10（推导式等价性） 列表推导式 $[f(x) \mid x \leftarrow xs]$ 等价于以下循环：

result = []
for x in xs:
    result.append(f(x))

证明：通过语义等价性证明。设 $xs = [x_1, x_2, \ldots, x_n]$。

推导式语义：$[f(x_1), f(x_2), \ldots, f(x_n)]$

循环语义：依次执行 append(f(x_i))，结果相同。∎

2.5.2 性能优化原理

定理 2.11（推导式性能优势） 列表推导式比等效循环快约 $10%$-$30%$。

证明：列表推导式在CPython层面直接调用 LIST_APPEND 字节码，避免了：

1. 循环控制开销（FOR_ITER, STORE_FAST 等）
2. 方法查找开销（LOAD_ATTR for append）
3. 函数调用开销（CALL_FUNCTION）

字节码对比：

# 循环版本
LOAD_CONST       0 ([])
STORE_FAST       0 (result)
LOAD_GLOBAL      0 (range)
...
CALL_FUNCTION    1
GET_ITER
FOR_ITER         13 (to 24)
STORE_FAST       1 (x)
LOAD_FAST        0 (result)
LOAD_ATTR        1 (append)    # 方法查找
LOAD_FAST        1 (x)
CALL_FUNCTION    1             # 方法调用
POP_TOP
JUMP_ABSOLUTE    11

# 推导式版本
BUILD_LIST       0
LOAD_GLOBAL      0 (range)
...
CALL_FUNCTION    1
GET_ITER
FOR_ITER         8 (to 18)
STORE_FAST       0 (x)
LOAD_FAST        0 (x)
LIST_APPEND      1             # 直接追加
JUMP_ABSOLUTE    10

推导式版本减少了约 $40%$ 的字节码指令。∎

---

2.6 跳表：概率数据结构

2.6.1 跳表的形式化定义

定义 2.6（跳表） 跳表是一种随机化的数据结构，由多层链表组成。第 $0$ 层包含所有元素，第 $i$ 层包含第 $i-1$ 层元素的随机子集。

定义 2.7（节点层级） 节点 $v$ 的层级 $L(v)$ 服从几何分布：

$$P(L(v) = k) = p^k(1-p), \quad k = 0, 1, 2, \ldots$$

其中 $p$ 为晋升概率（通常取 $p = 1/2$）。

定理 2.12（期望层级） 节点的期望层级为：

$$E[L(v)] = \sum_{k=0}^{\infty} k \cdot p^k(1-p) = \frac{p}{1-p}$$

当 $p = 1/2$ 时，$E[L(v)] = 1$。

证明：几何分布的期望公式。设 $X \sim Geo(p)$，则 $E[X] = \frac{1-p}{p}$。但这里定义的是从 $0$ 开始，故 $E[L] = \frac{p}{1-p}$。∎

2.6.2 复杂度分析

定理 2.13（查找复杂度） 跳表的查找操作期望时间复杂度为 $O(\log n)$。

证明：采用逆向分析。从目标节点出发，向左上方回溯到头节点。

设 $T(k)$ 为从第 $k$ 层某节点回溯到头节点的期望步数。每步有概率 $p$ 上升到更高层，概率 $1-p$ 在当前层左移。

$$T(k) = 1 + p \cdot T(k+1) + (1-p) \cdot T(k)$$

解得 $T(k) = \frac{1}{1-p} + \frac{p}{1-p}T(k+1)$。

设最大层数为 $O(\log n)$，则总期望步数为 $O(\log n)$。∎

定理 2.14（空间复杂度） 跳表的期望空间复杂度为 $O(n)$。

证明：每个节点的期望指针数为 $E[L(v)] + 1 = \frac{1}{1-p}$。

当 $p = 1/2$ 时，期望指针数为 $2$。因此总空间为 $O(2n) = O(n)$。∎

2.6.3 跳表实现

import random
from typing import TypeVar, Generic, Optional, List, Iterator

T = TypeVar('T')

class SkipNode(Generic[T]):
    """跳表节点"""
    __slots__ = ['value', 'forward']
    
    def __init__(self, value: Optional[T], level: int):
        self.value = value
        self.forward: List[Optional['SkipNode[T]']] = [None] * (level + 1)

class SkipList(Generic[T]):
    """
    跳表实现
    
    期望时间复杂度：
    - search: O(log n)
    - insert: O(log n)
    - delete: O(log n)
    
    空间复杂度：O(n)
    """
    
    MAX_LEVEL = 16
    P = 0.5
    
    def __init__(self):
        self.header = SkipNode[T](None, self.MAX_LEVEL)
        self.level = 0
        self._size = 0
    
    def _random_level(self) -> int:
        """生成随机层级，服从几何分布"""
        level = 0
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level
    
    def search(self, value: T) -> bool:
        """
        查找元素
        时间复杂度：O(log n) 期望
        """
        current = self.header
        
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
        
        current = current.forward[0]
        return current is not None and current.value == value
    
    def insert(self, value: T) -> None:
        """
        插入元素
        时间复杂度：O(log n) 期望
        """
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header
        
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        if current is None or current.value != value:
            new_level = self._random_level()
            
            if new_level > self.level:
                for i in range(self.level + 1, new_level + 1):
                    update[i] = self.header
                self.level = new_level
            
            new_node = SkipNode[T](value, new_level)
            
            for i in range(new_level + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node
            
            self._size += 1
    
    def delete(self, value: T) -> bool:
        """
        删除元素
        时间复杂度：O(log n) 期望
        """
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header
        
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        if current and current.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]
            
            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1
            
            self._size -= 1
            return True
        
        return False
    
    def __len__(self) -> int:
        return self._size
    
    def __iter__(self) -> Iterator[T]:
        current = self.header.forward[0]
        while current:
            yield current.value
            current = current.forward[0]
    
    def __repr__(self) -> str:
        return f"SkipList({list(self)})"
    
    def visualize(self) -> str:
        """可视化跳表结构"""
        lines = []
        
        for level in range(self.level, -1, -1):
            values = []
            current = self.header.forward[level]
            while current:
                values.append(str(current.value))
                current = current.forward[level]
            lines.append(f"L{level}: " + " → ".join(values) if values else f"L{level}: empty")
        
        return "\n".join(lines)


def test_skiplist():
    """跳表测试"""
    sl = SkipList[int]()
    
    data = [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]
    for x in data:
        sl.insert(x)
    
    print(f"跳表内容: {sl}")
    print(f"元素数量: {len(sl)}")
    print(f"\n跳表结构:\n{sl.visualize()}")
    
    print(f"\n查找测试:")
    print(f"  search(19): {sl.search(19)}")
    print(f"  search(100): {sl.search(100)}")
    
    sl.delete(19)
    print(f"\n删除19后: {sl}")
    print(f"  search(19): {sl.search(19)}")


if __name__ == '__main__':
    test_skiplist()

---

2.7 稀疏数组：空间-时间权衡

2.7.1 稀疏性定义

定义 2.8（稀疏度） 设数组 $A$ 有 $n$ 个元素，其中 $k$ 个为非零元素。稀疏度定义为：

$$\rho(A) = \frac{k}{n}$$

当 $\rho(A) \ll 1$ 时，称数组为稀疏数组。

定理 2.15（空间效率） 稀疏数组的空间复杂度为 $O(k)$，相比密集数组的 $O(n)$，当 $k \ll n$ 时显著节省空间。

2.7.2 实现

from typing import Dict, List, Optional, Iterator, Tuple

class SparseArray:
    """
    稀疏数组实现
    
    空间复杂度：O(k)，k为非零元素数
    时间复杂度：
    - get: O(1)
    - set: O(1)
    - 迭代: O(k)
    """
    
    def __init__(self, size: int):
        if size <= 0:
            raise ValueError("Size must be positive")
        self._size = size
        self._data: Dict[int, int] = {}
    
    def __len__(self) -> int:
        return self._size
    
    def __getitem__(self, index: int) -> int:
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size})")
        return self._data.get(index, 0)
    
    def __setitem__(self, index: int, value: int) -> None:
        if not 0 <= index < self._size:
            raise IndexError(f"Index {index} out of range [0, {self._size})")
        if value != 0:
            self._data[index] = value
        elif index in self._data:
            del self._data[index]
    
    def non_zero_count(self) -> int:
        """非零元素数量"""
        return len(self._data)
    
    def sparsity(self) -> float:
        """稀疏度"""
        return 1 - self.non_zero_count() / self._size
    
    def non_zero_items(self) -> Iterator[Tuple[int, int]]:
        """迭代非零元素"""
        for index in sorted(self._data.keys()):
            yield index, self._data[index]
    
    def to_dense(self) -> List[int]:
        """转换为密集数组"""
        return [self[i] for i in range(self._size)]
    
    @classmethod
    def from_dense(cls, arr: List[int]) -> 'SparseArray':
        """从密集数组创建"""
        sparse = cls(len(arr))
        for i, val in enumerate(arr):
            if val != 0:
                sparse[i] = val
        return sparse
    
    def __repr__(self) -> str:
        items = list(self.non_zero_items())
        return f"SparseArray(size={self._size}, non_zero={items})"


class CompressedSparseRow:
    """
    压缩稀疏行（CSR）格式
    用于稀疏矩阵存储
    
    空间复杂度：O(nnz + n + 1)，nnz为非零元素数
    """
    
    def __init__(self, rows: int, cols: int):
        self.rows = rows
        self.cols = cols
        self.values: List[int] = []
        self.col_indices: List[int] = []
        self.row_ptr: List[int] = [0]
    
    def add_row(self, row_data: List[Tuple[int, int]]) -> None:
        """添加一行数据 (col, value)"""
        for col, val in sorted(row_data):
            self.values.append(val)
            self.col_indices.append(col)
        self.row_ptr.append(len(self.values))
    
    def get(self, row: int, col: int) -> int:
        """获取元素"""
        if not (0 <= row < self.rows and 0 <= col < self.cols):
            raise IndexError("Index out of range")
        
        start = self.row_ptr[row]
        end = self.row_ptr[row + 1]
        
        for i in range(start, end):
            if self.col_indices[i] == col:
                return self.values[i]
        
        return 0
    
    def nnz(self) -> int:
        """非零元素数"""
        return len(self.values)

---

2.8 高级应用

2.8.1 自定义动态数组

import ctypes
from typing import TypeVar, Generic, Optional, Iterator, List

T = TypeVar('T')

class DynamicArray(Generic[T]):
    """
    自定义动态数组实现
    
    特性：
    - O(1) 随机访问
    - O(1) 均摊尾部插入
    - O(n) 中间插入/删除
    - 自动扩容/缩容
    """
    
    def __init__(self, initial_capacity: int = 1):
        self._n = 0
        self._capacity = max(1, initial_capacity)
        self._array = self._make_array(self._capacity)
    
    def _make_array(self, capacity: int) -> ctypes.Array:
        return (capacity * ctypes.py_object)()
    
    def __len__(self) -> int:
        return self._n
    
    def capacity(self) -> int:
        return self._capacity
    
    def __getitem__(self, index: int) -> T:
        if not 0 <= index < self._n:
            raise IndexError(f"Index {index} out of range [0, {self._n})")
        return self._array[index]
    
    def __setitem__(self, index: int, value: T) -> None:
        if not 0 <= index < self._n:
            raise IndexError(f"Index {index} out of range [0, {self._n})")
        self._array[index] = value
    
    def append(self, value: T) -> None:
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        self._array[self._n] = value
        self._n += 1
    
    def insert(self, index: int, value: T) -> None:
        if index < 0:
            index = max(0, self._n + index)
        if index > self._n:
            index = self._n
        
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        
        for i in range(self._n, index, -1):
            self._array[i] = self._array[i - 1]
        
        self._array[index] = value
        self._n += 1
    
    def pop(self, index: int = -1) -> T:
        if self._n == 0:
            raise IndexError("pop from empty array")
        
        if index < 0:
            index = self._n + index
        
        if not 0 <= index < self._n:
            raise IndexError(f"Index {index} out of range")
        
        value = self._array[index]
        
        for i in range(index, self._n - 1):
            self._array[i] = self._array[i + 1]
        
        self._n -= 1
        self._array[self._n] = None
        
        if self._n < self._capacity // 4:
            self._resize(max(1, self._capacity // 2))
        
        return value
    
    def _resize(self, capacity: int) -> None:
        new_array = self._make_array(capacity)
        for i in range(self._n):
            new_array[i] = self._array[i]
        self._array = new_array
        self._capacity = capacity
    
    def __iter__(self) -> Iterator[T]:
        for i in range(self._n):
            yield self._array[i]
    
    def __repr__(self) -> str:
        return f"DynamicArray({list(self)}, capacity={self._capacity})"
    
    def __str__(self) -> str:
        return str(list(self))

2.8.2 环形缓冲区

from typing import TypeVar, Generic, Iterator, Optional

T = TypeVar('T')

class CircularBuffer(Generic[T]):
    """
    环形缓冲区（循环队列）
    
    特性：
    - O(1) 入队/出队
    - 固定容量
    - 内存高效
    """
    
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._buffer: List[Optional[T]] = [None] * capacity
        self._head = 0
        self._tail = 0
        self._size = 0
    
    def enqueue(self, value: T) -> bool:
        """入队，满时返回False"""
        if self.is_full():
            return False
        self._buffer[self._tail] = value
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1
        return True
    
    def dequeue(self) -> Optional[T]:
        """出队，空时返回None"""
        if self.is_empty():
            return None
        value = self._buffer[self._head]
        self._buffer[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return value
    
    def peek(self) -> Optional[T]:
        """查看队首元素"""
        if self.is_empty():
            return None
        return self._buffer[self._head]
    
    def is_empty(self) -> bool:
        return self._size == 0
    
    def is_full(self) -> bool:
        return self._size == self._capacity
    
    def __len__(self) -> int:
        return self._size
    
    def __iter__(self) -> Iterator[T]:
        for i in range(self._size):
            yield self._buffer[(self._head + i) % self._capacity]
    
    def __repr__(self) -> str:
        return f"CircularBuffer({list(self)}, capacity={self._capacity})"

---

2.9 本章小结

2.9.1 核心定理总结

定理	内容	应用
定理 2.3	总扩容代价 $O(n)$	均摊分析基础
定理 2.6	势能方法证明均摊 $O(1)$	算法正确性
定理 2.9	查找下界 $\Omega(n)$	复杂度下界
定理 2.13	跳表期望 $O(\log n)$	概率分析

2.9.2 数据结构选择指南

需求	推荐结构	原因
随机访问 + 尾部操作	动态数组	$O(1)$ 访问，均摊 $O(1)$ 追加
双端操作	deque	$O(1)$ 头尾操作
有序 + 快速查找	跳表	$O(\log n)$ 查找/插入/删除
大量零值存储	稀疏数组	$O(k)$ 空间

2.9.3 最佳实践

# 1. 尾部操作优先
lst.append(x)        # O(1) 均摊
lst.insert(0, x)     # O(n) 避免

# 2. 成员检测用集合
if x in set(lst):    # O(1) 平均
    pass

# 3. 推导式简洁高效
[x**2 for x in range(10)]

# 4. 预分配已知大小
lst = [None] * n

# 5. 避免迭代中修改
lst = [x for x in lst if condition]

---

2.10 习题

理论题

1. 证明：采用扩容因子 $\alpha$ 的动态数组，$n$ 次 append 操作的总扩容代价为 $O(n)$。

2. 证明：定义势能函数 $\Phi(D) = 3n - 2c$，证明在 $1.5$ 倍扩容策略下，append 的均摊代价为 $O(1)$。

3. 分析跳表的删除操作期望时间复杂度为 $O(\log n)$。

4. 证明：在 $n$ 个元素的有序数组中，二分查找的最坏情况比较次数为 $\lfloor \log_2 n \rfloor + 1$。

设计题

5. 设计一个支持 $O(1)$ 均摊插入、$O(1)$ 随机访问、$O(n)$ 迭代的数据结构。

6. 实现一个支持范围查询的跳表变体。

实现题

7. 实现一个支持自动缩容的动态数组，分析其均摊复杂度。

8. 实现一个支持并发访问的跳表。

---

2.11 参考文献

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Chapter 17: Amortized Analysis.

2. Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676.

3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 1.3: Bags, Queues, and Stacks.

4. Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2), 306-318.

5. CPython Source Code. (2024). Objects/listobject.c. https://github.com/python/cpython/blob/main/Objects/listobject.c

6. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. Section 2.2: Linear Lists.

---

下一章：第3章 元组与不可变序列