python的list容器和C++ stl中的list容器不同，它和C++中的vector容器比较相似，python的list容器中存储的都是PyObject*指针，PyListObject对象不仅是一个变长对象，还是一个可变对象。看一下PyListObject的定义：
[code lang=”C”]
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for ‘allocated’ elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
[/code]
加入一个list能容纳10个元素，已经装入5个元素，则ob_size变为5，allocated为10。
创建与维护：
python创建list的唯一方法是PyList_New。这个函数接收一个size参数。源码如下：
[code lang=”C”]
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
static int initialized = 0;
if (!initialized) {
Py_AtExit(show_alloc);
initialized = 1;
}
#endif
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
/* Check for overflow without an actual overflow,
* which can cause compiler to optimise out */
if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
return PyErr_NoMemory();
nbytes = size * sizeof(PyObject *);
if (numfree) {
numfree–;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
count_reuse++;
#endif
} else {
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
#ifdef SHOW_ALLOC_COUNT
count_alloc++;
#endif
}
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;
}
[/code]
从上面的代码发现python的list要先检查是否内存溢出，然后为对象申请空间，开辟缓冲池，在没有元素的情况下将其初始化为null。
python的list的内存结构如下：
从以上可以看出，python的list其实在内存中是分为两部分的，ob_item是指向一个object*的数组。python的list容器主要有一下几种操作，设置、插入、删除：
设置：设置元素不许要移动内存；
插入：需要移动内存；
删除：需要移动内存。
同样，python的list也存在对象池这个概念，一个list释放后其实是释放了ob_item这个指针所指的内存，当需要再用到这个list是，python将会从对象池中取出这个list，并重新设置他的ob_item指针。如下：
OK，list讲完了，明天学习dict对象。