08-解密Python中列表的底层实现

08-解密Python中列表的底层实现

楔子

Python中的列表可以说使用的非常广泛了，在初学列表的时候，老师会告诉你列表就是一个大仓库，什么都可以存放。不过在最开始的几个章节中，我们花了很大的笔墨介绍了Python中的对象，并明白了Python中变量的本质，我们知道列表中存放的元素其实都是泛型指针PyObject *，所以到现在列表已经没有什么好神秘的了。

并且根据我们使用列表的经验，我们可以得出以下两个结论：

• 每个列表中的元素个数可以不一样：所以这是一个变长对象
• 可以对列表中的元素进行添加、删除、修改等操作，所以这是一个可变对象

在分析列表对应的底层结构之前，我们先来回顾一下列表的使用。

# 创建一个列表，这里是通过Python/C API创建的
>>> lst = [1, 2, 3, 4]
>>> lst
[1, 2, 3, 4]

# 往列表尾部追加一个元素，此时是在本地操作的，返回值为None
# 但是列表被改变了
>>> lst.append(5)
>>> lst
[1, 2, 3, 4, 5]

# 从尾部弹出一个元素，会返回弹出的元素
>>> lst.pop()
5
# 此时列表也会被修改
>>> lst
[1, 2, 3, 4]
# 另外在pop的时候还可以指定索引，弹出指定的元素
>>> lst.pop(0)
1
>>> lst
[2, 3, 4]

# 也可以在指定位置插入一个元素
>>> lst.insert(0, 'x')
>>> lst
['x', 2, 3, 4]

# 通过extend在尾部追加多个元素
>>> lst.extend([7, 8, 9])
>>> lst
['x', 2, 3, 4, 7, 8, 9]

# 查找指定元素第一次出现的位置
>>> lst.index(3)
2

# 计算某个元素在列表中出现的次数
>>> lst.count(3)
2

# 翻转列表
>>> lst.reverse()
>>> lst
[9, 8, 7, 4, 3, 2, 'x']

# 根据元素的值删除第一个出现的元素
>>> lst.remove(4)
[9, 8, 7, 3, 2, 'x']

# 清空列表
>>> lst.clear()
>>> lst
[]
>>>

上面的一些操作是列表经常使用的，但是在分析它的实现之前，我们肯定要了解它们的时间复杂度如何。这些东西即使不看源码，也是必须要知道的，尤其想要成为一名优秀的Python工程师。

• append：会向尾部追加元素，所以时间复杂度为O(1)
• pop：默认从尾部弹出元素，所以时间复杂度为O(1);如果不是尾部，而是从其它的位置弹出元素的话，那么该位置后面所有的元素都要向前移动，此时时间复杂度为O(n)
• insert：向指定位置插入元素，该位置后面的所有元素都要向后移动，所以时间复杂度为O(n)

注意：由于列表里面的元素个数是可以自由变化的，所以列表有一个容量的概念，我们后面会说。当添加元素时，列表可能会扩容；同理当删除元素时，列表可能会缩容。

下面我们就来看一下列表对应的底层结构。

列表的内部结构–PyListObject

*list* 对象(列表)在 *Python* 内部，由 *PyListObject* 结构体表示，定义于头文件 *Include/listobject.h* 中：

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

我们看到里面有如下成员：

• PyObject_VAR_HEAD: 变长对象的公共头部信息
• ob_item：一个二级指针，指向一个PyObject *类型的指针数组，这个指针数组保存的便是对象的指针，而操作底层数组都是通过ob_item来进行操作的。
• allocated：容量, 我们知道列表底层是使用了C的数组, 而底层数组的长度就是列表的容量

列表之所以要有容量的概念，是因为列表可以动态添加元素，但是底层的数组在创建完毕之后，其长度却是固定的。所以一旦添加新元素的时候，发现底层数组已经满了，这个时候只能申请一个更长的数组，同时把原来数组中的元素依次拷贝到新的数组里面(这一过程就是列表的扩容)，然后再将新元素添加进去。但是问题来了，总不可能每添加一个元素，就申请一次数组、将所有元素都拷贝一次吧。所以Python在列表扩容的时候，会将底层数组申请的长一些，可以在添加元素的时候不用每次都申请新的数组。

这便是列表的底层结构示意图，图中的object只是单纯的代指对象，不是Python中的基类object。我们看到底层数组的长度为5，说明此时列表的容量为5，但是里面只有3个PyObject *指针，说明列表的ob_size是3，或者说列表里面此时有3个元素。注意：尽管底层数组的容量目前是5个，但是我们访问的时候，最多只能访问到第三个元素，也就是说索引最大只能是2，这是显而易见的，因为列表里面只有3个元素。

如果这个时候我们往列表中append一个元素，那么会将这个新元素设置在底层数组中索引为ob_size的位置、或者说第四个位置。一旦设置完，ob_size会自动加1，因为ob_size要和列表的长度保持一致。

如果此时再往列表中append一个元素的话，那么还是将新元素设置在索引为ob_size的位置，此时也就是第5个位置。

列表的容量是5，但此时长度也达到了5，这说明当下一次append的时候已经没有办法再容纳新的元素了。因为此时列表的长度、或者说元素个数已经达到了容量，当然最直观的还是这里的底层数组，很明显全都占满了。那这个时候如果想再接收新的元素的话，要怎么办呢？显然只能扩容了。

原来的容量是5个，长度也是5个，当再来一个新元素的时候由于没有位置了，所以要扩容。但是扩容的时候肯定会将容量申请的大一些、即底层数组申请的长一些(具体申请多长,Python内部有一个公式,我们后面会说)，假设申请的新的底层数组长度是8，那么说明列表的容量就变成了8。然后将原来数组中的PyObject *按照顺序依次拷贝到新的数组里面，再让ob_item指向新的数组。最后将要添加的新元素设置在新的数组中索引为ob_size的位置、即第6个位置，然后将ob_size加1，此时ob_size就变成了6。

以上便是列表底层在扩容的时候所经历的过程。

由于扩容会申请新的数组，然后将旧数组的元素拷贝到新数组中，所以这是一个时间复杂度为O(n)的操作。而append可能会导致列表扩容，因此append最坏情况下也是一个O(n)的操作，只不过扩容不会频繁发生，所以append的平均时间复杂度还是O(1)。

