内部结构#

list 对象是一种 变长对象 ，因此包含变长对象公共头部。除了公共头部， list 内部维护了一个动态数组，而 数组则依次保存元素对象的指针：

**ob_item ，指向动态数组的指针，动态数组保存元素对象的指针；
allocated ，动态数组长度，即列表容量；
ob_size ，动态数组 当前保存元素个数，即列表长度。

对象操作#

append#

python中的list的实现非常像 C++ 中的Vector

1	l = list（） # 初始化一个空列表

字段 ob_size存储实际大小，其类型为Py_ssize_t，通常为64位，1 << 64可以表示的数非常大，通常在ob_size字段 溢出之前会耗尽 RAM

如果我们append('a') 1个元素：

ob_size 变为 1, ob_item 指向一个 大小为4的新内存块

相继append三个元素：

ob_size 变为 4, 内存块满了

大多数情况下， append 方法性能都足够好，时间复杂度是 O(1)。

动态扩容#

继续append一个元素：

这是resize相关代码

/* cpython/Objects/listobject.c */
/* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */
/* currently: new_allocated = 5 + (5 >> 3) + 3 = 8 */
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);  # 扩容时，预留一定的余量，(newsize >> 3)表明余量一般是 1/8 左右

如果 list 对象内部数组已用满，再添加元素时则需要进行扩容。 append 等方法在操作时都会对内部数组进行检查，如需扩容则调用 list_resize 函数。在 list_resize 函数， Python 重新分配一个长度更大的数组并替换旧数组。

由于内部数组扩容时，需要将列表元素 从旧数组拷贝到新数组，时间复杂度为 O(n) ，开销较大。为此， Python 在为内部数组扩容时，会预留一定余量，一般是 1/8 左右 。

pop#

1 2	>>> l.pop() 'e'

我们可以看到这里只是简单将元素e 弹出，内存布局并未发生变化。

动态减容#

实际上，每次pop，都会调用 resize 函数。

/* cpython/Objects/listobject.c */
/* allocated: 8, newsize: 3, 8 >= 3 && (3 >= 4?), no */
if (allocated >= newsize && newsize >= (allocated >> 1)) {
    /* Do not realloc if the newsize deos not fall
       lower than half the allocated size
        不分配内存，仅改变ob_size的值    */
    assert(self->ob_item != NULL || newsize == 0);
    /* only change the ob_size field */
    Py_SIZE(self) = newsize;
    return 0;
}
/* newsize小于allocated的一半时，会重新分配内存 */
/* 3 + (3 >> 3) + 3 = 6 */
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

如果理解了pop 每次都会调用 resize 函数，下面情形就很容易理解了

1 2	>>> l.pop() 'd'

LiuWen's Blogs

[python源码分析] 7.可变容器list