Python列表的基础数据结构是什么？

Question

用于实现Python内置列表数据类型的典型底层数据结构是什么？

Answer 1

列表对象实现为数组.它们针对快速固定长度操作进行了优化,并导致pop(0)和insert(0,v)操作的O(n)内存移动成本,这些操作改变了底层数据表示的大小和位置.

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

顺便说一句,我觉得有趣的是数据结构的Python教程建议使用pop(0)来模拟队列但不提O(n)或deque选项.

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

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

在Jython实现中,它是一个ArrayList<PyObject>.