python的list实现

list对象定义：

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

list对象是变长对象，所以有变长对象头.
ob_item数组为真正的存储容器，用来存储PyObject对象指针。
ob_size表示list长度。
allocated表示list已分配了多少存储空间。

list创建与销毁

list的创建分两步。

1. 创建list对象本身。
2. 为ob_item分配内存。
   list的销毁也分两步。
3. 回收ob_item的内存。
4. 销毁list对象本身。
   这样的对象创建和销毁方案是为对象池（free_lists）服务的。

在创建list阶段，Python会查看free_lists中是否有缓存对象。若有，则直接从free_lists取出。若没有，则从堆上分配list对象内存。
在销毁list阶段，若缓存list数（num_free_lists）小于最大可缓存数（MAXFREELISTS ），则将list对象缓存到free_lists备用。若超过了num_free_lists，则直接释放对象内存。

赋值操作

设置元素操作可以理解为list[i] = obj。

插入操作

插入元素操作：实质是函数ins1的包装。ins1函数的关键操作是，先通过list_resize（下面细说）调整list长度，然后确定插入点。由于Python list的索引可以为负数（即末尾元素索引为-1），所以索引值小于0时得加上长度得到C数组的索引。接着将插入点后的元素向后搬运，在插入点写入对象。从此可以看出list就是C里数组的概念。

list_resize函数：int list_resize(PyListObject *self, Py_ssize_t newsize)
如果allocated / 2 <= newsize <= allocated，则直接把ob_size设置成newsize。如果不在这个范围内，就按如下方案realloc内存：new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
不是很理解为什么采用这个方案，求指教。

删除元素

删除元素操作：实质是函数app1的包装。app1函数的关键操作是，先找到第一个对象的位置，然后通过list_ass_slice函数将删除点前后的两段合并。