Python列表的底层数据结构是什么?

列表对象实现为 阵列。它们经过优化,速度很快 固定长度运算和招致O(n) pop(0)的内存移动成本和 插入(0,v)更改的操作 的大小和位置 底层数据表示。

另请参见: http://docs.python.org/library/collections.html#collections.deque

顺便说一句,我发现有趣的是,Python数据结构教程建议使用pop(0)来模拟队列,但没有提到O(n)或双端队列选项。

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

CPython:

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;

如下行所示,该列表被声明为指向以下对象的指针数组 PyObjects .

PyObject **ob_item;

在 Jython implementation ,这是一个 ArrayList<PyObject> .

虽然这可能是显而易见的,但值得一提的是Python列表 Dynamic 数组(与 Static 阵列)。这是面试问题/学术界提出的一个重要区别。

因为数组是动态的,Python在声明时会保留一定量的内存,例如:

somelist = []

因为已经留出了额外的内存,执行 somelist.append() 只需写入下一个保留的内存插槽,因此 O(1) 大多数时候。对于静态数组,通常数组是满的(即如果有4个字节,则数组大小为4),追加的总是 O(n) 因为它们需要保留一组全新的内存(现在可能是5个字节)并复制内容。