楔子
上一篇文章我们介绍了列表作为序列型对象支持的方法，但列表还有很多的自定义方法。作为一名优秀的 Python 工程师，我们必须要知道这些方法的实现过程，以及相应的时间复杂度。
实例对象能够调用的方法都定义在类型对象中，类型对象无一例外都是 PyTypeObject 结构体实例，该结构体有一个 tp_methods 字段，负责维护实例对象能够调用的方法。
// Include/pytypedefs.h
typedef struct _typeobject PyTypeObject;
// Include/cpython/object.h
struct _typeobject {
// ...
struct PyMethodDef *tp_methods;
// ...
}
/* tp_methods 指向 PyMethodDef 结构体类型的数组
* 所以一个 PyMethodDef 结构体实例，就是 Python 实例对象能够调用的一个方法
*/
// Include/methodobject.h
struct PyMethodDef {
// 暴露给 Python 的方法名
const char *ml_name;
// 承载了具体逻辑的 C 函数
PyCFunction ml_meth;
// 指示函数的调用方式和传递参数的方式，比如
/* METH_NOARGS: 表示函数不接收任何参数
* METH_O: 函数只接收一个参数
* METH_VARARGS: 函数支持以元组的形式接收多个位置参数
* METH_KEYWORDS: 函数支持关键字参数
* METH_CLASS: 函数是一个类方法，等价于 Python 里的 @classmethod
* METH_STATIC: 函数是一个静态方法，即 @staticmethod
* METH_FASTCALL: 函数使用优化的快速调用协议，Python 3.7 及以上版本可用
传递参数时使用 C 数组，而不是 Python 元组
* METH_COEXIST: 如果希望存在两个同名函数，但类和实例分别调用不同的函数
那么便可以指定 METH_COEXIST
*/
int ml_flags;
// 函数的 docstring
const char *ml_doc;
};而 list 在底层对应 PyList_Type，它的 tp_methods 字段被赋值为 list_method。
里面定义了列表可以调用的方法，我们随便看一个，比如 append。
// Objects/clinic/listobject.c.h
#define LIST_APPEND_METHODDEF \
{"append", (PyCFunction)list_append, \
METH_O, list_append__doc__},
// 列表调用时使用的方法名为 append
// 内部会执行 list_append 函数
// 只接收一个参数相信当你以后想查看某个对象的方法的底层实现时，已经知道该怎么定位了，下面我们就来看看这些方法的实现过程。
append：在尾部追加元素
append 方法在底层对应 list_append，我们上面已经看到了，那么它的实现细节是怎样的呢。
// Objects/listobject.c
static PyObject *
list_append(PyListObject *self, PyObject *object)
{
// 调用 _PyList_AppendTakeRef 添加元素
if (_PyList_AppendTakeRef(self, Py_NewRef(object)) < 0) {
return NULL;
}
// 该函数返回 None
Py_RETURN_NONE;
}
// Include/internal/pycore_list.h
static inline int
_PyList_AppendTakeRef(PyListObject *self, PyObject *newitem)
{
assert(self != NULL && newitem != NULL);
assert(PyList_Check(self));
// 获取列表的长度
Py_ssize_t len = PyList_GET_SIZE(self);
// 获取列表的容量，即底层数组的长度
Py_ssize_t allocated = self->allocated;
assert((size_t)len + 1 < PY_SSIZE_T_MAX);
// 如果长度没有达到容量
if (allocated > len) {
// 那么将 newitem 设置在 ob_item 中索引为 len 的位置
PyList_SET_ITEM(self, len, newitem);
// 将列表的 ob_size 加 1
Py_SET_SIZE(self, len + 1);
return 0;
}
// 如果长度达到容量了，那么会调用下面这个函数
return _PyList_AppendTakeRefListResize(self, newitem);
}
// Objects/listobject.c
int
_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)
{
Py_ssize_t len = PyList_GET_SIZE(self);
assert(self->allocated == -1 || self->allocated == len);
// 逻辑是类似的，但这里会多一步扩容操作
if (list_resize(self, len + 1) < 0) {
Py_DECREF(newitem);
return -1;
}
PyList_SET_ITEM(self, len, newitem);
return 0;
}所谓往尾部追加元素，本质上就是将元素设置在索引为 len 的位置。
insert：在任意位置插入元素
接下来是列表的 insert 方法。
// Objects/clinic/listobject.c.h
#define LIST_INSERT_METHODDEF \
{"insert", _PyCFunction_CAST(list_insert), \
METH_FASTCALL, list_insert__doc__},它由 list_insert 函数负责实现。
// Objects/listobject.c
static PyObject *
list_insert(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
// 函数返回值，但只会返回 None
PyObject *return_value = NULL;
// 插入的位置
Py_ssize_t index;
// 插入的元素
PyObject *object;
// insert 方法精确接收两个参数
if (!_PyArg_CheckPositional("insert", nargs, 2, 2)) {
goto exit;
}
{
// 参数 args 是一个元组，里面包含了插入位置和元素
Py_ssize_t ival = -1;
// 插入位置，对象必须实现 __index__
PyObject *iobj = _PyNumber_Index(args[0]);
if (iobj != NULL) {
// 转成 Py_ssize_t
ival = PyLong_AsSsize_t(iobj);
Py_DECREF(iobj);
}
if (ival == -1 && PyErr_Occurred()) {
goto exit;
}
// 赋值给 index
index = ival;
}
// 拿到待插入的元素
object = args[1];
// 调用 list_insert_impl 执行元素插入逻辑
return_value = list_insert_impl(self, index, object);
exit:
// 虽然这里返回了 return_value，但我们知道 insert 方法是没有返回值的
// 或者说返回值为 None，所以上面的 list_insert_impl 一定返回了 None
return return_value;
}
static PyObject *
list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
{
// 调用 ins1 插入元素，插入成功之后返回 None
if (ins1(self, index, object) == 0)
Py_RETURN_NONE;
return NULL;
}
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
// 初始化循环变量 i
// n 为列表长度
Py_ssize_t i, n = Py_SIZE(self);
// 指向 ob_item 数组的首元素
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
assert((size_t)n + 1 < PY_SSIZE_T_MAX);
// 只要涉及到元素个数的改变，比如添加和删除元素
// 都会先调用 list_resize，在里面检测一下容量
// 比如这里，如果发现 (容量 >= n + 1) && (容量 / 2 <= n + 1)
// 那么说明容量目前是合理的，不需要做任何的扩容或缩容操作（如果条件不满足则需要）
// 然后将列表的 ob_size 修改为 n + 1，直接返回
if (list_resize(self, n+1) < 0)
return -1;
// 判断插入位置，如果 where 小于 0，那么加上列表长度
if (where < 0) {
where += n;
// 加上列表长度之后如果还小于 0，那么让其等于 0
if (where < 0)
where = 0;
}
// 如果插入位置大于列表长度 n，那么让其等于 n
// 此时相当于 append
if (where > n)
where = n;
items = self->ob_item;
// 将 where 以及之后的元素依次向右移动一个位置
for (i = n; --i >= where; )
items[i+1] = items[i];
// 将待插入元素 v 的引用计数加 1，并设置在底层数组中索引为 where 的位置
items[where] = Py_NewRef(v);
return 0;
}以上就是 insert 函数的底层逻辑，列表在插入数据的时候是非常灵活的，不管你在什么位置插入，都是合法的。它会自己调整，在确定待插入位置 where 之后，会将 where 以及之后的所有元素都向后挪动一个位置，空出来的地方设置为待插入的值。
另外我们看到 append 和 insert 其实非常像，都是基于索引设置元素。只不过对于 append 来说，索引就是列表长度，而对于 insert 来说，索引是由外界指定的，但函数内部会进行边界调整。
并且由于 insert 会涉及元素的移动，所以它的时间复杂度是 O(n)，而 append 则不会，所以它的时间复杂度是 O(1)。当然在极端情况下（发生扩容），append 也会退化成 O(n)，只不过这个过程不会频繁发生，所以 append 的复杂度仍然是 O(1) 的。
pop：从尾部弹出一个元素
pop 默认会从尾部弹出一个元素，当然我们也可以指定索引，弹出指定索引对应的元素。如果不指定索引，那么默认是 -1。
// Objects/clinic/listobject.c.h
#define LIST_POP_METHODDEF \
{"pop", _PyCFunction_CAST(list_pop), \
METH_FASTCALL, list_pop__doc__},它由 list_pop 函数负责实现。
// Objects/clinic/listobject.c.h
static PyObject *
list_pop(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
// 返回值
PyObject *return_value = NULL;
Py_ssize_t index = -1;
// pop 接收 0 ~ 1 个参数
if (!_PyArg_CheckPositional("pop", nargs, 0, 1)) {
goto exit;
}
// 如果参数个数小于 1，说白了就是没有传参，直接跳转到 skip_optional 标签
if (nargs < 1) {
goto skip_optional;
}
{
// 如果传参了，那么拿到指定的索引
Py_ssize_t ival = -1;
PyObject *iobj = _PyNumber_Index(args[0]);
if (iobj != NULL) {
ival = PyLong_AsSsize_t(iobj);
Py_DECREF(iobj);
}
if (ival == -1 && PyErr_Occurred()) {
goto exit;
}
index = ival;
}
skip_optional:
// 将列表和 index 作为参数传进去，如果不指定索引，那么 index 默认为 -1
return_value = list_pop_impl(self, index);
exit:
// 返回弹出的元素
return return_value;
}
// Objects/listobject.c
static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
{
PyObject *v;
int status;
// 如果列表为空，那么抛出 IndexError: pop from empty list
if (Py_SIZE(self) == 0) {
/* Special-case most common failure cause */
PyErr_SetString(PyExc_IndexError, "pop from empty list");
return NULL;
}
// 如果 index 小于 0，那么加上列表长度
if (index < 0)
index += Py_SIZE(self);
// 检测索引是否合法，如果索引小于 0 或大于等于列表长度
// 那么抛出 IndexError: pop index out of range
if (!valid_index(index, Py_SIZE(self))) {
PyErr_SetString(PyExc_IndexError, "pop index out of range");
return NULL;
}
// 获取 ob_item 数组
PyObject **items = self->ob_item;
// 拿到索引为 index 的元素，这也是一会儿要返回的元素
v = items[index];
// pop 之后，列表的长度（ob_size）要减去 1
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
// 如果减 1 之后长度为 0，说明列表没有元素了
if (size_after_pop == 0) {
// 增加 v 的引用计数
Py_INCREF(v);
// 将列表清空掉，注意这里的清空不仅仅是将元素清空，因为列表已经为空了
// _list_clear 还会将列表中每个元素指向的对象的引用计数减 1
// 并将 ob_item 设置为 NULL，将 ob_size 和 allocated 设置为 0
// 等于让列表回归到初始状态，因为 Python 认为当列表为空时，
// 你可能已经不用这个列表了，因此不会再让它占用额外内存
status = _list_clear(self);
}
else {
// 否则检测弹出的是否是最后一个元素
// 如果不是，那么要将 index 之后的元素依次向前移动一个位置
if ((size_after_pop - index) > 0) {
memmove(&items[index], &items[index+1],
(size_after_pop - index) * sizeof(PyObject *));
}
// 检测容量的大小是否合理，如果合理，则不做任何操作
// 直接将 ob_size 设置为 size_after_pop，然后返回即可
status = list_resize(self, size_after_pop);
// 可能有人好奇为什么这里没有增加引用计数呢？
// 首先元素从列表中弹出时，应该减少引用计数，但它又返回了，所以还要增加引用计数
// 因此两个操作相互抵消，不需要操作引用计数。但问题来了，为什么上面要执行加 1 操作呢
// 很简单，因为列表为空时会调用 _list_clear，将引用计数减 1，所以在调用之前要先加 1
}
// status 表示 list_resize 的执行结果
// 在 C 中一般约定，执行成功返回 0，失败返回 -1
if (status >= 0) {
// 返回弹出的对象
return v;
}
else {
// list resize failed, need to restore
memmove(&items[index+1], &items[index],
(size_after_pop - index)* sizeof(PyObject *));
items[index] = v;
return NULL;
}
}在 3.8 的时候，pop 弹出元素是这么做的。
list_ass_slice(self, index, index+1, (PyObject *)NULL等价于 self[index: index + 1] = []，但在 3.12 的时候，调用了 C 标准库的 memmove 函数，将 index + 1 以及之后的元素拷贝到 index 的位置。
index：查询元素首次出现的位置
index 方法可以接收一个元素，然后返回该元素首次出现的位置。当然还可以额外指定一个 start 和 end，表示查询的范围。
// Objects/clinic/listobject.c.h
#define LIST_INDEX_METHODDEF \
{"index", _PyCFunction_CAST(list_index), \
METH_FASTCALL, list_index__doc__},它由 list_index 负责实现。
// Objects/clinic/listobject.c.h
static PyObject *
list_index(PyListObject *self, PyObject *const *args, Py_ssize_t nargs)
{
PyObject *return_value = NULL;
PyObject *value;
Py_ssize_t start = 0;
Py_ssize_t stop = PY_SSIZE_T_MAX;
// index 方法接收 1 ~ 3 个参数
if (!_PyArg_CheckPositional("index", nargs, 1, 3)) {
goto exit;
}
// args[0] 表示查找的元素
value = args[0];
if (nargs < 2) {
goto skip_optional;
}
// args[1] 表示查找的起始位置
if (!_PyEval_SliceIndexNotNone(args[1], &start)) {
goto exit;
}
if (nargs < 3) {
goto skip_optional;
}
// args[2] 表示查找的结束位置
if (!_PyEval_SliceIndexNotNone(args[2], &stop)) {
goto exit;
}
skip_optional:
// 调用 list_index_impl 查找元素
return_value = list_index_impl(self, value, start, stop);
exit:
// 返回
return return_value;
}
// Objects/listobject.c
static PyObject *
list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
Py_ssize_t stop)
{
Py_ssize_t i;
// 如果 start 小于 0，那么加上列表长度
if (start < 0) {
start += Py_SIZE(self);
// 如果相加之后还小于 0，那么等于 0
if (start < 0)
start = 0;
}
// 如果结束位置小于 0，那么加上列表长度，所以它们都支持负数索引
if (stop < 0) {
stop += Py_SIZE(self);
// 如果相加之后还小于 0，那么等于 0
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);
// 然后进行比较，这个函数我们之前说过
// 它会先比较地址是否相同，如果地址相同，那么直接判定为相等
// 如果地址不同，那么比较值是否相等
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
// 相等返回 1，不相等返回 0，比较失败返回 -1
// 如果 cmp 大于 0，表示两者相等，返回索引
if (cmp > 0)
return PyLong_FromSsize_t(i);
else if (cmp < 0)
return NULL;
}
// 到这里说明元素不存在，那么抛出 ValueError: x is not in list
PyErr_Format(PyExc_ValueError, "%R is not in list", value);
return NULL;
}所以列表 index 方法的时间复杂度为 O(n)，因为它在底层要循环整个列表，如果运气好，可能第一个元素就是；运气不好，就只能循环整个列表了。
然后需要注意的是，在比较的时候，会先判断地址是否相同，然后再比较值是否相等。
class A:
def __eq__(self, other):
return False
a = A()
data = [a]
print(a == data[0]) # False
print(data.index(a)) # 0a 和 data[0] 指向的对象不相等，但 data.index(a) 却返回了相应的索引，因为两者保存的地址是相同的。
同理 if v in data 这种也是类似的，先比较地址，地址不同再比较维护的值。
count：查询元素出现的次数
列表有一个 count 方法，可以计算出某个元素出现的次数。
// Objects/clinic/listobject.c.h
#define LIST_COUNT_METHODDEF \
{"count", (PyCFunction)list_count, \
METH_O, list_count__doc__},它由 list_count 函数负责实现。
// Objects/listobject.c
static PyObject *
list_count(PyListObject *self, PyObject *value)
{
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 是否成立）
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
if (cmp > 0)
count++;
else if (cmp < 0)
return NULL;
}
// 返回元素出现的次数
return PyLong_FromSsize_t(count);
}毫无疑问，count 方法无论在什么情况下，它都是一个时间复杂度为 O(n) 的操作，因为列表必须要从头遍历到尾。
但还是要注意里面判断相等的方式，因为变量只是一个指针，所以 C 的 == 相当于 Python 的 is，但 Python 的 == 则对应 PyObject_RichCompare 函数。而源码里面在比较的时候先调用 ==，所以会先判断两者是不是同一个对象。
class A:
def __eq__(self, other):
return False
a = A()
data = [a, a, a]
print(data[0] == a) # False
print(data[1] == a) # False
print(data[2] == a) # False
print(data.count(a)) # 3我们看到列表里的三个元素和 a 都不相等，但计算数量的时候，结果是 3。原因就是比较的时候是先比较地址，如果地址一样，那么认为元素相同。
当然 PyObject_RichCompareBool 函数里面已经包含了比较地址的逻辑，该函数会先比较地址是否一样，如果一样则认为相等，不一样再比较对象维护的值是否相等。但在 count 方法里面，将比较地址的逻辑又单独拿了出来，可以理解为快分支。当然即遍没有也无所谓，因为在函数 PyObject_RichCompareBool 里面还是会先对地址进行比较。
remove：删除指定元素
除了根据索引删除元素之外，也可以根据值来删除元素，会删除第一个出现的元素。
// Objects/clinic/listobject.c.h
#define LIST_REMOVE_METHODDEF \
{"remove", (PyCFunction)list_remove, \
METH_O, list_remove__doc__},它由 list_remove 函数实现。
// Objects/listobject.c
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
// 等价于 self[i: i + 1] = []
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
else if (cmp < 0)
return NULL;
}
// 否则说明元素不在列表中，抛出 ValueError: list.remove(x): x not in list
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}以上就是 remove 函数的底层实现，说白了就是一层 for 循环，依次比较列表的每个元素和待删除元素是否相等。如果出现了相等的元素，则删除，然后直接返回，因为只删除一个；但如果整个循环遍历结束也没有发现满足条件的元素，那么报错，待删除元素不存在。
所以背后的逻辑并没有我们想象中的那么神秘。
reverse：翻转列表
如果是你的话，你会怎么对列表进行翻转呢？显然是采用双指针，头指针指向列表的第一个元素，尾指针指向列表的最后一个元素，然后两两交换。
交换完毕之后，头指针后移一位、尾指针前移一位，继续交换。当两个指针相遇时，停止交换，而 Python 底层也是这么做的。
// Objects/clinic/listobject.c.h
#define LIST_REVERSE_METHODDEF \
{"reverse", (PyCFunction)list_reverse, \
METH_NOARGS, list_reverse__doc__},它由 list_reverse 负责实现。
// Objects/clinic/listobject.c.h
static PyObject *
list_reverse(PyListObject *self, PyObject *Py_UNUSED(ignored))
{
return list_reverse_impl(self);
}
// Objects/listobject.c
static PyObject *
list_reverse_impl(PyListObject *self)
{
// 如果列表长度不大于 1，那么什么也不做，直接返回 None 即可
if (Py_SIZE(self) > 1)
// 大于 1 的话，执行 reverse_slice，传递了两个参数
// 第一个参数显然是底层数组首元素的地址
// 而第二个参数则是底层数组中索引为 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;
// 数组元素的地址，从左往右是依次增大的
// 如果 lo < hi，证明 lo 依旧在 hi 的左边，那么交换指向的元素
// 如果 lo > hi，证明两者相遇了，交换结束
while (lo < hi) {
// 交换指向的元素，下面三步等价于 *lo, *hi = *hi, *lo
// 但 C 不支持这么写，它需要借助一个中间变量
PyObject *t = *lo;
*lo = *hi;
*hi = t;
// 两个指针继续靠近，指向的元素继续交换，直到两个指针相遇
++lo;
--hi;
}
}所以到现在，你还认为 Python 的列表神秘吗？虽然我们很难自己写出一个 Python 解释器，但是底层的一些思想其实并没有那么难，作为一名程序猿很容易想的到。
clear：清空列表
将列表中的元素全部清空，让列表回到初始状态。
// Objects/clinic/listobject.c.h
#define LIST_CLEAR_METHODDEF \
{"clear", (PyCFunction)list_clear, \
METH_NOARGS, list_clear__doc__},它由 list_clear 负责实现。
// Objects/clinic/listobject.c.h
static PyObject *
list_clear(PyListObject *self, PyObject *Py_UNUSED(ignored))
{
return list_clear_impl(self);
}
// Objects/listobject.c
static PyObject *
list_clear_impl(PyListObject *self)
{
// 在介绍 pop 方法的时候我们提到过这个函数
_list_clear(self);
Py_RETURN_NONE;
}
static int
_list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
if (item != NULL) {
// 获取列表的长度
i = Py_SIZE(a);
// 将 ob_size 设置为 0
Py_SET_SIZE(a, 0);
// ob_item 设置为 NULL
a->ob_item = NULL;
// 将容量设置为 0
a->allocated = 0;
// 将列表中每个元素指向的对象的引用计数减 1
while (--i >= 0) {
Py_XDECREF(item[i]);
}
// 释放底层数组所占的内存
PyMem_Free(item);
}
return 0;
}过程非常简单，当列表为空时，除了将 ob_size 和 allocated 设置为 0 之外，还会将底层数组释放掉，减少内存占用。
copy：列表的拷贝
调用列表的 copy 方法，可以将列表拷贝一份。
// Objects/clinic/listobject.c.h
#define LIST_COPY_METHODDEF \
{"copy", (PyCFunction)list_copy, \
METH_NOARGS, list_copy__doc__},它由 list_copy 负责实现。
// Objects/clinic/listobject.c.h
static PyObject *
list_copy(PyListObject *self, PyObject *Py_UNUSED(ignored))
{
return list_copy_impl(self);
}
// Objects/listobject.c
static PyObject *
list_copy_impl(PyListObject *self)
{
// 调用 list_slice，也就是基于切片获取元素
// 所以 data.copy() 等价于 data[:]
return list_slice(self, 0, Py_SIZE(self));
}
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
// 指向创建的新列表
PyListObject *np;
// 指向列表的底层数组的首元素
PyObject **src, **dest;
Py_ssize_t i, len;
// 创建的新列表的长度
len = ihigh - ilow;
if (len <= 0) {
return PyList_New(0);
}
// 创建底层数组长度为 len 的列表
np = (PyListObject *) list_new_prealloc(len);
if (np == NULL)
return NULL;
src = a->ob_item + ilow;
dest = np->ob_item;
// 将原始列表中的元素依次拷贝到新列表中
for (i = 0; i < len; i++) {
PyObject *v = src[i];
dest[i] = Py_NewRef(v);
}
// 将新列表的 ob_size 设置为 len
Py_SET_SIZE(np, len);
// 转成泛型指针之后返回
return (PyObject *)np;
}过程非常简单，但列表的 copy 方法或者说 data[:] 这种叫做列表的浅拷贝。关于列表的深浅拷贝也是初学者容易犯的错误之一，我们看一个 Python 的例子。
data = [[]]
# 默认是浅拷贝，这个过程会创建一个新列表
# 但我们说列表里面的元素都是指针，因此只会将里面的指针拷贝一份
# 而指针指向的内存并没有拷贝
data_cp = data.copy()
# 两个对象的地址是一样的
print(id(data[0]), id(data[0]))
"""
1338344668224 1338344668224
"""
# 操作 data[0], 会改变 data_cp[0]
data[0].append(123)
print(data, data_cp)
"""
[[123]] [[123]]
"""
# 操作 data_cp[0]，会改变 data[0]
data_cp[0].append(456)
print(data, data_cp)
"""
[[123, 456]] [[123, 456]]
"""之所以会有这样的现象，是因为 Python 的变量、容器里面的元素都是一个泛型指针 PyObject *，在传递的时候会传递指针， 但是在操作的时候会操作指针指向的内存。
所以 data.copy() 就是创建了一个新列表，然后把元素拷贝了过去，只不过元素都是指针。因为只是拷贝指针，没有拷贝指针指向的对象（内存），所以它们指向的是同一个对象。
但如果我们就想在拷贝指针的同时也拷贝指针指向的对象呢？答案是使用一个叫 copy 的模块。
import copy
data = [[]]
# 此时拷贝的时候，会把指针指向的对象也给拷贝一份
data_cp1 = copy.deepcopy(data)
data_cp2 = data[:]
data[0].append(123)
print(data_cp1) # [[]]
print(data_cp2) # [[123]]
# data[:] 这种方式也是浅拷贝，所以修改 data[0]，会影响 data_cp2[0]
# 但是没有影响 data_cp1[0]，证明它们是相互独立的，因为指向的是不同的对象浅拷贝示意图如下：
里面的两个指针数组存储的元素是一样的，都是同一个对象的地址。
深拷贝示意图如下：
里面的两个指针数组存储的元素是不一样的，因为是不同对象的地址。
注意：copy.deepcopy 虽然在拷贝指针的同时会将指针指向的对象也拷贝一份，但这仅仅是针对可变对象，而不可变对象是不会拷贝的。
import copy
data = [[], "古明地觉"]
data_cp = copy.deepcopy(data)
print(data[0] is data_cp[0]) # False
print(data[1] is data_cp[1]) # True为什么会这样，其实原因很简单。因为不可变对象是不支持本地修改的，你若想修改只能创建新的对象并指向它。但这对其它的变量而言则没有影响，其它变量该指向谁就还指向谁。
因为 b = a 只是将 a 存储的对象的指针拷贝一份给 b，然后 a 和 b 都指向了同一个对象，至于 a 和 b 本身则是没有任何关系的。如果此时 a 指向了新的对象，是完全不会影响 b 的，b 还是指向原来的对象。
因此，如果一个指针指向的对象不支持本地修改，那么深拷贝不会拷贝对象本身，因为指向的是不可变对象，所以不会有修改一个影响另一个的情况出现。
关于列表还有一些陷阱：
data = [[]] * 5
data[0].append(1)
print(data) # [[1], [1], [1], [1], [1]]
# 列表乘上一个 n，等于把列表里面的元素重复 n 次
# 但列表里面存储的是指针，也就是将指针重复 n 次
# 所以上面的列表里面的 5 个指针存储的地址是相同的
# 也就是说，它们都指向了同一个列表
# 这种方式创建的话，里面的指针都指向了不同的列表
data = [[], [], [], [], []]
data[0].append(1)
print(data) # [[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]}
# 它们都指向了同一个列表类似的陷阱还有很多，因此在工作中要注意，否则一不小心就会出现大问题。
总之记住三句话：虽然 Python 一切皆对象，但我们拿到的其实是指向对象的指针；变量在传递的时候本质上是将对象的指针拷贝一份，所以 Python 是变量的赋值传递、对象的引用传递；在操作变量（指针）的时候，会自动操作变量（指针）指向的内存。
小结
到此关于列表的内容就介绍完了，作为 Python 中的万能容器，我们可以自由地添加、修改和删除元素。但在使用的时候要了解它的底层结构以及元素是如何存储的，应该在什么场景下使用列表，它的每个方法的时间复杂度是多少。
下一篇文章来介绍元组，或许你觉得自己在代码中很少创建元组，但其实它无处不在。另外还有一个小插曲，就是我给 CPython 的元组修复了一个小 Bug，下一篇文章会说。
