楔子
最近有读者发了一条私信，希望我介绍一下 Python 列表和字典在读写数据的时候谁更快。
那就安排一下，我们先来介绍列表和字典的底层实现，如果了解了具体的实现，那么一切问题就都迎刃而解了。我准备分多篇文章介绍，本次先来介绍列表。
列表是怎么实现的？
在初学列表的时候，可能书上会告诉你列表就是一个大仓库，什么都可以存放。但我们要知道，无论是 Python 的变量，还是列表、元组里面的元素，它们本质上都是一个指针。
并且根据我们使用列表的经验，可以得出以下两个结论：
- 每个列表的元素个数可以不一样，所以这是一个变长对象；
- 可以对列表的元素进行添加、删除、修改等操作，所以这是一个可变对象；
而列表在底层由PyListObject结构体表示，定义于头文件 Include/listobject.h 中：
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
我们看到里面有如下成员：
- PyObject_VAR_HEAD：变长对象的公共头部信息，包含了以下三个字段；
- ob_refcnt：对象的引用计数；
- ob_type：对象的类型；
- ob_size：负责维护变长对象的长度，比如 len(列表) 的时候，会直接返回这里的 ob_size；
- ob_item：一个二级指针，指向 PyObject * 类型的指针数组，这个指针数组保存的便是对象的指针，而操作底层数组都是通过 ob_item 来进行操作的；
- allocated：容量，我们知道列表底层是使用了 C 的数组，而底层数组的长度就是列表的容量；
列表之所以要有容量的概念，是因为列表可以动态添加和删除元素，但是底层的数组在创建完毕之后，其长度却是固定的。所以一旦添加新元素的时候，发现数组已满，这时候只能申请一个更长的数组，同时把旧数组中的元素依次拷贝到新数组里面（这一过程就是列表的扩容），然后再将新元素添加进去，最后再将旧数组释放掉。
但是问题来了，总不可能每添加一个元素，就申请一次数组、将所有元素都拷贝一次吧。所以列表在扩容的时候，会将数组申请的长一些，可以在添加元素的时候不用每次都申请新的数组。
这便是列表的底层结构示意图，我们看到底层数组的长度为 5，说明此时列表的容量为 5，但是里面只有 3 个 PyObject * 指针，说明列表的 ob_size 是 3，或者说列表里面此时有 3 个元素。
如果这个时候往列表中 append 一个元素，那么会将这个新元素设置在数组索引为 ob_size 的位置、或者说索引为 3 的位置。一旦设置完，ob_size 会自动加 1，因为 ob_size 要和列表的长度保持一致。
如果此时再往列表中 append 一个元素的话，那么还是将新元素设置在索引为 ob_size 的位置，此时也就是索引为 4 的位置。然后 ob_size 加 1，变成 5。
列表的容量是 5，但此时长度也达到了 5，这说明当下一次 append 的时候，已经没有办法再容纳新的元素了。因为此时列表的长度、或者说元素个数已经达到了容量。当然最直观的还是这里的底层数组，很明显全都占满了。那这个时候如果想再接收新元素的话，要怎么办呢？显然只能扩容了。
原来的容量是 5，长度也是 5，当再来一个新元素的时候由于没有位置了，所以要扩容。但是扩容的时候肯定会将容量申请的大一些、即底层数组申请的长一些。
而申请的新的底层数组长度是9，那么说明列表的容量就变成了 9。然后将原来数组中的 PyObject * 按照顺序依次拷贝到新的数组里面，并让 ob_item 指向新的数组。然后将新元素设置在新数组中索引为 ob_size 的位置、即索引为 5 的位置，再将 ob_size 加 1（此时 ob_size 变成了 6）。
以上便是列表底层在扩容的时候所经历的过程。
并且通过以上几张图，我们可以得知列表在append之后地址是不变的。因为如果长度没有达到容量，那么 append 其实就是往底层数组中设置了一个新元素；如果达到容量了，那么会扩容，但扩容只是申请一个新的指针数组，然后让 ob_item 重新指向罢了。
所以底层的指针数组会变，但 PyListObject 结构体实例本身是没有变化的。因此列表执行 append, extend, pop, insert 的时候，因为是本地操作，所以它的地址是不会变化的。
下面我们再来看看列表所占的内存大小是怎么算的：
- PyObject_VAR_HEAD：24字节；
- ob_item：8 字节；
- allocated：8 字节；
所以总共 40 字节，但是不要忘记，在计算列表大小的时候，ob_item 指向的指针数组也要算在内。所以：列表的大小 = 40 + 8 * 指针数组长度(或者说列表容量)。注意是指针数组长度、或者说列表容量，可不是列表长度，因为数组一旦申请了，不管你用没用，大小就摆在那里了。就好比你租了间房子，就算不住，房租该交还是得交。
# 显然一个空数组占40个字节
print([].__sizeof__()) # 40
# 40 + 3 * 8 = 64
print([1, 2, "x" * 1000].__sizeof__()) # 64
#虽然里面有一个长度为1000的字符串
#但我们说列表存放的都是指针，所以大小都是8字节
#注意: 我们通过lst = [1, 2, 3]这种方式创建列表的话
#不管内部元素有多少个, 其ob_size和allocated都是一样的
#只有当列表在添加元素的时候，发现容量不够了才会扩容
lst = list(range(10))
# 40 + 10 * 8 = 120
print(lst.__sizeof__()) # 120
# 这个时候append一个元素
lst.append(123)
print(lst.__sizeof__()) # 184
#我们发现大小达到了184, (184 - 40) // 8 = 18
#说明扩容之后申请的数组的长度为18
所以列表的大小我们就知道是怎么来的了，以及为什么列表在通过索引定位元素的时候，时间复杂度是 O(1)。因为列表存储的都是对象的指针，不管对象有多大，其指针大小是固定的，都是 8 字节。通过索引可以瞬间计算出偏移量，从而找到对应元素的指针，而操作指针会自动操作指针所指向的内存。
print([1, 2, 3].__sizeof__()) # 64
print([[1, 2, 3]].__sizeof__()) # 48
相信上面这个结果，你肯定能分析出原因。因为第一个列表中有3个指针，所以大小是40 + 24 = 64；而第二个列表中有一个指针，所以是40 + 8 = 48。用一张图来展示一下[1, 2, 3]和[[1, 2, 3]]的底层结构，看看它们之间的区别：
到此相信你已经彻底掌握列表的结构了，下面我们来分析一下列表相关操作的时间复杂度。
添加元素
假设有如下这样一个列表：
我们来看一下它在添加元素的时候，是怎么表现的。
首先添加元素有很多种方式，其中 append 方法用于向尾部追加一个元素，看一下它的底层实现。
static PyObject *
list_append(PyListObject *self, PyObject *object)
{
//显然调用的app1是核心, 它里面实现了添加元素的逻辑
//Py_RETURN_NONE是一个宏，表示返回Python中的None
//因为list.append返回的就是None
if (app1(self, object) == 0)
Py_RETURN_NONE;
return NULL;
}
static int
app1(PyListObject *self, PyObject *v)
{
//参数self是列表，v是要添加的元素
//获取列表的长度
Py_ssize_t n = PyList_GET_SIZE(self);
//......
//因为v作为了列表的一个元素，所以其指向的对象的引用计数要加1
Py_INCREF(v);
//设置元素，原来的列表长度为n，最大索引是n - 1
//那么追加的话就等于将元素设置在索引为n的地方
PyList_SET_ITEM(self, n, v);
return 0;
}
以上就是 append 的逻辑，所谓插入、追加本质上都是先计算出索引，然后再通过索引设置元素。
如果上面的列表 append 一个 6，就会变成如下：
还是很好理解的。
添加元素除了 append，还可以使用 insert，和只能在尾部追加的 append 不同，该方法可以在任意位置插入。
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
/*
参数self：列表
参数where：索引
参数v：插入的值
*/
//i是循环变量，n则是当前列表的元素个数
Py_ssize_t i, n = Py_SIZE(self);
//指向指针数组的二级指针
PyObject **items;
//......
//确定插入位置
if (where < 0) {
//如果where小于0，则加上 n
//比如有6个元素，where=-1，那么会加上6，得到5
//显然就是insert在索引为5的位置上
where += n;
//如果吃撑了，写个 -100，加上元素的个数还是小于0
if (where < 0)
//那么where = 0，就在开头插入
where = 0;
}
//如果where > n，那么就在索引为n的位置插入，
//可元素个数为n，最大索引是n-1啊
//对，所以此时就相当于append
if (where > n)
where = n;
//走到这，索引就确定完了，然后是设置元素
//拿到原来的二级指针，指向一个指针数组
items = self->ob_item;
//然后从where处开始，把索引为i的值赋值给索引为i+1
//相当于元素后移
//既然是在where处插入，那么where之前的就不需要动了
//所以到where处就停止了
for (i = n; --i >= where; )
items[i+1] = items[i];
//增加v指向的对象的引用计数，因为要被放到列表里
Py_INCREF(v);
//将索引为where的值设置成v
items[where] = v;
return 0;
}
逻辑不难理解，然后是时间复杂度。
- append：显然时间复杂度为 O(1)，只是在指定位置写入一个元素。但需要注意：如果容量不够了，那么会扩容，而扩容是一个 O(n) 操作。因此 append 最坏情况下也是一个 O(n) 操作，只不过扩容不会频繁