​ 另外我们还可以看到一个现象，那就是Python中的列表在底层是分开存储的，因为PyListObject结构体实例并没有存储相应的指针数组，而是存储了指向这个指针数组的二级指针。显然我们添加、删除、修改元素等操作，都是通过ob_item这个二级指针来间接操作这个指针数组。

​ 所以底层对应的PyListObject实例的大小其实是不变的，因为指针数组没有存在PyListObject里面。但是Python在计算内存大小的时候是会将这个指针数组也算进去的，所以Python中列表的大小是可变的。

而且我们知道，列表在append之后地址是不变的，至于原因上面的几张图已经解释的很清楚了。如果长度没有达到容量，那么append其实就是往底层数组中设置了一个新元素；如果达到容量了，那么会扩容，但是扩容只是申请一个新的指针数组，然后让ob_item重新指向罢了。所以底层数组会变，但是PyListObject结构体实例本身是没有变化的。因此列表无论是append、extend、pop、insert等等，只要是在本地操作，那么它的地址是不会变化的。

下面我们再来看看Python中的列表所占的内存大小是怎么算的：

• PyObject_VAR_HEAD: 24字节
• ob_item: 二级指针, 8字节
• allocated: 8字节

但是不要忘记，在计算列表大小的时候，ob_item指向的指针数组也要算在内。所以：一个列表的大小 = 40 + 8 * 指针数组长度(或者列表容量)。注意是底层数组长度、或者列表容量，可不是列表长度，因为底层数组一旦申请了，不管你用没用，大小就摆在那里了。就好比你租了间房子，就算不住，房租该交还是得交。

# 显然一个空数组占40个字节
print([].__sizeof__())  # 40

# 40 + 3 * 8 = 64
print([1, 2, "x" * 1000].__sizeof__())  # 64
# 虽然里面有一个长度为1000的字符串，但我们说列表存放的都是指针, 所以大小都是8字节


# 注意: 我们通过l = [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]]的底层结构，看看它们之间的区别：

​ 分析完PyListObject之后，我们来看看它支持的操作，显然我们要通过类型对象PyList_Type来查看。

PyTypeObject PyList_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    sizeof(PyListObject),
    0,
    (destructor)list_dealloc,                   /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    (reprfunc)list_repr,                        /* tp_repr */
    0,                                          /* tp_as_number */
    &list_as_sequence,                          /* tp_as_sequence */
    &list_as_mapping,                           /* tp_as_mapping */
    //......
};

我们看到，列表支持序列型操作和映射型操作，下面我们就来分析一下。

列表支持的操作

我们看看平常使用的列表所支持的操作在底层是如何实现的。

自动扩容

我们先来说说列表的扩容，因为我们知道列表是会自动扩容的，那么什么时候会扩容呢？我们说列表扩容的时候，是在添加元素时发现底层数组已经满了的情况下才会扩容。换句话说，一个列表在添加元素的时候会扩容，那么说明在添加元素之前，其内部的元素个数和容量是相等的。然后我们看看底层是怎么实现的，这些操作都位于Objects/listobject.c中。

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{   //参数self就是列表啦，newsize指的元素在添加之后的ob_size
    //比如列表的ob_size是5，那么在append的时候发现容量不够，所以会扩容，那么这里的newsize就是6
    //如果是extend添加3个元素，那么这里的newsize就是8
    //当然list_resize这个函数不仅可以扩容，也可以缩容，假设列表原来有1000个元素，这个时候将列表清空了
    //那么容量肯定缩小，不然会浪费内存，如果清空了列表，那么这里的newsize显然就是0
    
    //items是一个二级指针，显然是用来指向指针数组的
    PyObject **items;
    //新的容量，以及对应的内存大小
    size_t new_allocated, num_allocated_bytes;
    //获取原来的容量
    Py_ssize_t allocated = self->allocated;
	
    //如果newsize达到了容量的一半，但还没有超过容量, 那么意味着newsize、或者新的ob_size和容量是匹配的，所以不会变化
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        //只需要将列表的ob_size设置为newsize即可
        Py_SIZE(self) = newsize;
        return 0;
    }

    //走到这里说明容量和ob_size不匹配了，所以要进行扩容或者缩容。
    //因此要申请新的底层数组，申请多少个?这里给出了公式,一会儿我们可以通过Python进行测试
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    //显然容量不可能无限大，是有范围的，当然这个范围基本上是达不到的
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }
	
    //如果newsize为0，那么容量也会变成0，假设将列表全部清空了，容量就会变成0
    if (newsize == 0)
        new_allocated = 0;
    
    //我们说数组中存放的都是PyObject *, 所以要计算内存
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    //申请相应大小的内存，将其指针交给items
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        //如果items是NULL, 代表申请失败
        PyErr_NoMemory();
        return -1;
    }
    //然后让ob_item = items, 也就是指向新的数组, 此时列表就发生了扩容或缩容
    self->ob_item = items;
    //将ob_size设置为newsize, 因为它维护列表内部元素的个数
    Py_SIZE(self) = newsize;
    //将原来的容量大小设置为新的容量大小
    self->allocated = new_allocated;
    return 0;
}

我们看到还是很简单的，没有什么黑科技，下面我们就来分析一下列表扩容的时候，容量和元素个数之间的规律。其实在list_resize函数中是有注释的，其种一行写着：The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

说明我们往一个空列表中不断append元素的时候，容量会按照上面的规律进行变化，我们来试一下。

# 还记得底层是怎么改变容量的吗？
# 我们说有一个公式: new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
# 我们来看一下

lst = []
allocated = 0
print("此时容量是: 0")

for item in range(100):
    lst.append(item)  # 添加元素
    
    # 计算ob_size
    ob_size = len(lst)

    # 判断ob_size和当前的容量
    if ob_size > allocated:
        # lst的大小减去空列表的大小, 再除以8显然就是容量的大小, 因为不管你有没有用, 容量已经分配了
        allocated = (lst.__sizeof__() - [].__sizeof__()) // 8
        print(f"列表扩容啦, 新的容量是: {allocated}")
"""
此时容量是: 0
列表扩容啦, 新的容量是: 4
列表扩容啦, 新的容量是: 8
列表扩容啦, 新的容量是: 16
列表扩容啦, 新的容量是: 25
列表扩容啦, 新的容量是: 35
列表扩容啦, 新的容量是: 46
列表扩容啦, 新的容量是: 58
列表扩容啦, 新的容量是: 72
列表扩容啦, 新的容量是: 88
列表扩容啦, 新的容量是: 106

Process finished with exit code 0
"""

