python - Python 的 List 是如何实现的？

Question

是链表还是数组？我四处寻找，只发现人们在猜测。我的 C 知识还不够好，无法查看源代码。

Answer 1

实际上，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 FAQ .