楔
最近有读者私信让我介绍一下列表和字典哪个读写数据更快。
那我们就安排一下吧。 我们先介绍一下列表和字典的底层实现。 如果明白了具体的实现，那么一切问题就迎刃而解了。 我打算在多篇文章中介绍它。 这次我先介绍一下名单。
清单是如何实施的？
当你第一次学习列表时，书上可能会告诉你，列表是一个大仓库，里面可以存储任何东西。 但我们需要知道，无论是变量还是列表或元组中的元素，它们本质上都是一个指针。
根据我们使用列表的经验，我们可以得出以下两个结论：
该列表由底层的结构体表示，该结构体在头文件/.h中定义：
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;我们在里面看到以下成员：
：辅助指针，指向*类型的指针数组。 这个指针数组存放的是对象的指针，底层通过数组进行操作；
：容量，我们知道链表底层是一个使用C的数组，底层数组的长度就是链表的容量；
列表之所以有容量的概念，是因为元素可以动态添加和删除，但底层数组的长度在创建后是固定的。 所以一旦添加新元素，发现数组满了，就只能申请一个更长的数组，同时将旧数组中的元素按顺序复制到新数组中（这个过程就是扩容） list），然后add添加新元素，最后释放旧数组。
但问题来了。 不可能申请一个数组，每次添加一个元素就复制所有元素。 因此，当列表扩展时，就会要求数组更长，这样在添加元素时，就不需要每次都申请新的数组了。
这是列表底层结构的示意图。 我们看到底层数组的长度是5，也就是说此时链表的容量是5，但是里面只有3个*指针，也就是说链表是3个，或者说链表里有3个此时列出。 元素。
如果此时向列表中添加元素，则新元素将被设置在数组索引的位置，即索引3。设置后，它会自动加1，因为需要与数组的长度保持一致列表。
如果此时再向列表中添加一个元素，新元素仍然会被设置在index的位置，也就是此时index 4的位置。 然后加 1 使其变为 5。
列表的容量是5，但是此时长度也达到了5，这意味着下次没有办法容纳新的元素了。 因为此时列表的长度，或者说元素的数量，已经达到了容量。 当然，最直观的还是这里的底层数组，显然已经全部被占用了。 那么此时想要接收新的元素该怎么办呢？ 显然只能扩大。
原来容量是5，长度也是5，当有新元素来的时候，没有位置了，所以需要扩容。 但是扩容的时候肯定会申请更大的容量，也就是申请更长的底层数组。
申请的新底层数组的长度是9，所以链表的容量变成9。然后将原数组中的*按顺序复制到新数组中，并让它指向新数组。 然后将新元素设置在新数组中的索引 5 处，并添加 1（现在变为 6）。
以上就是列表底层扩展时所经历的过程。
并且从上面的图片我们可以知道，之后列表的地址将保持不变。 因为如果长度没有达到容量，那么实际上会向底层数组设置一个新元素； 如果长度达到容量，那么就会扩容，但扩容只是申请一个新的指针数组，然后再指向它。
所以底层的指针数组会改变，但结构体实例本身不会改变。 因此，当执行列表时， 、 pop ，因为是本地操作，所以它的地址不会改变。
我们看一下列表占用的内存大小是如何计算的：
所以一共40个字节，但是别忘了在计算列表大小的时候，指向的指针数组也包含在内。 因此：列表的大小 = 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]] 的底层结构，看看它们之间的区别他们：
至此，相信您已经彻底掌握了列表的结构。 我们来分析一下列表相关操作的时间复杂度。
添加元素
假设有一个如下所示的列表：
让我们看看添加元素时它的行为如何。
首先添加元素的方法有很多种。 该方法用于将一个元素追加到末尾。 我们来看看它的底层实现。
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;
}以上就是逻辑。 所谓插入和追加本质上是先计算索引，然后通过索引设置元素。
如果上面的列表有一个 6，它将变成如下：
还是很容易理解的。
除了添加元素之外，还可以使用这种方法。 与只能追加在末尾的方法不同，该方法可以插入到任意位置。
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;
}逻辑不难理解，然后就是时间复杂度了。
获取元素
列表支持根据索引检索元素，比较简单。 直接获取底层指针数组即可，然后根据索引获取，所以是一个时间复杂度为O(1)的操作。
当然，除了索引之外，还可以使用切片，但是切片底层仍然使用索引。
# lst[1: 8: 3] 等价于
start = 1
end = 8
step = 3
while start < end:
item = lst[start]
# .....
start += step所以，一些看似高端的操作，其实底层并没有那么神秘。
设置元素
我们可以获取指定索引处的元素，当然也可以设置它。
# 获取元素
item = lst[5]
# 设置元素
lst[5] = item前面说过，添加元素本质上是通过设置元素来实现的。 如果列表的最大索引为n，那么相当于将元素设置为n+1； 而是先将待插入位置后面的元素按顺序向后移动，然后将待插入位置设置为指定元素。 本质上，元素也在不断地被设置。
设置元素的时间复杂度显然是O(1)。 当然，设置现有元素相当于修改它。
另外，设置元素时，除了使用索引之外，还可以使用切片。 使用切片的时候非常灵活，我们来演示一下。
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中有7个元素, 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应该不难理解。 建议看源码中的具体实现。c。 检查时有以下几个功能，应牢牢掌握。
这两个函数可以接收索引或切片：
以上是设置元素时的具体实现。 虽然是设置元素，但也用于添加和删除。
删除元素
您可以使用 pop 来删除元素。 默认情况下，元素从末尾弹出。 当然，我们也可以指定索引来弹出指定元素。
而我们说过删除元素时会调用pop和del。
lst = [1, 2, 3, 4, 5]
# 修改元素，在底层相当于修改指针数组中索引为 4 的元素
lst[4] = 55
print(lst)
"""
[1, 2, 3, 4, 55]
"""
# 添加元素，本质上是将元素设置在索引为 5 的位置
# 但我们不能执行 lst[5] = 6，因为索引越界了
# 需要调用 append，由解释器帮我们设置
lst.append(6)
print(lst)
"""
[1, 2, 3, 4, 55, 6]
"""
# 删除索引为 3 的元素
# 可以执行 del lst[3] 或者 lst.pop(3)
# 但它们底层都等价于如下
lst[3: 4] = []
print(lst)
"""
[1, 2, 3, 55, 6]
"""解释器是用C实现的，而C是一种非常简单的语言，所以列表的一些花哨的功能又回到了C，这只是对C数组的一些简单操作。
列表扩展
前面提到，添加元素时，可能会出现容量不足的情况。 因此，当列表和方法执行时，它们会首先检查列表中存储的元素数量是否已达到当前容量。 一旦达到了，就必须先扩容。
从内部来看，它的扩展机制是这样的。
我们来验证一下：
lst = [0] * 1000
# 长度和容量一致
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
1000
1000
"""
# 再必须提一下
# 扩容是当解释器在添加元素时，发现容量不够的时候才会扩容
# 而使用 lst = [...] 这种方式创建的列表
# 其大小和容量是相等的
# 但此时添加一个元素的话, 那么ob_size会变成1001，大于容量1000
# 所以此时列表就要扩容了, 执行 list_resize
# (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
# 显然 newsize 就是 1001
print(
1001 + (1001 >> 3) + (3 if 1001 < 9 else 6)
) # 1132
# append一个元素，列表扩容
lst.append(123)
print((lst.__sizeof__() - 40) // 8) # 1132结果是一样的，因为底层是这样实现的，所以结果一定是一样的。 只是我们通过这个测试方法证明了这一点，加深了对榜单的理解。
介绍完了扩容，我们再来介绍一下缩减，因为如果列表元素的数量远小于容量，就必须缩减，否则会造成内存的浪费。 那么什么时候会减少呢？ 答案是，当列表中的元素数量小于容量的一半时，它就会收缩。
举一个生活中的例子，假设你租了10间房间作为办公用途。 显然你必须支付10个房间的租金。 不管你使用与否，一旦租用，你就一定要付费。 对于底层数组也是如此。 只要申请了，不管有没有存储元素，内存就已经被占用了。
但有一天你将不再使用 10 个房间。 如果您想使用8个或9个房间，那么剩余的房间将免费。 但由于退租比较麻烦，而且我也只有一两间空闲房，所以干脆就不退租了，还是会付10间房的钱，这样我需要的时候就不用再租了有一天再次使用它。
对于列表也是如此。 删除元素时（相当于不再使用房子），如果发现长度小于容量的一半，则不会缩小尺寸。 但反之，则会减少。 例如，如果有8个房间空置，即只有两个房间就够了，那么这个时候就必须交出租金。 如果8个房间空置，则可以交出6个房间。
lst = [0] * 1000
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
1000
1000
"""
# 删除500个元素, 此时长度或者说ob_size就为500
lst[500:] = []
# 但是ob_size还是达到了容量的一半, 所以不会缩容
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
500
1000
"""
# 如果再删除一个元素的话, 那么就要进行缩容了
# 因为 ob_size 变成了 499, 小于 1000 // 2
# 缩容之后容量怎么算呢? 还是之前那个公式
print(499 + (499 >> 3) + (3 if 499 < 9 else 6))
"""
567
"""
# 测试一下, 删除一个元素
# 看看会不会按照我们期待的规则进行缩容
lst.pop()
print(len(lst))
print((lst.__sizeof__() - 40) // 8)
"""
499
567
"""一切都和我们想象的一样，因为源代码就是这么写的。
最后，源码中有一个if判断，即当list的长度为0时，缩减后的容量也会为0。
lst = [0] * 1000
lst[:] = []
print(
len(lst), (lst.__sizeof__() - 40) // 8
) # 0 0
# 如果按照之前的容量变化公式的话, 会发现结果应该是3
# 但是结果是0, 就是因为多了if判断
# 如果newsize是0, 就把容量也设置为0
print(0 + (0 >> 3) + (3 if 0 < 9 else 6)) # 3你为什么这么做？ 因为我认为如果列表长度为0，说明你不想使用这个列表，所以不需要申请额外的3个。以租房为例，如果你不使用其中任何一个房间，意味着你不能使用这里的房间来工作，所以你可以把它全部退回。
概括