我们看到和官方给的结果是一样的，显然这是毫无疑问的，我们根据底层的公式也能算出来。

ob_size = 0
allocated = 0

print(allocated, end=" ")
for item in range(100):
    ob_size += 1
    if ob_size > allocated:
        allocated = ob_size + (ob_size >> 3) + (3 if ob_size < 9 else 6)
        print(allocated, end=" ")
# 0 4 8 16 25 35 46 58 72 88 106 

​ 但还是那句话，扩容是指解释器发现容量不够的情况下才会扩容，如果我们直接通过lst = []这种形式创建列表的话，那么其长度和容量是一样的。

lst = [0] * 1000
# 长度和容量一致
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)  # 1000 1000

# 但此时添加一个元素的话, 那么ob_size会变成1001, 大于容量1000
# 所以此时列表就要扩容了, 执行list_resize, 里面的new_size就是1001, 然后是怎么分配容量来着
# new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
print("新容量:", 1001 + (1001 >> 3) + (3 if 1001 < 9 else 6))  # 新容量: 1132

# append一个元素，列表扩容
lst.append(123)
# 计算容量
print((lst.__sizeof__() - [].__sizeof__()) // 8)  # 1132

# 结果是一样的, 因为底层就是这么实现的, 所以结果必须一样
# 只不过我们通过这种测试的方式证明了这一点, 也更加了解了底层的结构是什么样子的。

​ 介绍完扩容，那么介绍缩容，因为列表元素个数要是减少到和容量不匹配的话，也要进行缩容。

​ 举个生活中的例子，假设你租了10间屋子用于办公，显然你要付10间屋子的房租，不管你有没有住，一旦租了肯定是要付钱的。同理底层数组也是一样，只要你申请了，不管有没有元素，内存已经占用了。但有一天你用不到10间屋子了，假设会用8间或者9间，那么会让剩余的屋子闲下来。但由于退租比较麻烦，并且只闲下来一两间屋子，所以多余的屋子就不退了，还是会付10间屋子的钱，这样当没准哪天又要用的时候就不用重新租了。对于列表也是如此，如果在删除元素(相当于屋子不用了)的时候发现长度没有超过容量但是又达到了容量的一半，所以也不会缩容。但是，如果屋子闲了8间，也就是只需要两间屋子就足够了，那么此时肯定要退租了，闲了8间，可能会退掉6间。

lst = [0] * 1000
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)  # 1000 1000

# 删除500个元素, 此时长度或者说ob_size就为500
lst[500:] = []
# 但是ob_size还是达到了容量的一半, 所以不会缩容
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)  # 500 1000

# 如果再删除一个元素的话, 那么不好意思, 显然就要进行缩容了, 因为ob_size变成了499, 小于1000 // 2
# 缩容之后容量怎么算呢? 还是之前那个公式
print(499 + (499 >> 3) + (3 if 499 < 9 else 6))  # 567

# 测试一下, 删除一个元素, 看看会不会按照我们期待的规则进行缩容
lst.pop()
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)  # 499 567

一切都和我们想的是一样的，另外在代码中我们还看到一个if语句，就是如果newsize是0，那么容量也是0，我们来测试一下。

lst = [0] * 1000
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)  # 1000 1000

lst[:] = []
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)  # 0 0

# 如果按照之前的容量变化公式的话, 会发现结果应该是3, 但是结果是0, 就是因为多了if判断:如果newsize是0, 就把容量也设置为0
print(0 + (0 >> 3) + (3 if 0 < 9 else 6))  # 3
# 但为什么要这么做呢?因为Python认为, 列表长度为0的话，说明你不想用这个列表了, 所以多余的3个也没有必要申请了

# 我们还以租房为栗, 如果你一间屋子都不用了, 说明可能你不用这里的屋子办公了
# 因此多余3间屋子也没有必要再租了, 所以直接全部退掉

以上就是列表在改变容量时所采用的策略，我们从头到尾全部分析了一遍。

append追加元素

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);
    assert (v != NULL);
    //如果长度已经达到了限制，那么无法再添加了, 会抛出OverflowError
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
	
    //还记得这个list_resize吗? self就是列表, n + 1就是newsize，或者说新的ob_size
    //会自动判断是否要进行扩容, 当然里面还有重要的一步，就是将列表的ob_size设置成newsize、也就是这里的n + 1
    //因为append之后列表长度大小会变化，而ob_size则要时刻维护这个大小
    if (list_resize(self, n+1) < 0)
        return -1;
	
    //因为v作为了列表的一个元素，所以其指向的对象的引用计数要加1
    Py_INCREF(v);
    //然后调用PyList_SET_ITEM，这是一个宏，它的作用就是设置元素的，我们下面会看这个宏长什么样
    //原来的列表长度为n, 里面的元素的最大索引是n - 1，那么追加的话就等于将元素设置在索引为n的地方
    PyList_SET_ITEM(self, n, v);
    return 0;
}

//我们说PyList_SET_ITEM是用来设置元素的，设置在什么地方呢？显然是设置在底层数组中
//PyList_SET_ITEM一个宏,除了这个宏之外，还有很多其它的宏，它们位于Inlcude/listobject.h中
#define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i])
#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
#define PyList_GET_SIZE(op)    (assert(PyList_Check(op)),Py_SIZE(op))
//这些宏的作用是啥，一目了然

获取元素

我们在使用列表的时候，可以通过val = lst[1]这种方式获取元素，那么底层是如何实现的呢？

static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{	
    //先看item是不是一个整型，显然这个item除了整型之外，也可以是切片
    if (PyIndex_Check(item)) {
        Py_ssize_t i;
        //这里检测i是否合法，因为Python的整型是没有限制的
        //但是列表的长度和容量都是由一个有具体类型的变量维护的，所以其个数肯定是有范围的
        //所以你输入一个lst[2 ** 100000]显然是不行的, 在Python中会报错IndexError: cannot fit 'int' into an index-sized integer
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        
        //设置异常
        if (i == -1 && PyErr_Occurred())
            return NULL;
        
        //如果i小于0, 那么加上列表的长度, 变成正数索引
        if (i < 0)
            i += PyList_GET_SIZE(self);
        //然后调用list_item
        return list_item(self, i);
    }
    else if (PySlice_Check(item)) {
    //......
    }    
    else {
        //......
    }
}


