数据结构：数组与动态数组

Python 里日常说的「数组」几乎总是 list：它是 动态数组（dynamic array），底层是一排连续的对象指针，不是 C 的 int a[n]。本篇只讲线性家族的「按下标访问」这一支。

版本锚点：CPython 3.11+；扩容公式自 3.4 起未改语义。

段末注释：动态数组 = 逻辑上按下标 (O(1)) 读写，物理上是一块可扩容的连续内存；CPython 的 list 连续存放的是指针，真正的对象散落在堆上。

图 1　list 是一排挂钩：下标命中指针，对象在堆上

1. 一句话定位

维度	内容
抽象数据类型（Abstract Data Type，ADT）	按下标读写、尾部追加、切片
CPython 实现	`PyObject **ob_item` + `ob_size`（长度）+ `allocated`（容量）
该用	扫描、随机访问、栈（只动尾部）
不该用	队头插入删除（(O(n))）；要存大量同质数值时优先看 `array` / NumPy

2. 底层：挂钩连续，箱子不连续

list 对象本身很小，真正占一块连续区的是指针表：

list 对象
  ob_size    = 逻辑长度 n
  allocated  = 已申请槽位数 ≥ n
  ob_item    → [ptr0, ptr1, …, ptr(n-1), 空槽…]
                    ↓      ↓
                 堆上的对象（各自带对象头）

因此：

a[i] 仍是 (O(1))：一次指针算术 + 一次解引用。
缓存不友好：扫 list 时指针表连续，对象本身往往不连续。
sys.getsizeof(a) 只量容器 + 指针表，不含元素。

同质数值要连续字节，用 array.array 或 NumPy，不要指望 list[int]。

3. 扩容与缩容

追加时若 ob_size == allocated，调用 list_resize。CPython 超额分配：

[
\text{new_allocated} = \text{newsize} + \lfloor \text{newsize}/8 \rfloor +
\begin{cases}
3 & \text{newsize} < 9 \
6 & \text{otherwise}
\end{cases}
]

增长序列（容量）：(0, 4, 8, 16, 25, 35, 46, 58, 72, 88, \ldots)
比「每次 ×2」温和，均摊追加仍是 (O(1))。

缩容：新长度小于容量一半才 realloc，避免尾删立刻还内存、再追加又分配。

import sys

def show_growth(n):
    """观察 list 追加时指针表何时跳变。

    输入：n，追加次数。
    输出：每次容量（按指针宽度估算）变化的 (长度, 字节数) 列表。
    处理：逐次 append，记录 sys.getsizeof 上升点。
    """
    a, last, jumps = [], sys.getsizeof([]), []
    for i in range(n):
        a.append(i)
        cur = sys.getsizeof(a)
        if cur != last:
            jumps.append((len(a), cur))
            last = cur
    return jumps

4. 操作与复杂度

操作	代码	时间	说明
按下标读/写	`a[i]`	(O(1))	负下标先换算
尾部追加	`a.append(x)`	均摊 (O(1))	偶发扩容 (O(n))
尾部弹出	`a.pop()`	均摊 (O(1))
头插 / 头删	`a.insert(0, x)` / `a.pop(0)`	(O(n))	后面指针整体挪
中间插入	`a.insert(i, x)`	(O(n-i))
按值查找	`x in a` / `a.index(x)`	(O(n))	没有索引
切片	`a[i:j]`	(O(j-i))	拷贝新指针表
拼接	`a + b` / `a.extend(b)`	(O(\|b\|))	`+` 出新对象；`extend` 原地
清空	`a.clear()`	(O(n))	逐个减引用

5. 同一家族的其他容器

类型	可变	底层	何时用
`list`	是	指针动态数组	默认选择
`tuple`	否	指针静态数组（创建后容量=长度）	当键、函数返回多值、固定记录
`array.array`	是	连续 C 标量	海量 `int`/`float` 且不引入 NumPy
`bytearray`	是	连续字节	拼缓冲、原地改
`bytes`	否	连续字节	二进制常量
`memoryview`	视导出对象	零拷贝视图	切片大缓冲又不想复制

from array import array

# 输入：可迭代的整数；输出：紧凑的有符号 int 数组（按机器字长）。
xs = array("i", range(1000))

tuple 与 list 的差不只是「能不能改」：tuple 可哈希（元素均可哈希时），能当 dict 的键；list 不能。

6. 代码：只动尾部才像数组

def stack_ops(nums):
    """用 list 当栈：只在尾部进出。

    输入：nums，可迭代。
    输出：逆序后的新 list。
    处理：append 入栈、pop 出栈，均为均摊 O(1)。
    """
    stack = []
    for x in nums:
        stack.append(x)
    out = []
    while stack:
        out.append(stack.pop())
    return out


def bad_queue(nums):
    """反例：用 list 当队列。

    输入 / 输出：同 stack_ops。
    处理：pop(0) 每次搬移剩余指针，总时间 O(n^2)。
    """
    q = list(nums)
    out = []
    while q:
        out.append(q.pop(0))  # 不要这样写
    return out

队列改走 collections.deque，见链表与栈队列专篇。

7. 踩坑

[[0] * n] * m 或 [x] * n（x 可变）：复制的是同一引用。改 a[0][0] 会改每一行。行要独立就写 [[0] * n for _ in range(m)]。
切片是拷贝：b = a[:] 与 a 不再共享指针表；但元素对象仍共享。浅拷贝改可变元素会互相看见。
循环里 s = s + [x]：每次分配新 list，(O(n^2))。用 append / extend。
sort 与 sorted：前者原地、稳定；后者出新 list。比较键用 key=，不要自己写 (O(n^2)) 的装饰。
把 list 当链表用：中间频繁插删在现代 CPU 上几乎总慢于「删了重建」或换 deque。

8. 自检

为什么 list[int] 不是 C 的 int[]？
写出追加扩容的超额分配公式，并说明均摊 (O(1)) 从何而来。
何种操作把 list 从 (O(1)) 打成 (O(n))？
什么时候该换 tuple / array.array / bytearray？

9. 社区口径与风险

实现以 CPython Objects/listobject.c 的 list_resize 为准；PyPy 的 list 策略不同，不要把扩容序列写成跨解释器约定。大规模数值计算的社区方案是 NumPy ndarray（连续、向量化）；风险是依赖重、对象数组（dtype=object）会退回指针表，失去连续数值的好处。