Edit: 深入探讨一下 Python `list` 的底层实现

编辑文章

标题 *

URL 别名 *

内容 * (支持 Markdown 格式)

# 深入探讨一下 Python `list` 的底层实现

简而言之，Python 的 `list` 是通过**动态数组（Dynamic Array）** 实现的。更具体地说，在官方的 CPython 解释器中，它是一个**指针数组**，存储着指向列表中各个元素的指针。

下面我们将从核心数据结构、动态扩容机制和操作的时间复杂度这几个关键方面来详细解析。

### 1. 核心数据结构：指针数组

当你创建一个 Python `list` 时，其底层在 C 语言层面是一个结构体（`PyListObject`），这个结构体包含了几个关键信息：

1.  **`ob_item`**: 这是一个指向指针数组的指针 (`PyObject **`)。这个数组才是真正存储数据的地方，但它存的不是元素对象本身，而是指向这些对象的**指针**。
2.  **`ob_size`**: 这是一个整数，表示 `list` 当前包含了多少个元素。也就是我们调用 `len(my_list)` 时得到的值。
3.  **`allocated`**: 这是一个整数，记录了底层为这个指针数组分配了多大的内存空间（即可以容纳多少个指针）。这个值通常会大于或等于 `ob_size`。

**为什么是指针数组？**

*   **支持异构数据类型**：Python 的 `list` 可以包含任意类型的对象（整数、字符串、自定义对象等）。因为数组中存储的只是指向不同对象的指针，而每个 `PyObject` 指针的类型都是相同的，从而轻松实现了在同一个列表中存储不同类型的数据。
*   **内存效率**：如果直接存储对象本身，当对象大小不一时，数组的管理会变得异常复杂且低效。存储统一大小的指针则简单高效得多。

**内存示意图：**

假设我们有这样一个列表：`my_list = [10, "hello", [1, 2]]`

它的底层内存结构大致如下：

### 2. 动态扩容与缩容机制 (Amortized O(1))

动态数组的精髓在于它可以根据需要自动调整大小。

#### **扩容 (Append)**

当你不断向 `list` 中添加元素 (`append`) 时，`ob_size` 会增加。当 `ob_size` 即将超过 `allocated` 时，Python 必须为列表分配更大的存储空间。这个过程大致如下：

1.  **申请新空间**：Python 会申请一块比当前所需更大的新内存空间。这个“更大”不是简单地+1，而是采用一种**超额分配 (over-allocation)** 的策略。
2.  **复制元素**：将旧数组中所有的指针复制到新的内存空间中。
3.  **添加新元素**：在新空间的末尾放入指向新元素的指针。
4.  **释放旧空间**：释放掉旧的、较小的内存空间。

**增长策略：**

为了避免频繁地进行内存分配和复制（这是一个成本很高的操作），Python 的 `list` 扩容策略大致是每次将容量变为原来的 `1.125` 倍左右，并加上一个小的常数。这个增长因子确保了连续 `append` 操作的**摊还时间复杂度 (Amortized Time Complexity)** 为 O(1)。

虽然偶尔一次 `append` 会因为触发扩容而导致 O(n) 的时间成本，但由于扩容后会留出很多空闲空间，接下来多次 `append` 操作都将是 O(1) 的。将高成本操作的耗时分摊到多次低成本操作上，平均下来每次操作的成本接近于一个常数。

#### **缩容 (Pop / Remove)**

当从列表中删除元素时，如果 `allocated` 的空间远大于 `ob_size`，为了节省内存，Python 也会进行缩容。但缩容策略相对保守，通常是当列表中的元素数量少于已分配空间的一半时，才会触发缩容，将数组大小减小。

### 3. 主要操作的时间复杂度

理解了底层实现后，我们就能很自然地推导出 `list` 主要操作的时间复杂度：

| 操作 | 示例 | 平均时间复杂度 | 最坏时间复杂度 | 解释 |
| :--- | :--- | :--- | :--- | :--- |
| **索引访问** | `my_list[i]` | O(1) | O(1) | 数组通过下标直接计算内存地址，所以访问是常数时间。 |
| **末尾添加** | `my_list.append(x)` | O(1) | O(n) | 大部分情况是 O(1)，但如果触发扩容，则需要 O(n) 来复制所有元素。 |
| **末尾弹出** | `my_list.pop()` | O(1) | O(1) | 只需移动 `ob_size` 指针，通常不涉及缩容。 |
| **插入元素** | `my_list.insert(i, x)`| O(n) | O(n) | 需要将被插入位置之后的所有元素的指针向后移动一位。 |
| **删除元素** | `del my_list[i]` | O(n) | O(n) | 需要将被删除位置之后的所有元素的指针向前移动一位。 |
| **迭代** | `for x in my_list:` | O(n) | O(n) | 需要遍历所有元素。 |
| **切片** | `my_list[i:j]` | O(k) | O(k) | 其中 k = j-i。需要创建一个新列表并复制 k 个元素的指针。 |
| **成员检查** | `x in my_list` | O(n) | O(n) | 需要线性扫描列表，逐个比较元素。 |

### 总结

*   **数据结构**：Python `list` 的底层是**动态数组**，在 CPython 中具体实现为**指针数组** (`PyObject **`)。
*   **核心优势**：
    *   通过指针支持**异构数据类型**。
    *   通过索引实现**O(1)**的快速访问。
*   **动态性**：
    *   通过**超额分配**和**动态扩容**机制，实现了摊还 O(1) 的尾部添加效率。
    *   当空间浪费过多时会**自动缩容**。
*   **性能注意点**：在列表的**开头或中间**进行插入和删除操作是低效的（O(n)），因为需要移动大量元素。如果你的应用场景需要频繁地在序列两端进行添加和删除，那么 `collections.deque`（双向队列）会是更好的选择，因为它在两端的操作都是 O(1) 的。

配图 (可多选)

选择新图片文件或拖拽到此处

标签