static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{	
    //检测索引i的合法性，如果i > 列表的长度, 那么会报出索引越界的错误。
    if (!valid_index(i, Py_SIZE(a))) {
        //如果索引为负数也会报出索引越界错误,因为上面已经对负数索引做了处理了,但如果负数索引加上长度之后还是个负数, 那么同样报错。
        //假设列表长度是5, 你的索引是-100, 加上长度之后是-95，结果还是个负数, 所以也会报错
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    //通过ob_item获取第i个元素
    Py_INCREF(a->ob_item[i]);
    //返回
    return a->ob_item[i];
}

显然获取元素的时候不光可以通过索引，还可以通过切片的方式。

static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
    if (PyIndex_Check(item)) {
        //.......
    }
    else if (PySlice_Check(item)) {
        /*
        start: 切片的起始位置
        end: 切片的结束位置
        step: 切片的步长
        slicelength: 获取元素个数,比如[1:5:2],显然slicelength就是2, 因为只能获取索引为1和3的元素
        cur: 底层数组中元素的索引
        i: 循环变量, 因为切片的话只能循环获取每一个元素, 比如[1:5:2], 需要循环两次。第一次循环, 上面的cur就是1, 第二次循环cur就是3
        */
        Py_ssize_t start, stop, step, slicelength, cur, i;
        //返回的结果
        PyObject* result;
        
        //下面代码中会有所体现
        PyObject* it;
        PyObject **src, **dest;
		
        //对切片item进行解包进行解包, 得到起始位置、结束位置、步长
        if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
            return NULL;
        }
        //计算出slicelength, 因为即便我们指定的切片是[1:3:5], 但如果列表只有3个元素, 所以slicelength也只能是1
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
                                            step);
		
        //如果slicelength为0, 那么不好意思, 表示没有元素可以获取, 因此直接返回一个空列表即可
        if (slicelength <= 0) {
            //PyList_New表示创建一个PyListObject, 里面的参数表示底层数组的长度
            //另外对于创建列表，Python底层只提供了PyList_New这一种Python/C API
            //当我们执行lst = [1, 2, 3]的时候就会执行PyList_New(3)
            return PyList_New(0);
        }
        //如果步长为1, 那么会调用list_slice,这个函数内部的逻辑很简单,首先接收一个PyListObject *和两个整型(ilow, ihigh)
        //然后在内部会创建一个PyListObject *np, 申请相应的底层数组，设置allocated
        //然后将参数列表中索引为ilow的元素到索引为ihigh的元素依次拷贝到np -> ob_item里面, 然后这是ob_size并返回
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        else {
            //走到这里说明步长不为1, 我们说result是一个PyListObject *, 底层数组没有存储在PyListObject中，而是通过ob_item发生关联
            //所以这一步是申请底层数组、设置容量的，容量就是这里的slicelength, 上面的list_slice中也调用了这一步
            result = list_new_prealloc(slicelength);
            if (!result) return NULL;
			
            //src是一个二级指针, 也就是self -> ob_item
            src = self->ob_item;
            //同理dest是result -> ob_item
            dest = ((PyListObject *)result)->ob_item;
            //进行循环, cur从start开始遍历, 每次加上step步长
            for (cur = start, i = 0; i < slicelength;
                 cur += (size_t)step, i++) {
                //it就是self -> ob_item中的元素
                it = src[cur];
                //增加指向的对象的引用计数
                Py_INCREF(it);
                //将其设置到dest中
                dest[i] = it;
            }
            //将大小设置为slicelength，说明通过切片创建新列表, 其长度和容量也是一致的
            Py_SIZE(result) = slicelength;
            //返回结果
            return result;
        }
    }
    else {
        //此时说明item不合法
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers or slices, not %.200s",
                     item->ob_type->tp_name);
        return NULL;
    }
}

我们发现这个和字符串类似啊，因为通过字符串也支持切片的方式获取。

随着源码的分析，我们也渐渐明朗Python的操作在底层是如何实现的了，真的一点不神秘，实现的逻辑非常简单。

设置元素

获取元素知道了，设置元素也不难了。

static int
list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
{	//在list_subscript的基础上多了一个value参数
    
    if (PyIndex_Check(item)) {
        //依旧是进行检测i是否合法
        Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return -1;
        //索引小于0，则加上列表的长度
        if (i < 0)
            i += PyList_GET_SIZE(self);
        //调用list_ass_item进行设置，我们之前见到了list_item，是用来基于索引获取的
        //这里的list_ass_item是基于索引进行元素设置的
        return list_ass_item(self, i, value);
    }
    else if (PySlice_Check(item)) {
    	//......
    }
}


