Python列表的内部工作原理：深入理解数据结构
1. 列表是如何工作的？
myList = [1, 2, 3, 4]
for i in myList:
print(i)
看起来很简单直观，对吧？所有学过Python的人都在某个时候使用过列表。几乎所有的教程、视频、训练营和博客都会讲解如何使用列表以及它们提供的各种方法。但你是否曾经想过列表究竟是如何工作的？它们是如何自动调整大小的，这与C语言中的静态数组有什么不同？Python到底隐藏了什么？它实际上是如何添加或删除元素的？
这就是本文要讨论的内容。我们将通过查看唯一能够揭示真相的地方——源代码，来回答所有这些问题。我们的任务是揭开帷幕，窥探支撑Python的C代码，理解列表的真实面貌。这里没有魔法，只有纯粹的逻辑。
那么，为什么我们突然谈论起C语言？当你在终端中输入python3时，你实际上是在运行一个程序。这个程序，也就是Python语言最流行的实现，被称为CPython，它几乎完全是用C语言编写的。
可以把它想象成实际运行你的Python脚本的软件。每当你创建一个列表或调用.append()方法时，你实际上是在告诉CPython运行一个特定的C函数。要真正理解列表是如何工作的，我们必须查看定义列表的C代码。
2. Python是如何实现对象的？
第一个令人惊讶的事实是，Python这个著名的面向对象语言是建立在C语言之上的，而C语言并不具备我们通常理解的类和对象。这怎么可能呢？
面向对象编程的基本构建块实际上只是结构体（用于组织数据）、指针（用于创建引用）、函数指针（用于表示方法）和间接引用（一种在运行时决定执行哪个函数的方式）。
这四个构建块让CPython能够支持面向对象编程的关键特性：将数据和方法组合在一起（封装）、让一个类继承另一个类（继承）以及让对象根据其类型表现出不同的行为（多态）。
现在让我们看看这些对象是如何用C语言实现的！
2.1 通用对象 - PyObject
这是所有Python对象的根。每个其他对象结构体都包含一个PyObject，使其成为一切的绝对基础。下面是使用结构体和指针定义的PyObject：
typedef struct _object {
Py_ssize_t ob_refcnt;
PyTypeObject *ob_type;
} PyObject;
属性解析
1. ob_refcnt
全称：Object Reference Count（对象引用计数）
本质：一个简单的整数计数器
功能：记录当前有多少个变量或其他对象正在引用这个对象
重要性：这是Python主要内存管理系统的核心部分。当计数降到零时，Python知道没有人再关心这个对象了，就会释放其内存
2. 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()返回的数字。它是一个预先计算好的值，这就是为什么对列表或元组调用len()是即时的，O(1)操作，无论它有多大都不需要计数
2.3 列表对象 - PyListObject
好了，准备好接受这个重大秘密吧，这个让我陷入这一切的秘密。在内部，一个动态的、灵活的Python列表基本上就是一个静态的C数组😱。是的，我当时也是一脸震惊。
让我们看看它的定义：
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
属性解析
1. PyObject_VAR_HEAD
这是另一个宏，包含了PyVarObject的所有字段
所以我们的列表对象继承了：
ob_refcnt（引用计数）
ob_type（类型信息）
ob_size（当前大小）
2. ob_item
本质：一个指向指针的指针
功能：这就是实际的C数组，存储着指向列表中每个Python对象的指针
为什么是双指针：因为它指向一个指针数组，每个指针又指向一个Python对象
3. allocated
本质：另一个整数
功能：跟踪为ob_item分配的总槽位数
重要性：这就是Python列表"动态"增长的秘密
3. 列表操作的内部机制
3.1 创建新列表
当你写my_list = []时，Python会：
分配一个新的PyListObject结构体
初始化所有计数器（ob_refcnt = 1, ob_size = 0）
分配一个小的初始ob_item数组（通常为0）
设置allocated = 0
3.2 列表的增长策略
这是Python列表最有趣的部分。它不会每次都只增加一个槽位，而是使用一个聪明的过度分配策略：
当列表为空时，分配4个槽位
当需要增长时，新大小 = 旧大小 + (旧大小 >> 3) + 3
这意味着列表会以大约12.5%的速度增长
这种策略在时间和空间之间取得了很好的平衡：
不会太频繁地调整大小（这很慢）
也不会浪费太多内存（通常最多浪费12.5%）
3.3 添加元素（append）
当你调用my_list.append(x)时，Python会：
检查是否有空闲槽位（allocated > ob_size）
如果有：直接将新项放入下一个槽位
如果没有：调用list_resize()分配更多空间，然后添加项
这就是为什么append通常是O(1)操作，但偶尔会需要O(n)时间来增长数组。
3.4 插入元素（insert）
当你在列表中间插入一个元素时，Python必须：
确保有足够的空间（可能需要调整大小）
将插入点后的所有元素向右移动一个位置
在空出的槽位中放入新元素
这就是为什么insert是O(n)操作 - 它可能需要移动很多元素。
3.5 删除元素（del）
删除元素时，Python会：
将删除点后的所有元素向左移动一个位置
减少ob_size
可能调整数组大小（如果浪费太多空间）
这也是一个O(n)操作，因为它需要移动元素来填补空缺。
4. 最终总结：列表的本质
那么，Python到底隐藏了什么？在剥开层层包装，深入研究C源代码之后，我们找到了答案，这并不是魔法。我们每天使用的动态的、不断增长的列表是建立在一个简单的静态C数组之上的。这就是秘密。
了解这一点会改变你看待自己代码的方式。使用my_list[99999]进行快速访问？这是C数组的原始能力，通过简单的数学计算找到内存地址。但这种能力是有代价的。my_list.insert(0, 'x')感觉很慢的原因是，你正在见证同一个C数组的蛮力现实，它必须一个接一个地物理移动每个元素，只是为了在前面腾出空间。
最终，列表只是一个建立在巧妙权衡之上的优秀工程作品。它打赌你会比在开头插入更频繁地使用append，所以它通过过度分配策略为这种情况进行了优化。现在，你也知道了这个秘密。
恭喜你读到最后！🎉