python中的高级特性之一就是内置了list,dict等。今天就先围绕列表（List）进行源码分析。
Python中的List对象（PyListObject）
Python中的的PyListObject是对列表的一个抽象，内置了插入、添加、删除等操作。不同List中存储的元素的个数会是不同的，所以PyListObject是一个变长对象。而PyListObject中支持插入删除等操作，可以在运行时动态地调整其所维护的内存和元素，所以它又是一个可变对象。PyListObject的定义
在列表对象接口listobject.h中，PyListObject的定义是：
typedef struct {PyObject_VAR_HEADPyObject **ob_item;Py_ssize_t allocated; 其中，ob_item是指向了元素列表所在的内存块的首地址，allocated维护了当前列表中的可容纳的元素的总数。
我们知道，用户选用list正是为了可以频繁的执行插入或删除等操作，如果是需要存多少就申请多大的内存，这种内存管理显然是低效的。那么Python内部是怎么实现的呢？这就与刚才所提到的allocated有关了，我们知道，在PyObject_VAE_HEAD中有一个ob_size，在PyListObject中，每一次需要申请内存时，总会申请一大块内存存，这时申请的总内存的大小记录记录在allocated中，而其中实际被使用了的内存的数量则记录在ob_size中。
PyListObject对象的创建与维护
创建
在列表对象的实现文件listObject.c文件中，我们可以看到，Python对于创建一个列表，提供了唯一的一条途径，就是PyList_New（），对应的代码如下：PyObject *PyList_New(Py_ssize_t size){PyListObject *op;size_t nbytes;#ifdef SHOW_ALLOC_COUNTstatic int initialized = 0;if (!initialized) {Py_AtExit(show_alloc);initialized = 1;}#endifif (size < 0) {PyErr_BadInternalCall();return NULL;}//进行溢出检查if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))return PyErr_NoMemory();nbytes = size * sizeof(PyObject *);//为PyListObject对象申请空间，使用到缓冲池技术if (numfree) {numfree--;op = free_list[numfree];_Py_NewReference((PyObject *)op);#ifdef SHOW_ALLOC_COUNTcount_reuse++;#endif} else {op = PyObject_GC_New(PyListObject, &PyList_Type);if (op == NULL)return NULL;#ifdef SHOW_ALLOC_COUNTcount_alloc++;#endif}//为PyListObject对象中维护的元素列表申请空间if (size <= 0)op->ob_item = NULL;else {op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);if (op->ob_item == NULL) {Py_DECREF(op);return PyErr_NoMemory();}memset(op->ob_item, 0, nbytes);}Py_SIZE(op) = size;op->allocated = size;_PyObject_GC_TRACK(op);return (PyObject *) op;} 首先，进行溢出检查。接下来，就是List对象的创建了，Python中的list对象实际上是分为两部分的，一是PyListObject对象本身，二是PyListObject对象维护的元素列表，而这两块内存是通过ob_item建立联系的。
在创建PyListObject对象时，首先检查缓冲池中free_list是否有可用的对象，如果有，则直接使用，若没有可用对象，则通过PyObject_GC_New在系统堆中申请内存，在Python2.7.12中，free_lists中最多维护80个PyListObject对象。
当创建了新的PyListObject对象之后，会根据调用PyList_New是传递的size参数创建ListObject对象所维护的元素列表。
设置元素
元素创建好了，下一步就是向元素中添加元素了,通过PyList_SetItem()实现：
intPyList_SetItem(register PyObject *op, register Py_ssize_t i,register PyObject *newitem){register PyObject *olditem;register PyObject **p;if (!PyList_Check(op)) {Py_XDECREF(newitem);PyErr_BadInternalCall();return -1;}//索引检查if (i < 0 || i >= Py_SIZE(op)) {Py_XDECREF(newitem);PyErr_SetString(PyExc_IndexError,"list assignment index out of range");return -1;}//存放元素p = ((PyListObject *)op) -> ob_item + i;olditem = *p;*p = newitem;Py_XDECREF(olditem);return 0;} 首先，进行类型检查，然后进行索引的有效性检查，当类型检查和索引检查均通过的时候，就可以将待加入的Pyobject*指针放在指定的位置了。
插入元素
插入元素和设置元素的不同在于：设置元素不会将ob_item指向的内存发生变化，而插入内存可能会导致ob_item指向的内存发生变化。
比如：a = [0, 0, 0, 0];a[2] = 3;print a[0, 0, 3, 0]a.insert(2,3)[0,0,2,3,0]
这个插入动作确实导致了元素列表的内存发生变化。关于插入，在列表中有两种操作：insert()和append()。
insert通过调用PyList_Insert()方法来完成元素的插入动作，首先判断PyListObject对象有足够的内存容纳我们期望插入的元素，然后调用list_resize()函数调整列表容量，确定插入点，插入元素。
在调整PyListObject对象所维护对象的内存时，Python使用了两种方法：1. 当newsize < allocated && newsize > allocated/2 时，简单调整ob_size;2. 调用realloc,重新分配空间。 append是通过调用PyList_Append()方法，在第ob_size+1个位置上插入。删除元素
对于一个容器而言，除了创建，插入这些操作，肯定是还得有删除操作的。remove()a = [1, 2, 3, 4]print a.remove(3)[1, 2, 4]
remove()调用了listremove操作。Python会对整个列表进行遍历，将待删除的元素与PyListObject中的每个元素一一比较，比较操作通过PyObject_RichCompareBool完成，当返回值大于0，则表示列表中有和待删元素匹配的元素，则Python发现之后调用list_ass_slice删除该元素。
PyListObject对象缓冲池
在这之前，我们学习到，在创建PyListObject对象时，会首先检查缓冲区中的free_lists中是否有可用的对象。
在创建一个新的的对象时，实际也是分为两部，首先创建PyListObject对象，然后创建PyListObject对象所维护的元素列表，与之对应，在销毁一个list时，销毁的过程也是分离的，首先销毁PyListObject所维护的元素列表，然后释放PyListObject对象自身。。 在删除PylsitObject对象自身时，Python会先检查我们开始提到的那个缓冲池free_list，查看其中缓存的PyListObject的数量是否已经满了，如果没有，就将待删除的PyListObject对象放到缓冲池中，以备后用。 因此，那个在Python启动时空荡荡的缓冲池原来都是被本应该死去的PyListObject对象给填充了，在以后需要创建新的PyListObject的时候，Python会首先唤醒这些对象，重新分配Pyobject*元素列表占用的内存，重新拥抱新的对象。