static int
list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
{	
    //判断索引是否越界
    if (!valid_index(i, Py_SIZE(a))) {
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    //这里的list_ass_slice后面会说
    if (v == NULL)
        return list_ass_slice(a, i, i+1, v);
    //增加v指向对象的引用计数，因为指向它的指针被传到了列表中
    Py_INCREF(v);
    //将第i个元素设置成v
    Py_SETREF(a->ob_item[i], v);
    return 0;
}

通过索引设置元素，逻辑很容易，关键是通过切片设置元素会比较复杂。而复杂的原因就在于步长，我们通过Python来演示一下。

lst = [1, 2, 3, 4, 5, 6, 7, 8]

# 首先通过切片进行设置的话, 右值一定要是一个可迭代对象
lst[0: 3] = [11, 22, 33]
# 会将lst[0]设置为11, lst[1]设置为22, lst[2]设置为33
print(lst)  # [11, 22, 33, 4, 5, 6, 7, 8]


# 而且它们的长度是可以不相等的
# 这里表示将[0: 3]的元素设置为[1, 2], lst[0]设置成1, lst[1]设置成2
# 问题来了, lst[2]咋办? 由于右值中已经没有元素与之匹配了, 那么lst[2]就会被删掉
lst[0: 3] = [1, 2]
print(lst)  # [1, 2, 4, 5, 6, 7, 8]

# 所以我们如果想删除[0: 3]的元素, 那么只需要执行lst[0: 3] = []即可
# 因为[]里面没有元素能与之匹配, 所以lst中[0: 3]的元素由于匹配不到, 所以直接就没了
# 当然由于Python的动态特性, lst[0: 3] = []、lst[0: 3] = ()、lst[0: 3] = ""等等都是可以的
lst[0: 3] = ""
print(lst)  # [5, 6, 7, 8]
# 实际上我们del lst[0]的时候, 实际上就是执行了lst[0: 1] = []


# 当然如果右值元素多的话也是可以的
lst[0: 1] = [1, 2, 3, 4]
print(lst)  # [1, 2, 3, 4, 6, 7, 8]
# lst[0]匹配1很好理解, 但是此时左边已经结束了, 所以剩余的元素会依次插在后面


# 然后重点来了, 如果切片有步长的话, 那么两边一定要匹配
# 由于此时lst中有8个元素, lst[:: 2]会得到4个元素, 那么右边的可迭代对象的长度也是4
lst[:: 2] = ['a', 'b', 'c', 'd']
print(lst)  # ['a', 2, 'b', 4, 'c', 7, 'd']

# 但是，如果长度不一致
try:
    lst[:: 2] = ['a', 'b', 'c']
except Exception as e:
    # 显然会报错
    print(e)  # attempt to assign sequence of size 3 to extended slice of size 4

至于通过切片来设置元素，源码很长，这里就不分析了，总之核心如下：

• 如果步长为1: 那么会调用list_ass_slice。我们说: list_item是基于索引获取元素、list_slice是基于切片获取元素、list_ass_item是基于索引设置元素、list_ass_slice是基于切片设置元素。而list_ass_slice内部的代码逻辑也很长，但是核心并不难, 我们通过lst[a: b] = [v1, v2, v3, ...]这种方式就会走这里的list_ass_slice。
• 如果步长不为1，那么就是采用循环的方式逐个设置。

主要是考虑的情况比较多，但是核心逻辑并不复杂，有兴趣可以自己去深入了解一下。

insert插入元素

insert用来在指定的位置插入元素，我们知道它是一个时间复杂度为O(n)的一个操作，因为插入位置后面的所有元素都要向后移动。

int
PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{	
    //类型检查
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    //底层又调用ins1
    return ins1((PyListObject *)op, where, newitem);
}


static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{	
    /*参数self：PyListObject *
    参数where：索引
    参数v：插入的值，这是一个PyObject *指针，因为list里面存的都是指针
    */
    
    //i:后面for循环遍历用的，n则是当前列表的元素个数
    Py_ssize_t i, n = Py_SIZE(self);
    //指向指针数组的二级指针
    PyObject **items;
    //如果v是NULL，错误的内部调用
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    //列表的元素个数不可能无限增大，一般当你还没创建到PY_SSIZE_T_MAX个对象时
    //你内存就已经玩完了，但是python仍然做了检测，当达到这个PY_SSIZE_T_MAX时，会报出内存溢出错误
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
	
    //调整列表容量，既然要inert，那么就势必要多出一个元素
    //这个元素还没有设置进去，但是先把这个坑给留出来
    //当然如果容量够的话，是不会扩容的，只有当容量不够的时候才会扩容
    if (list_resize(self, n+1) < 0)
        return -1;
	
    //确定插入点
    if (where < 0) {
        //这里可以看到如果where小于0，那么我们就加上n，也就是当前列表的元素个数
        //比如有6个元素，那么我们where=-1，加上6，就是5，显然就是insert在最后一个索引的位置上 
        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;
    //然后不断遍历，把索引为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;
}

所以可以看到，Python插入数据是非常灵活的。不管你在什么位置插入，都是合法的。因为它会自己调整位置，在确定位置之后，会将当前位置以及之后的所有元素向后挪动一个位置，空出来的地方设置为插入的值。

pop弹出元素

pop默认是从尾部弹出元素的，因为如果不指定索引的话，默认是-1。当然我们也可以指定索引，弹出指定索引对应的元素。

static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
{	
    //弹出的对象的指针，因为弹出一个元素实际上是先用某个变量保存起来，然后再从列表中删掉
    PyObject *v;
    
    //下面代码中体现
    int status;
	
    //如果列表长度为0，显然没有元素可以弹, 因此会报错
    if (Py_SIZE(self) == 0) {
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    //索引小于0，那么加上列表的长度得到正数索引
    if (index < 0)
        index += Py_SIZE(self);
    //依旧是调用valid_index，判断是否越界。显然pop没有insert那么智能
    //insert的话，索引在加上列表长度之和还小于0，那么默认是在索引为0的地方插入
    //但是pop就不行了，pop的话会报出索引越界错误，同理索引大于等于列表长度，insert会等价于append,而pop同样报出索引越界错误
    if (!valid_index(index, Py_SIZE(self))) {
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
    //根据索引获取指定位置的元素
    v = self->ob_item[index];
    
    //这里同样是一个快分支，如果index是最后一个元素
    if (index == Py_SIZE(self) - 1) {
        //那么直接调用list_resize即可，我们说只要涉及元素的添加、删除都要执行list_resize
        //至于容量是否变化，就看是否满足newsize和allocated之间的关系,如果allocated//2 <= newsize <= allocated，那么容量就不变
        //list_resize中会将ob_size设置成newsize，也就是原来的ob_size减去1, 因为是在尾部删除的，所以只需要将ob_size设置为ob_size-1即可
        status = list_resize(self, Py_SIZE(self) - 1);
        //list_resize执行成功会返回0
        if (status >= 0)
            //直接将对象的指针返回
            return v; 
        else
            return NULL;
    }
    //否则说明不是快分支
    Py_INCREF(v);
    //这里调用了list_ass_slice, 这一步等价于self[index: index + 1] = []
    status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
    if (status < 0) {
        //设置失败，减少引用计数
        Py_DECREF(v);
        return NULL;
    }
    //返回指针
    return v;
}

所以pop本质上也是调用了list_ass_slice。

index查询元素的索引

index可以接收一个元素，返回该元素首次出现的索引。当然还可以额外指定一个start和end，表示查询的范围

static PyObject *
list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
                Py_ssize_t stop)
{
    Py_ssize_t i;
	
    //如果start小于0，加上长度。
    //还小于0，那么等于0
    if (start < 0) {
        start += Py_SIZE(self);
        if (start < 0)
            start = 0;
    }
    if (stop < 0) {
        //如果stop小于0，加上长度
        //还小于0，那么等于0
        stop += Py_SIZE(self);
        if (stop < 0)
            stop = 0;
    }
    //从start开始循环
    for (i = start; i < stop && i < Py_SIZE(self); i++) {
        //获取相应元素
        PyObject *obj = self->ob_item[i];
        //增加引用计数，因为有指针指向它
        Py_INCREF(obj);
        //进行比较PyObject_RichCompareBool是一个富比较，接收三个参数：元素1、元素2、操作(这里显然是Py_EQ)
        //相等返回1，不相等返回0
        int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        //比较完之后，减少引用计数
        Py_DECREF(obj);
        if (cmp > 0)
            //如果相等，返回其索引
            return PyLong_FromSsize_t(i);
        else if (cmp < 0)
            return NULL;
    }
    //循环走完一圈，发现都没有相等的，那么报错，提示元素不再列表中
    PyErr_Format(PyExc_ValueError, "%R is not in list", value);
    return NULL;
}

所以lst.index是一个时间复杂度为O(n)的操作，因为它在底层要循环整个列表，如果运气好，可以第一个元素就是，运气不好可能就好循环整个列表了。同理后面要说的if value in lst这种方式也是一样的，因为都要循环整个列表，只不过后者返回的是一个布尔值。

count查询元素出现的次数

static PyObject *
list_count(PyListObject *self, PyObject *value)
{	
    //初始为0
    Py_ssize_t count = 0;
    Py_ssize_t i;
	
    //遍历每一个元素
    for (i = 0; i < Py_SIZE(self); i++) {
        //获取元素
        PyObject *obj = self->ob_item[i];
        //如果相等，那么count自增1，继续下一次循环
        //注意这里的相等，判断的是什么呢？显然是对象的地址，如果地址一样，那么肯定指向同一个对象，所以一定相等。
        if (obj == value) {
           count++;
           continue;
        }
        Py_INCREF(obj);
        //走到这里说明地址不一样，但是地址不一样只能说明a is b不成立，但并不代表a == b不成立，所以调用PyObject_RichCompareBool进行判断
        int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        Py_DECREF(obj);
        //大于0，说明相等，count++
        if (cmp > 0)
            count++;
        else if (cmp < 0)
            return NULL;
    }
    //返回count
    return PyLong_FromSsize_t(count);
}

count毫无疑问，无论在什么情况下，它都是一个时间复杂度为O(n)的操作，因为列表必须要从头遍历到尾。

remove根据元素的值删除元素

除了根据索引删除元素之外，也可以元素指向的对象维护的值删除元素，删除第一个出现元素。

static PyObject *
list_remove(PyListObject *self, PyObject *value)
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        //从头开始遍历，获取元素
        PyObject *obj = self->ob_item[i];
        Py_INCREF(obj);
        //比较是否相等
        int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
        Py_DECREF(obj);
        //如果相等
        if (cmp > 0) {
            //调用list_ass_slice删除元素
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                //返回None
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    //否则说明元素不在列表中
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

reverse翻转列表

static PyObject *
list_reverse_impl(PyListObject *self)
{	
    //如果列表长度不大于1的话, 那么直接返回其本身即可
    if (Py_SIZE(self) > 1)
        //大于1的话，执行reverse_slice, 传递了两个参数
        //第一个参数self -> ob_item显然是底层数组首元素的地址
        //而第二个参数self->ob_item + Py_SIZE(self)则是底层数组中索引为ob_size的元素的地址
        //但是很明显能访问的最大索引应该是ob_size - 1才对, 别急我们继续往下看, 看一下reverse_slice函数的实现
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
}


static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);
	
    //我们看到又执行了一次--hi,将hi移动到了ob_size - 1位置，也就是说此时二级指针hi保存的还是索引为ob_size - 1的元素的值
    //所以个人觉得有点纳闷, 直接reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self) - 1);不行吗
    --hi;
    //当lo小于hi的时候
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        //上面三步就等价于 *lo, *hi = *hi, *lo, 但是C不支持这么写
        //所以我们看到就是将索引为0的元素和索引为ob_size-1的元素进行了交换，前后两个指针继续靠近,指向的元素继续交换，知道两个指针相遇
        ++lo;
        --hi;
    }
}

所以到现在，你还认为Python中的列表神秘吗？虽然我们不可能写出一个Python解释器，但是底层的一些思想其实并没有那么难，作为一名程序猿很容易想的到。

两个列表相加

static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
    Py_ssize_t size;  //相加之后的列表长度
    Py_ssize_t i; //循环变量
    //两个二级指针，指向ob_item
    PyObject **src, **dest;
    //新的列表
    PyListObject *np;
    //类型检测
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                  "can only concatenate list (not \"%.200s\") to list",
                  bb->ob_type->tp_name);
        return NULL;
    }
