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

Question

Python内置列表数据类型通常使用什么底层数据结构实现？

答案：Python的内置列表数据类型通常使用动态数组作为其底层数据结构来实现。

- Nixuz

---

两个选项：1）只是出于好奇；2）过早优化。 - flybywire

有人问了我这个问题，我告诉他们我的直觉是实现是基于数组的，但我不确定。这让我有点好奇，所以我决定问一下。 - Nixuz

信不信由你，我确实花了几分钟时间在谷歌上搜索答案，即使我下载了源代码，我可能也不知道从哪里开始。我想这里的某个人会知道答案，并且只需付出最少的努力。结果证明我是正确的。他们轻松获得赞誉，我快速得到答案，双方都受益。 - Nixuz

这并不是一件傻事。Python中的列表包含append()操作而不包括prepend()操作，正是由于Guido等人认为列表的用户需要非常明确地意识到它是一个数组，很容易高效地追加内容，但却很昂贵地在前面添加内容。 - Brandon Rhodes

可能是Python的列表是如何实现的？的重复问题。 - bain

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

- e1i45

---

在deque模块出现之前，这个教程就已经存在了很久，这就是原因。如果可能的话，请将其报告到bugs.python.org，并提供一个正确的语句补丁，这样教程将不再给出不正确的提示。 - Philippe F

在几次面试中，我被告知列表的底层数据结构是链表。这是正确的吗？如果是这样，那么对于字典也是链表。是这样吗？ - Shruti Kar

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;

- Georg Schölly

Answer 3

在Jython实现中，它是一个ArrayList<PyObject>。

- nategood

Answer 4

尽管这可能很明显，但值得指出的是，Python列表是动态数组（与静态数组相对）。这是一个重要的区别，在工作面试问题/学术中会涉及到。

由于数组是动态的，Python在声明时保留一定量的内存，例如：

somelist = []

因为额外的内存已经被预留，执行 somelist.append() 只需写入下一个预留的内存槽，因此大部分时间都是 O(1)。对于静态数组，通常情况下数组已满（例如，如果有4个字节，则数组大小为4），添加操作总是需要预留一组全新的内存空间（现在可能是5个字节），并将内容复制过去，因此其时间复杂度通常为 O(n)。

- Adam Hughes

Answer 5

列表是Python中的内置数据结构。但可以用于创建用户定义的数据结构。由列表创建的两个主要用户定义的数据结构是栈和队列。

- Riya Parashar

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心找到有关如何编写良好答案的更多信息。 - Community