Python的列表是如何实现的？

Question

Python的列表是如何实现的？是链表还是数组？我四处搜寻，只发现有人在猜测。我的C知识还不够好，不能看源代码。

Answer 1

是个动态阵列..实际证明：索引使用(当然，与极小的差异(0.0013！)同时，无论索引是什么：

...>python -m timeit --setup="x = [None]*1000" "x[500]"10000000 loops, best of 3: 0.0579 usec per loop...>
python -m timeit --setup="x = [None]*1000" "x[0]"10000000 loops, best of 3: 0.0566 usec per loop

如果IronPython或Jython使用链接列表(它们会破坏许多被广泛使用的库的性能)，我会感到惊讶，因为它们假设列表是动态数组。

Answer 2

实际上，C代码非常简单。扩展一个宏并删除一些不相关的注释，基本结构在listobject.h，它将列表定义为：

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* 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
     */
    Py_ssize_t allocated;} PyListObject;

PyObject_HEAD包含引用计数和类型标识符。因此，它是一个过分配的向量/数组。当数组满时调整大小的代码在listobject.c..它实际上并不是数组的两倍，而是通过分配

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);new_allocated += newsize;

每一次，newsize请求的大小(不一定)allocated + 1因为你可以extend由任意数目的元素代替append一个接一个地给他们看)。

另见Python常见问题.

Answer 3

在CPython中，列表是指针数组。Python的其他实现可以选择以不同的方式存储它们。