#define b ((PyListObject *)bb)
    //判断长度是否溢出
    if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))
        return PyErr_NoMemory();
    //计算新列表的长度
    size = Py_SIZE(a) + Py_SIZE(b);
    //设置np -> ob_item指向的底层数组
    np = (PyListObject *) list_new_prealloc(size);
    if (np == NULL) {
        return NULL;
    }
    //获取a -> ob_item和np -> ob_item
    src = a->ob_item;
    dest = np->ob_item;
    //将元素依次拷贝过去, 增加引用计数
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    //获取b->ob_item
    //获取np->ob_item + Py_SIZE(a), 要从Py_SIZE(a)的位置开始设置, 否则就把之前的元素覆盖掉了
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    //将元素依次拷贝过去, 增加引用计数
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    //设置ob_size
    Py_SIZE(np) = size;
    //返回np
    return (PyObject *)np;
#undef b
}

判断元素是否在列表中

对于一个序列来说，可以使用in操作符，等价于调用其__contains__魔法方法。

static int
list_contains(PyListObject *a, PyObject *el)
{
    PyObject *item;
    Py_ssize_t i;
    int cmp;
	//挨个循环，比较是否相等。存在cmp会等于1，cmp == 0 && i < Py_SIZE(a)不满足，直接返回
    //不相等则为0, 会一直比完列表中所有的元素
    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
        item = PyList_GET_ITEM(a, i);
        Py_INCREF(item);
        cmp = PyObject_RichCompareBool(el, item, Py_EQ);
        Py_DECREF(item);
    }
    return cmp;
}

真的非常简单，没有什么好说的。

列表的深浅拷贝

列表的深浅拷贝也是初学者容易犯的错误之一，我们看一个Python的例子。

lst = [[]]

