String 对象的实现比较复杂，主要是因为 unicode 编码的特殊性，虽然还有不少不清楚的细节，但是我不打算在此卡住，直接进入 Python 另一个基本类型 List。与 String、Int 类型不同，List 是一个可变对象。

List 对象的结构

List Object 的结构非常简单，根据 Include/listobject.h 中。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

删除掉注释只有几行，将 PyObject_VAR_HEAD 展开，List Object 看起来这样。

List Object 可以认为是 C 风格指针数组的高级封装，真正的载荷数据是 PyListObject.ob_item，allocated 是 ob_item 指向的 预分配 元素数量，但这些内存并不一定被全部使用，真正使用的数量是 PyObject_VAR_HEAD 中的 ob_size。显然 ob_size 只可能小于等于 allocated。

从 List Object 的结构可以看出，List 之所以能作为通用容器使用，是因为它是以 PyObject * 数组保存数据，并没有限制 List items 的类型。List Object 是一个类型、数据分离的结构，通过对 ob_item 的修改实现 List 的可变性。

可变数组的关键实现

List 的可变性通过对 List 元素的：

增、
删、
改、

实现。仅从最底层的 C 语言来看，删和改难度都比较小，主要是对内存就地复制操作。比如删除元素的操作：

由于 List Object 的元素实际上是 PyObject 引用，修改元素也只需要就地修改元素的指针即可，不需要移动内存。真正的困难在增加元素的情况，比如插入元素、追加元素之类。通常可以用下面一些方法：

一次性预分配 “相当多” 内存，确保增加元素操作可以就地进行；
增加元素时重新分配适合大小的内存，并将旧 List 的引用复制过来。

显然第一种方法是不合理的，一方面有严重的内存浪费，另外实际上很难确定应该一次性分配多少内存。

第二种方法可以实现动态数组，但频繁的内存分配会引起内存碎片化，效率不高。

因此 Python 采用了一种折中方案，每次扩大数组大小时，会预分配一些内存，这样多次 “调整” 数组大小，实际上只有预分配内存不够时才会真正调整内存大小。缩小数组时则反之。其实现：

//Objects/listobject.c:35
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    Py_ssize_t allocated = self->allocated;

    // newsize 介于 allocated 的 0.5 ～ 1 之间，则直接调整 ob_size 后返回。
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    // 如果 newsize 小于 allocated/2 或者大于 allocated，重新分配空间
    // 新的 allocated 增加模式是 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);

    // 调整内存大小
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

如果将 new_size 落到 allocated 的不同区域相应的操作绘制出来：

无论低于 allocated/2 还是超过 allocated 都会引起 realloc。

Think In Python

14. 初始 List Object

List 对象的结构

可变数组的关键实现