Python 3.7 的 list 源码

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的具体结构：

 

 

可以看到，list 本质上是一个 over-allocate 的 array。其中，ob_item是一个指针列表，里面的每一个指针都指向列表的元素。而allocated则存储了这个列表已经被分配的空间大小

需要注意的是，allocated与列表实际空间大小的区别。列表实际空间大小，是指len(list) 返回的结果，即上述代码注释中的ob_size，表示这个列表总共存储了多少个元素。实际情况下，为了优化存储结构，避免每次增加元素都要重新分配内存，列表预分配的空间 allocated 往往会大于 ob_size（详见正文中的例子）。

所以，它们的关系为：allocated >= len(list) = ob_size。

如果当前列表分配的空间已满（即 allocated == len(list)），则会向系统请求更大的内存空间，并把原来的元素全部拷贝过去。列表每次分配空间的大小，遵循下面的模式：

0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

 

Python 3.7 的 tuple 源码

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 的具体结构：

 tuple和list相似，本质也是一个array，但是空间大小固定。不同于一般array，python的tuple做了许多优化，来提升程序中的效率。

举个例子，当tuple的大小不超过20时，python就会把它缓存在内部的一个free list中。这样，如果你以后需要再去创建同样的tuple，Python 就可以直接从缓存中载入，提高了程序运行效率。