# 默认是浅拷贝, 这个过程会创建一个新列表, 会将里面的指针拷贝一份
# 但是指针指向的内存并没有拷贝
lst_cp = lst.copy()

# 两个对象的地址是一样的
print(id(lst[0]), id(lst_cp[0]))  # 2207105155392 2207105155392

# 操作lst[0], 会改变lst_cp[0]
lst[0].append(123)
print(lst, lst_cp)  # [[123]] [[123]]

# 操作lst_cp[0], 会改变lst[0]
lst_cp[0].append(456)
print(lst, lst_cp)  # [[123, 456]] [[123, 456]]

我们通过索引或者切片也是一样的道理

lst = [[], 1, 2, 3]
val = lst[0]
lst_cp = lst[0: 1]

print(lst[0] is val is lst_cp[0])  # True
# 此外，lst[:]完全等价于lst.copy()

之所以会有这样现象，是因为我们说过Python中变量、容器里面的元素都是一个泛型指针PyObject *，在传递的时候会传递指针， 但是在操作的时候会操作指针指向的内存。

所以lst.copy()就是创建了一个新列表，然后把元素拷贝了过去，并且这里的元素是指针。因为只是拷贝指针，没有拷贝指针指向的对象(内存)，所以它们的地址都是一样的，因为指向的是同一个对象。

但如果我们就想在拷贝指针的同时也拷贝指针指向的对象呢？答案是使用一个叫copy的模块。

import copy

lst = [[]]
# 此时拷贝的时候，就会把指针指向的对象也给拷贝一份
lst_cp1 = copy.deepcopy(lst)
lst_cp2 = lst[:]

lst_cp2[0].append(123)
print(lst)  # [[123]]
print(lst_cp1)  # [[]]

# lst[:]这种方式也是浅拷贝, 所以修改lst_cp2[0], 也会影响lst[0]
# 但是没有影响lst_cp1[0], 证明它们是相互独立的, 因为指向的是不同的对象

浅拷贝示意图如下：

里面的两个底层数组的元素是一样的

深拷贝示意图如下：

里面的两个底层数组的元素是不一样的

注意：copy.deepcopy虽然在拷贝指针的同时会将指针指向的对象也拷贝一份，但这仅仅是针对于可变对象，对于不可变对象是不会拷贝的。

import copy

lst = [[], "古明地觉"]
lst_cp = copy.deepcopy(lst)

print(lst[0] is lst_cp[0])  # False
print(lst[1] is lst_cp[1])  # True

为什么会这样，其实原因很简单。因为不可变对象是不支持本地修改的，你若想修改只能指向新的对象，但是对其它的变量则没有影响，其它变量该指向谁就还指向谁。因为a = b只是将对象的指针拷贝一份给a，然后a和b都指向了同一个对象，至于a和b本身则是没有任何关系的。如果此时b指向了新的对象，是完全不会影响a的，a还是指向原来的对象。所以如果一个指针指向的对象不支持本地修改，那么深拷贝不会拷贝对象本身，因为指向的是不可变对象，所以不会有修改一个影响另一个的情况出现。

关于列表还有一些陷阱：

lst = [[]] * 5
lst[0].append(1)
print(lst)  # [[1], [1], [1], [1], [1]]
# 列表乘上一个n，等于把列表里面的元素重复n次
# 注意: 类似于lst = [1, 2, 3], 虽然我们写的是整数，但是它存储的并不是整数，而是其指针
# 所以会把指针重复5次, 因此列表里面5个指针都指向了同一个列表


# 这种方式创建的话，里面的元素都指向了不同的列表
lst = [[], [], [], [], []]
lst[0].append(1)
print(lst)  # [[1], [], [], [], []]


# 再比如字典，在后续系列中会说
d = dict.fromkeys([1, 2, 3, 4], [])
print(d)  # {1: [], 2: [], 3: [], 4: []}
d[1].append(123)
print(d)  # {1: [123], 2: [123], 3: [123], 4: [123]}
# 它们都指向了同一个列表，因此这种陷阱在工作中要注意, 因为一不小心就会出现大问题

创建PyListObject

我们说创建一个列表，Python底层只提供了唯一一个Python/C API，也就是PyList_New。这个函数接收一个size参数，从而允许我们在创建一个PyListObject对象时指定底层数组的长度。

