一、列表的工作原理究竟是什么？
myList = [1, 2, 3, 4]
for i in myList:
print(i)
是不是非常简单直观？所有学过 Python 的人，在学习过程中都或多或少使用过列表。几乎所有教程、视频、训练营和博客都会介绍列表的使用方法，以及列表提供的各种实用方法。但你是否曾经好奇，列表的工作原理究竟是什么？为何它能像变魔术一样自动调整大小，而不像 C 语言中的静态数组那样固定不变？Python 在这背后隐藏了什么？它又是如何实现元素的添加与删除的呢？
这正是本文要探讨的核心问题。我们将通过探究最具权威性的源头 —— 源代码，来解答所有这些疑问。我们的目标是揭开列表的神秘面纱，深入研究支撑 Python 运行的 C 语言代码，从而真正理解列表的本质。这里没有魔法，只有纯粹的逻辑。
那么，我们为什么突然要提及 C 语言呢？当你在终端中输入“python3”时，实际上是在运行一个程序。这个程序是 Python 语言最主流的实现版本，名为 CPython，它几乎完全是用 C 语言编写的。
可以把 CPython 看作是真正运行 Python 脚本的软件。每当你创建一个列表，或者调用 .append() 方法时，实际上是在让 CPython 在后台执行一个特定的 C 语言函数。因此，要想真正理解列表的工作原理，就必须深入研究定义列表的 C 语言代码。
二、Python 是如何实现对象的？
第一个令人惊讶的事实是：Python 作为一门著名的面向对象编程语言，其底层却是基于 C 语言构建的，而 C 语言并不具备我们认知中的类或对象概念。这听起来似乎有些矛盾，究竟是如何实现的呢？
面向对象编程的基本构建模块，本质上就是结构体（用于对数据进行分组）、指针（用于创建引用）、函数指针（用于表示方法）和间接引用（一种在运行时确定执行哪个函数的方式）。
借助这四个构建模块，CPython 得以支持面向对象编程的关键特性：
- 封装性：将数据和方法整合在一起；
- 继承性：允许一个类借鉴另一个类的属性和方法；
- 多态性：使不同类型的对象能够呈现出不同的行为。
接下来，我们就来看看这些对象是如何通过 C 语言实现的！
注：为简化理解，我们会对部分代码进行抽象处理，你仍可通过点击超链接查看完整代码！由于主分支代码会持续更新，本文将以 3.11 版本为准。
2.1 通用对象 ——PyObject
PyObject 是所有 Python 对象的根基。其他所有对象结构体中都包含一个 PyObject，使其成为一切对象的绝对基础。以下是通过结构体和指针定义的 PyObject：
typedef struct _object {
Py_ssize_t ob_refcnt;
PyTypeObject *ob_type;
} PyObject;
属性解析
- ob_refcnt
- 全称：对象引用计数（Object Reference Count）。
- 定义：一个简单的整数计数器。
- 作用：实时记录当前有多少个变量或其他对象在引用该对象。
- 重要性：这是 Python 主要内存管理机制的核心部分。当引用计数降为 0 时，Python 就会判定该对象不再被使用，进而释放其占用的内存。
- ob_type
- 全称：对象类型（Object Type）。
- 定义：一个指向另一个重要结构体 PyTypeObject 的指针。
- 作用：相当于对象的“身份证”，它会告知 CPython：“嘿，我是一个整数”，或者“哟，我是一个列表”。而 PyTypeObject 就如同一个庞大的查找表，存储着该类型对象的所有“方法”。
- 重要性：这是实现多态性的关键所在。当你调用
len(my_list)时，CPython 会通过my_list的ob_type找到用于计算列表长度的正确 C 语言函数。这也使得len()函数不仅能用于列表，还能适用于元组、字典等其他数据类型。
2.2 可变大小基础 ——PyVarObject
有些对象（如数字 7）具有固定的大小，而另一些对象（如列表和字符串）则是能够容纳可变数量元素的容器。PyVarObject 就是所有这些可变大小容器的通用基础。
typedef struct {
PyObject_HEAD
Py_ssize_t ob_size;
} PyVarObject;
其中，PyObject_HEAD是一个宏，在 C 语言中，它的作用相当于将 PyObject 的两个字段直接“复制粘贴”到当前结构体的顶部。这本质上就是继承的实现方式！PyVarObject“继承”了 ob_refcnt 和ob_type，并且新增了一个字段ob_size。
属性解析
ob_size
- 全称：对象大小（Object Size）。
- 定义：另一个整数计数器。
- 作用：存储容器当前容纳的元素数量。
- 重要性：
len()函数返回的值正是ob_size。它是一个预先计算好的值，这也是为什么无论列表或元组的规模多大，调用len()函数都能瞬间完成（时间复杂度为 O (1)），无需额外进行计数操作！
2.3 列表对象 ——PyListObject
好了，准备好揭晓最大的秘密了吗？这个秘密也正是我深入研究列表的契机。在 Python 内部，一个动态、灵活的列表，本质上竟然只是一个静态的 C 语言数组💀！想必你此刻的表情，和我当初得知这个真相时一样惊讶。
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
PyObject_VAR_HEAD宏会将 PyVarObject 的字段（ob_refcnt、ob_type和ob_size）“复制粘贴”过来。在此基础上，PyListObject 又新增了两个列表特有的字段。
属性解析
- ob_item
- 全称：对象元素（Object Items）。
- 定义：这是核心字段，其类型为
PyObject **，意味着它是一个指向 Python 对象指针的指针。你可以将其理解为一个“指针数组”。由于这些指针的类型是 PyObject，因此它们可以指向任何一种 Python 对象。 - 作用：存储一个独立的、连续的 C 语言数组的内存地址。而这个 C 语言数组，又依次存储着列表中所有实际 Python 对象的内存地址。它并非直接存储整数、字符串等数据，而是存储这些数据的地址。
- 重要性：这就是我们所说的“静态 C 语言数组”。由于它是一块连续的内存区域，获取
my_list[500]这样的元素时，只需进行简单的计算就能定位到目标元素，这也是列表元素访问操作速度极快（时间复杂度为 O (1)）的原因。
- allocated
- 全称：已分配槽位（Allocated Slots）。
- 定义：一个整数计数器，是
ob_size的“得力助手”。 - 作用：记录
ob_item这个 C 语言数组在内存中已预留的槽位总数。 - 重要性：这是列表能够实现“动态”特性的关键。Python 通常会分配比当前实际需求更多的内存空间，这就使得
allocated的值可能大于ob_size。那些额外的、未使用的槽位会随时等待你调用.append()方法添加元素，从而在大多数情况下保证了添加操作的高速执行。
三、列表的实际运作 —— 方法背后的 C 语言函数
好了，基础概念介绍完毕，现在我们终于可以深入探讨支撑列表各种常用方法的核心函数了！不过，先为你自己坚持学到这里点个赞，你已经掌握了不少新知识啦 :D
在本节中，我们将把日常使用的 Python 列表方法，与背后真正承担“重活累活”的 C 语言函数关联起来。我们会看到 ob_size 和allocated的值如何变化，还能见证我们熟知的 C 语言数组（ob_item）是如何被直接操作的。首先，我们从列表的创建开始，这是列表“生命”的起点。
3.1 列表的创建 ——PyList_New () 或 list ()
每个列表都有其“诞生”的时刻。当你输入 my_list = [] 时，列表的“生命”就开始了。这个简单的命令会触发对 C 语言函数 PyList_New 的调用，该函数相当于所有新列表对象的“创建者”。
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
// 快速安全性检查，因为一个包含 - 5 个元素的列表显然是不合理的。if (size < 0) {// ... 内部错误处理代码 ...}
// 仅当启用了空闲列表优化时，才会编译以下代码块。#if PyList_MAXFREELIST > 0
// 检查是否有可复用的列表对象。if (get_list_state()->numfree > 0) {// ... 从空闲列表“回收站”中获取对象的 C 语言代码 ...}
else //“回收站”为空时执行以下代码
#endif
{
// 从头开始创建一个全新的列表对象。op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL) {return NULL; // 创建失败}
}
// 如果列表为空，则完全不分配数组内存！if (size <= 0) {op->ob_item = NULL;}
else {
// 如果指定了列表大小，则分配 C 语言数组并将其初始化为零。op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
if (op->ob_item == NULL) {// ... 内存不足时的错误处理代码 ...}
}
// 完成列表属性的最终设置。Py_SET_SIZE(op, size);
op->allocated = size;
_PyObject_GC_TRACK(op); // 告知垃圾回收器对该对象进行监控。return (PyObject *) op;
}
代码片段解析
- 空闲列表逻辑：函数的前半部分是一项性能优化手段。CPython 会为最近删除的列表对象维护一个“回收站”（即空闲列表）。在创建新列表之前，代码会先检查这个“回收站”。如果能找到可复用的旧列表对象，就可以省去向操作系统申请新内存的步骤 —— 要知道，申请新内存的操作速度可是相当慢的。
- PyObject_GC_New：当“回收站”为空时，就会执行这个函数。它会从头开始创建一个全新的 PyListObject 结构体，并确保垃圾回收器能够对该对象进行监控。
- 空列表优化 ：
if (size <= 0)代码块是一项巧妙的内存节省策略。当你创建一个空列表（如[]）时，Python 不会为主要的 C 语言数组（ob_item）分配内存，而是将其指针设置为 NULL（相当于 Python 中的 None），直到你真正添加第一个元素时，才会为其分配内存。 - PyMem_Calloc：如果你创建一个指定大小的列表（例如
[None] * 10），该函数会用于分配ob_item这个 C 语言数组的内存，并且重要的是，它会将数组的所有槽位初始化为 NULL。 - 最终设置 ：函数最后几行代码会设置
ob_size和allocated字段（在列表创建初期，这两个字段的值是相等的），并正式将新创建的对象注册到垃圾回收器中。
核心收获
Python 列表的创建过程经过了高度优化。Python 的开发者深知，创建大量小型空列表是一种极为常见的操作模式。因此，他们实现了空闲列表机制，以加快列表对象的创建速度；同时，采用了空列表优化策略，通过延迟分配主数据数组的内存，提高了内存使用效率。
3.2 元素访问 ——PyList_GetItem ()（对应 my_list [index]）
现在，让我们来看看最简单的操作 —— 通过索引访问元素（如 my_list[i]）背后的 C 语言代码。这一操作由PyList_GetItem 函数负责处理。
PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
// 检查该对象是否为列表。if (!PyList_Check(op)) {// ... 内部错误处理代码 ...}
// 检查索引 i 是否在有效范围内。if (!valid_index(i, Py_SIZE(op))) {PyErr_SetString(PyExc_IndexError, "list index out of range");
return NULL;
}
// 这就是我们熟知的对“静态”C 语言数组的直接访问操作 :)
return ((PyListObject *)op)->ob_item[i];
}
代码片段解析
PyObject * PyList_GetItem(...)：定义了一个函数，该函数接收一个通用对象和一个索引i，并返回指向找到的元素的指针。if (!valid_index(i, Py_SIZE(op)))：这是索引边界检查。在尝试访问元素之前，会先确保索引i处于有效范围（从 0 到ob_size - 1）内。如果索引无效，则会设置错误信息为“IndexError”。return ((PyListObject *)op)->ob_item[i]：这是核心操作。它会将通用对象op强制转换为特定的PyListObject类型，然后直接访问ob_item这个 C 语言数组中索引为i的元素，从而获取指向目标元素的指针。
核心收获
列表元素访问操作的时间复杂度之所以是 O (1)（常数时间），是因为该操作本质上就是直接的内存计算，也称为指针运算。计算机可以通过“起始地址 +（索引 × 指针大小）”这个公式，精确计算出任意元素的内存地址。无论列表包含 10 个元素还是 1000 万个元素，计算机都能直接定位到目标数据，所需时间始终保持一致。
3.3 列表的动态特性源于何处？——list_resize ()
接下来是关键问题：当你向列表中追加元素时，列表为何能神奇地自动扩容？秘密就隐藏在 list_resize() 函数中。你无法在 Python 中直接调用这个函数，但像 .append() 和.insert()这样的方法，在需要调整列表容量时，都会调用它。
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
Py_ssize_t allocated = self->allocated;
size_t new_allocated;
PyObject **items;
// 快速路径：如果已有足够的空间，只需更新列表大小即可。if (allocated >= newsize && newsize >= (allocated >> 1)) {Py_SET_SIZE(self, newsize);
return 0;
}
// 慢速路径：需要额外分配内存。// 计算新的、更大的容量。new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
// 向操作系统申请更大的 C 语言数组内存，并将旧元素复制到新数组中。items = (PyObject **)PyMem_Realloc(self->ob_item, new_allocated * sizeof(PyObject *));
if (items == NULL) {// ... 内存不足时的错误处理代码 ...}
// 更新列表，使其使用新数组和新容量。self->ob_item = items;
Py_SET_SIZE(self, newsize);
self->allocated = new_allocated;
return 0;
}
代码片段解析
if (allocated>= newsize ...)：这是快速路径。当列表操作需要改变列表大小时，首先会检查当前已分配的空间是否足够（用于扩容场景），或者列表是否不会过度空荡（用于缩容场景）。如果新的列表大小能够很好地适配当前容量，那么只需更新ob_size的值，函数就可以直接返回。new_allocated = ...：这是扩容公式。当快速路径无法满足需求时，该行代码会计算出新的、更大的容量。它不会只额外分配一个槽位，而是会按比例（约为新大小的 1/8）分配额外空间，为列表后续的扩容预留出余地。items = PyMem_Realloc(...)：这是慢速路径，也是耗时较多的部分。PyMem_Realloc函数会向操作系统申请一块更大的内存空间，并且必须将旧数组中的所有元素指针复制到新的、更大的数组中。self->ob_item = items; ...：最后，函数会更新列表内部的ob_item指针和allocated计数器，使其分别指向新的 C 语言数组和反映新的容量大小。
核心收获
列表扩容（尤其是 .append() 方法）的高效性，要归功于这种“双路径”机制。大多数情况下，.append()调用会走快速路径，时间复杂度为 O (1)。偶尔，当需要扩容时，会走慢速路径，执行一次时间复杂度为 O (n) 的复制操作。Python 采用几何增长公式来计算新容量，确保随着列表规模的增大，这种耗时的复制操作发生的频率会越来越低。这样一来，扩容的成本就被分摊到了多次 .append() 操作中，使得 .append() 操作的平均时间复杂度保持为O(1)。
3.4 追加元素 ——list_append ()（对应 my_list.append (item)）
既然我们已经了解了 list_resize() 函数的工作原理，接下来就看看简单的 .append() 方法是如何调用它的。整个过程的起点是 C 语言函数list_append。
当你调用 .append() 时，首先执行的 C 语言函数是list_append。它相当于一个简单的“包装器”，负责处理一些基础准备工作，然后立即调用更核心的辅助函数_PyList_AppendTakeRef。
static PyObject *
list_append(PyList_Object *self, PyObject *object)
{
// Py_NewRef 会先增加对象的引用计数，再将其传递出去。if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {return NULL;}
Py_RETURN_NONE; // 这就是为什么 append()方法永远不会返回任何值。}
// 真正执行追加操作的核心函数
static inline int
_PyList_AppendTakeRef(PyListObject *self, PyObject *newitem)
{Py_ssize_t len = Py_SIZE(self);
Py_ssize_t allocated = self->allocated;
// 快速路径：列表末尾是否有空闲槽位？if (allocated > len) {
// 有空闲槽位！直接将新元素放入，并更新列表大小。PyList_SET_ITEM(self, len, newitem);
Py_SET_SIZE(self, len + 1);
return 0; // 追加成功！}
// 慢速路径：没有空闲槽位！调用 list_resize()函数扩容。return _PyList_AppendTakeRefListResize(self, newitem);
}
核心收获
.append()方法的设计目标只有一个：速度 。它总是优先尝试执行成本最低的 O (1) 操作（即直接将元素放入末尾空闲槽位）。只有在完全必要的情况下（没有空闲槽位时），才会调用list_resize() 函数进行扩容。这种“先检查、后操作”的逻辑，正是绝大多数场景下列表追加操作高效的关键原因。
3.5 插入元素 ——ins1 ()（对应 my_list.insert (index, item)）
追加元素之所以快速，是因为我们只需将元素放入列表末尾的空闲空间。但在列表开头或中间插入元素，速度往往较慢。C 语言函数 ins1() 揭示了其中的原因。
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
// 第一步：确保列表至少有一个空闲槽位（调用 list_resize()扩容）。if (list_resize(self, n + 1) < 0)
return -1;
// 内存移动操作！从最后一个元素开始，依次将元素向后移动一位，// 直到目标插入位置腾出空闲槽位。items = self->ob_item;
for (i = n; --i >= where;)
items[i+1] = items[i];
// 将新元素放入腾出的空闲槽位中。Py_INCREF(v);
items[where] = v;
return 0;
}
核心收获
插入操作的时间复杂度为 O(n)，罪魁祸首就是上述代码中的for 循环。如果要在列表开头插入元素（where=0），这个循环需要移动列表中的 每一个元素，才能腾出第一个槽位。操作的工作量与列表的大小直接成正比，因此时间复杂度为 O (n)。
3.6 删除元素 ——list_ass_slice ()（对应 del）
删除元素面临的问题与插入相反：插入是“腾出空间”，而删除是“填补空缺”。这一逻辑包含在 list_ass_slice() 函数中，该函数会调用 C 标准库中的 memmove() 函数来完成核心操作。
注 ：实际处理删除操作的 C 语言函数list_ass_slice() 非常复杂（因为它需要支持各种切片操作）。以下是简化后的函数delete_one_item，仅聚焦于“删除单个元素”的核心逻辑。
static int
delete_one_item(PyListObject *self, Py_ssize_t i)
{Py_ssize_t n = Py_SIZE(self);
PyObject **items = self->ob_item;
Py_ssize_t items_to_move = n - i - 1;
// ... 减少被删除对象的引用计数 ...
// 核心操作：填补删除元素后留下的空缺。if (items_to_move > 0) {memmove(&items[i], &items[i+1], items_to_move * sizeof(PyObject *));
}
// 最后，将列表大小减小 1（可能触发缩容）。return list_resize(self, n - 1);
}
代码片段解析
items_to_move = n - i - 1;：计算被删除元素右侧需要移动的元素数量（即删除位置之后的所有元素）。memmove(&items[i], &items[i+1], ...)：这是核心的“填补空缺”操作。memmove()是 C 语言中高度优化的内存操作函数，能够将一块连续的内存数据从一个位置“搬运”到另一个位置：&items[i]：目标地址（需要填补的空缺位置）；&items[i+1]：源地址（被删除元素右侧的第一个元素）；
该操作会将被删除元素右侧的所有元素，整体向左移动一位，从而填补空缺。
核心收获
删除操作的时间复杂度同样为 O(n)，根源在于memmove() 函数。为了填补删除元素后留下的空缺，CPython 必须物理移动该元素右侧的所有元素。如果删除列表的第一个元素（del my_list[0]），就需要移动列表中其余的 n-1 个元素。操作的工作量与需要移动的元素数量直接成正比，因此时间复杂度为 O (n)。
四、最终结论：列表的本质是什么？
那么，Python 在列表背后隐藏了什么秘密？通过层层拆解 CPython 的 C 语言源代码，我们找到了答案 —— 这背后并没有魔法。我们日常使用的、动态可变的 Python 列表，其底层竟然是基于一个简单的 静态 C 语言数组 构建的。这就是列表的核心秘密。
了解这一本质，会彻底改变你对自己代码的认知：
- 为什么
my_list[99999]这样的元素访问如此快速？因为这是静态 C 语言数组的“原生能力”—— 通过简单的内存地址计算，直接定位到目标数据。 - 为什么
my_list.insert(0, 'x')这样的插入操作可能很慢？因为你正在目睹静态数组的“局限性”—— 为了在开头腾出空间，必须逐个移动所有元素。
归根结底，Python 列表是一项精妙的工程设计，其核心是 一种巧妙的权衡策略 ：它假设你会更频繁地在列表末尾追加元素，而非在开头插入元素，因此通过“预分配内存”（allocated 字段）的策略优化了追加操作。而现在，你已经洞悉了这一秘密。
FAQ
1. 为什么 Python 列表能自动调整大小，而 C 语言的数组却不行？
Python 列表的底层虽然依赖静态 C 语言数组（通过 PyListObject 的ob_item字段存储），但它通过 list_resize() 函数实现了“动态扩容”。当列表元素数量（ob_size）接近或超过已分配槽位（allocated）时，list_resize()会按“几何增长公式”（约新增当前大小的 1/8 + 6）申请更大的内存空间，复制旧数组元素到新空间，再更新 ob_item 指针和 allocated 值。而 C 语言数组的大小在定义时就固定，无法直接修改，需手动申请新内存、复制数据，因此不具备“自动调整”能力。
2. 为什么 len(my_list) 调用能瞬间完成，无论列表多大？
因为 len() 函数的返回值直接取自 PyListObject 的ob_size字段 —— 这个字段会在列表添加 / 删除元素时实时更新（如 append() 时ob_size+1，del时ob_size-1），是“预计算好的值”。无需遍历列表计数，因此时间复杂度为 O (1)，无论列表包含 10 个还是 1000 万个元素，都能瞬间返回结果。
3. 为什么 my_list.append(item) 效率高，而 my_list.insert(0, item) 效率低？
append()默认优先走“快速路径”：若allocated > ob_size（存在空闲槽位），直接将元素放入列表末尾，仅更新ob_size，时间复杂度 O (1)；即使需扩容（走“慢速路径”），也因“几何增长”策略，扩容频率随列表增大而降低，平均效率仍接近 O (1)。insert(0, item)需先调用list_resize()扩容（若无空闲槽位），再通过for循环将所有元素向后移动一位（腾出第一个槽位），最后插入新元素。移动元素的工作量与列表大小成正比，时间复杂度为 O (n)，因此效率远低于append()。
4. 列表删除元素后，内存会立即释放吗？
不会完全“立即释放”，分为两种情况：
- 被删除的元素：其引用计数会减 1，若计数变为 0，Python 垃圾回收器（GC）会在后续时机释放该元素的内存；
- 列表本身的内存：删除元素后，
list_resize()会检查是否需要“缩容”（仅当新ob_size小于allocated的 1/2 时），若缩容则释放部分空闲内存，但不会每次删除都缩容，避免频繁申请 / 释放内存的开销；此外，CPython 还会将已删除的空列表对象存入“空闲列表（freelist）”，供后续创建新列表时复用，进一步优化内存效率。
5. 列表中的元素是直接存储数据，还是存储指针？
列表不直接存储数据，而是存储“指向 Python 对象的指针”。PyListObject的 ob_item 字段是 PyObject ** 类型（指针的指针），它指向一个“指针数组”—— 数组中的每个元素都是指向具体 Python 对象（如整数、字符串、字典等）的指针。这种设计让列表能容纳不同类型的元素（所有对象都继承自PyObject），且避免直接拷贝数据（仅操作指针），提升操作效率。
