列表的内部实现

listobject.h：https://github.com/python/cpython/blob/949fe976d5c62ae63ed505ecf729f815d0baccfc/Include/listobject.h#L23

listobject.c: https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Objects/listobject.c#L33

list的具体结构：

从Python中的源码可以很明显的看出，list的本质是一个over-allocate的array。(会分配比实际元素更多的空间，比如一个array有5个元素，但如果是over-allocate则可能会分配10个元素的空间大小)

其中，ob_item是一个指针列表，里面的每一个指针都指向列表的元素，而allocate则存储了这个列表已经被分配的空间大小。

需要注意的的是，allocated与列表的实际空间大小有大小的区别，列表的实际空间大小可以用len(list)返回值查看，就是源码中注释的ib_size，表示这个列表总共存储了多少个元素，在实际情况下，为了优化存储结构，避免每次增加元素都要分配内存，列表预分配的空间allcoated都会大于ob_size(源码31行)

所以，他们的关系是：allocated >= ob_size即len(list) >=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 ···

元组的内部实现

tupleobject.h： https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Include/tupleobject.h#L25

tupleobject.c：https://github.com/python/cpython/blob/3d75bd15ac82575967db367c517d7e6e703a6de3/Objects/tupleobject.c#L16

tuple的具体结构：

从源码来看，元组和本质也是一个array，但是空间大小固定。Python中针对元组做了很多的优化，来提升在程序中的效率。

元组静态资源缓存

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

对于一些静态变量，比如元组，如果它不被使用或者占用空间不大时，Python会暂时缓存这部分内存，这样，当我们下次再次创建同样大小的元组时，Python就不再向操作系统发出请求去请求内存，而是直接分配之前缓存的内存空间，这样就能大大加快程序的运行速度。

可以理解为，PyTupleObject对象在被析构时，不仅对象本身没有被回收，而且连底层的指针数组也被缓存起来了。

Q.E.D.