PyObject *
PyList_New(Py_ssize_t size)
{	
    //声明一个PyListObject *对象
    PyListObject *op;
#ifdef SHOW_ALLOC_COUNT
    static int initialized = 0;
    if (!initialized) {
        Py_AtExit(show_alloc);
        initialized = 1;
    }
#endif
	
    //如果size小于0，直接抛异常
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    //缓存池是否可用，如果可用
    if (numfree) {
        //将缓存池内对象个数减1
        numfree--;
        //从缓存池中获取
        op = free_list[numfree];
        //设置引用计数
        _Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
        count_reuse++;
#endif
    } else {
        //不可用的时候，申请内存
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
#ifdef SHOW_ALLOC_COUNT
        count_alloc++;
#endif
    }
    //如果size小于等于0，ob_item设置为NULL
    if (size <= 0)
        op->ob_item = NULL;
    else {
        //否则的话，创建一个指定容量的指针数组，然后让ob_item指向它
        //所以是先创建PyListObject对象, 然后创建底层数组, 最后通过ob_item建立联系
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    //设置ob_size和allocated，然后返回op
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

我们注意到源码里面有一个缓冲池，是的，创建PyListObject对象时，会先检测缓冲池free_lists里面是否有可用的对象，有的话直接拿来用，否则通过malloc在系统堆上申请。缓冲池中最多维护80个PyListObject对象。

/* Empty list reuse scheme to save calls to malloc and free */
#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];

根据之前的经验我们知道，既然能从缓存池中获取，那么在执行析构函数的时候也要把列表放到缓存池里面。

static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_SAFE_BEGIN(op)
    if (op->ob_item != NULL) {
        i = Py_SIZE(op);
        //将底层数组中每个指针指向的对象的引用计数都减去1
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
      	//然后释放底层数组所占的内存
        PyMem_FREE(op->ob_item);
    }
    //判断缓冲池里面PyListObject对象的个数，如果没满，就添加到缓存池
    //注意：我们看到执行到这一步的时候, 底层数组已经被释放掉了
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        //否则的话再释放掉PyListObject对象所占的内存
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}

我们知道在创建一个新的PyListObject对象时，实际上是分为两步的，先创建PyListObject对象，然后创建底层数组，最后让PyListObject对象中的ob_item成员指向这个底层数组。同理，在销毁一个PyListObject对象时，先销毁ob_item维护的底层数组，然后再释放PyListObject对象自身(如果缓存池已满的情况下)。

现在可以很清晰地明白了，原本空荡荡的缓存池其实是被已经死去的PyListObject对象填充了，在以后创建新的PyListObject对象时，Python会首先唤醒这些死去的PyListObject对象，给它们一个洗心革面、重新做人的机会。但需要注意，这里缓存的仅仅是PyListObject对象，对于底层数组，其ob_item已经不再指向了。从list_dealloc中我们看到，PyListObject对象在放进缓存池之前，ob_item指向的数组就已经被释放掉了，同时数组中指针指向的对象的引用计数会减1。所以最终数组中这些指针指向的对象也大难临头各自飞了，或生存、或毁灭，总之此时和PyListObject之间已经没有任何联系了。但是为什么要这么做呢？为什么不连底层数组也一起维护呢？可以想一下，如果继续维护的话，数组中指针指向的对象永远不会被释放，那么很可能会产生悬空指针的问题，所以这些指针指向的对象所占的空间必须交还给系统(前提是没有其它指针指向了)。

但是实际上，是可以将PyListObject对象维护的底层数组进行保留的，即只将数组中指针指向的对象的引用计数减1，然后将数组中的指针都设置为NULL，不再指向之前的对象了，但是并不释放底层数组本身所占用的内存空间。因此这样一来，释放的内存不会交给系统堆，那么再次分配的时候，速度会快很多。但是这样带来一个问题，就是这些内存没人用也会一直占着，并且只能供PyListObject对象的ob_item指向的底层数组使用，因此Python还是为避免消耗过多内存，采取将底层数组的内存交换给了系统堆这样的做法，在时间和空间上选择了空间。

元组的底层结构–PyTupleObject

因为元组比较简单，和列表比较相似，所以就放在一起介绍了。我们知道元组，就相当于不支持元素添加、修改、删除等操作的列表。

元组的实现机制非常简单，可以看做是在列表的基础上删除了增删改等操作。既然如此，那要元组有什么用呢？毕竟元组的功能只是列表的子集。元组存在的最大一个特点就是，它可以作为字典的key、以及可以作为集合的元素。因为字典和集合存储数据的原理是哈希表，字典和集合我们后续章节会说。对于列表这样的可变对象来说是可以动态改变的，而哈希值是一开始就计算好的，显然如果支持动态修改的话，那么哈希值肯定会变，这是不允许的。所以如果我们希望字典的key是一个序列，显然元组再适合不过了。

从tuple的特点也能看出：tuple的底层是一个变长对象，但同时也是一个不可变对象。

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];
} PyTupleObject;

可以看到，对于不可变对象来说，它底层结构体定义也非常简单。一个引用计数、一个类型、一个指针数组。这里的1可以想象成n，我们在PyLongObject中说过。

并且我们发现不像列表，元组没有allocated，这是因为它是不可变的，不支持resize操作。至于维护的值，同样是指针组成的数组，数组里面的每一个指针都指向了具体的值。

PyTupleObject的创建

正如列表一样，Python创建PyTupleObject也提供了类似的初始化方法。

PyObject *
PyTuple_New(Py_ssize_t size)
{	
    //PyTupleObject指针
    PyTupleObject *op;
    Py_ssize_t i;
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
#if PyTuple_MAXSAVESIZE > 0
    //元组同样有缓存池
    if (size == 0 && free_list[0]) {
        op = free_list[0];
        Py_INCREF(op);
#ifdef COUNT_ALLOCS
        tuple_zero_allocs++;
#endif  
        //如果长度为0，那么直接返回
        return (PyObject *) op;
    }
    if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
        //从缓存池中获取
        free_list[size] = (PyTupleObject *) op->ob_item[0];
        numfree[size]--;
#ifdef COUNT_ALLOCS
        fast_tuple_allocs++;
#endif
        /* Inline PyObject_InitVar */
#ifdef Py_TRACE_REFS
        //设置ob_size，和ob_type
        Py_SIZE(op) = size;
        Py_TYPE(op) = &PyTuple_Type;
#endif
        //引用计数初始化为1
        _Py_NewReference((PyObject *)op);
    }
    else
#endif
    {
        /* 元组的元素个数同样有限制，但我们说这个限制一般达不到 */
        if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - sizeof(PyTupleObject) -
                    sizeof(PyObject *)) / sizeof(PyObject *)) {
            return PyErr_NoMemory();
        }
        //申请空间
        op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
        if (op == NULL)
            return NULL;
    }
    for (i=0; i < size; i++)
        op->ob_item[i] = NULL;
#if PyTuple_MAXSAVESIZE > 0
    if (size == 0) {
        free_list[0] = op;
        ++numfree[0];
        Py_INCREF(op);          /* extra INCREF so that this is never freed */
    }
#endif
#ifdef SHOW_TRACK_COUNT
    count_tracked++;
#endif
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

和PyListObject初始化类似，同样需要做一些类型检测，内存是否溢出等等。

当然有了列表的经验，元组的一些底层操作我们就不分析了，它是列表的子集。

静态资源缓存

列表和元组两者在通过索引查找元素的时候是一致的，但是元组除了能作为字典的key之外，还有一个特点，就是分配的速度比较快。一方面是因为由于其不可变性，使得在编译的时候就确定了，另一方面就是它还具有静态资源缓存的作用。

对于一些静态变量，比如元组，如果它不被使用并且占用空间不大时，Python 会暂时缓存这部分内存。这样，下次我们再创建同样大小的元组时，Python 就可以不用再向操作系统发出请求，去寻找内存，而是可以直接分配之前缓存的内存空间，这样就能大大加快程序的运行速度。你可以理解为PyTupleObject对象在被析构时，不仅对象本身没有被回收，连底层的指针数组也被缓存起来了。

from timeit import timeit


t1 = timeit(stmt="x1 = [1, 2, 3, 4, 5]", number=1000000)
t2 = timeit(stmt="x2 = (1, 2, 3, 4, 5)", number=1000000)

print(round(t1, 2))  # 0.05
print(round(t2, 2))  # 0.01

可以看到用时，元组只是列表的五分之一。这便是元组的另一个优势，可以将资源缓存起来。