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

Question

Python内置的列表数据类型通常是用什么样的底层数据结构来实现的呢？

Answer 1

在这个Jython的实现中，它使用的是一种叫做ArrayList<PyObject>的东西。

Answer 2

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;

Answer 3

列表对象实际上是用数组来实现的。它们在处理固定长度的操作时速度很快，但如果你使用pop(0)或者insert(0, v)这些操作，就会导致内存移动的成本是O(n)。这意味着当你从列表的开头删除一个元素或者在开头插入一个元素时，整个列表的其他元素都需要移动，这样会比较耗时。

另外，值得一提的是，Python的教程在讲数据结构时推荐使用pop(0)来模拟队列，但却没有提到O(n)的性能问题，也没有介绍deque这个选项。

相关链接： http://docs.python.org/library/collections.html#collections.deque

还有一个链接： http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

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

5 个回答

撰写回答